论文部分内容阅读
摘要：本文通过应用Cranfield体系——构建查询样例集合、查询信息需求分类、抓取搜索引擎结果、规定标注准则、计算性能评价指标的基本流程，对目前常用中文搜索引擎，百度、谷歌、搜狗、搜搜、人民搜索性能从定量的角度，进行较为全面的评价。其结果可供用户在选择、利用这些搜索引擎时参考。
关键词：Cranfield评价体系；查询样例集合构建；查询信息需求
中图分类号：G354文献标识码：A文章编号：1007-9599 (2011) 15-0000-01
Chinese Search Engine Performance Comparative Studyon Cranfield System
Li Yujun, Bao Yonghan
(Qinghai University,Xining810016,China)
Abstract:Cranfield system through the application-to build a collection of sample query,the query classification of information needs,crawling of search engine results,provided labeling guidelines,the basic computing performance evaluation process,the most commonly used Chinese search engine,Baidu,Google,Sogou,search,people search performance from a quantitative point of view,a more comprehensive evaluation.The result for the user in the selection,use these search engines for reference.
Keywords:Cranfield evaluation system;Query sample collection building;Query information needs
一、Cranfield評价体系
（一）体系的建立。二十世纪五十年代，Cleverdon等人在Cranfield University工作时提出了这样一套评价系统：由查询样例集、正确答案集、评测指标构成的完整评测方案，并从此确立了“评价”在信息检索研究中的核心地位，其核心思想沿用至今。
（二）Cranfield评价体系由三个环节组成。（1）抽取具有代表性的查询词，组成一个规模适当的查询样例集合。（2）针对查询样例集合，从检索系统的语料库中寻找对应的结果，进行标注。（3）将查询词和带有标注信息的语料库输入检索系统，对系统反馈的检索结果，使用预定义好的评价计算公式，用数值化的方法来评价检索系统结果和标注的理想结果的接近程度。
二、查询信息需求的分类
（一）导航类查询。查找某个已知存在的页面/资源，针对特定站点主页的查找。
（二）信息类查询。查找与某个主题相关的权威内容的页面，获取相关权威信息，没有明确查询目标，往往需要不止一个结果。
（三）事务类查询。查找与某个特定需求相关的资源，以进一步交互，没有明确查询目标，但往往一个好的结果就能完成需求。
三、查询样例集合的构建
根据其构建的查询样例集合，抓取常用的五个中文搜索引擎（百度、谷歌、搜狗、搜搜、人民搜索）对这部分查询词的查询结果，每个搜索引擎抓取查询结果的前十位结果，并利用这些结果构建Pooling。
四、搜索引擎性能指标评价的计算
（一）需要计算的性能指标及其公式。
1.首位相关结果倒数（Reciprocal Rank）
2.前N位准确率（Precision@N）。N=10，20：第一页结果中的准确程度。
3.前N位成功率（Success@N）。N=10，20：第一页中是否有满足需求的结果。
4.平均准确率（Average Precision）。N为标准答案的数目；Precision（i）为系统找到第i个答案时的Precision。
（二）计算性能指标值如下表所示：
表1导航类查询的MRR、MAP值
导航 谷歌 搜狗 百度 搜搜 人民搜索
MAP 0.838056 0.797633 0.725333 0.606178 0.111111
MRR 0.955556 0.904444 0.795556 0.807222 0.16
表2信息类查询的MRR、MAP值
事务 百度 谷歌 搜狗 人民搜索 搜搜
MAP 0.611875 0.6115 0.59775 0.492375 0.436375
S@10 0.825 0.9 0.875 0.525 0.9
S@5 0.825 0.9 0.875 0.525 0.775
表3事物类查询的MRR、MAP值
信息 谷歌 搜搜 百度 搜狗 人民搜索
MAP 0.460955 0.425 0.413182 0.320091 0.090909
P@10 0.550545 0.472091 0.447727 0.509909 0.181818
P@5 0.641111 0.547778 0.525556 0.295556 0.111111
五、分析
（一）导航类信息查询结果的分析。分析导航类信息查询结果，可以得出：五个常用中文搜索引擎，平均首现正确答案排序倒数（MRR）值都要比平均准确率（AMP）高，但是这几个搜索引擎在平均准确率（AP）、首先正确答案倒排序（RR）方面还是有差距，其中谷歌、搜狗在导航类信息查询方面准确率要比百度、搜搜高。
（二）信息类信息查询结果的分析。分析信息类信息查询结果，可以得出：谷歌、搜搜、百度的MAP值高于搜狗。谷歌、搜搜、百度的前5选精度都要高于前10选精度，而搜狗和人民搜索恰恰相反。以上数据说明：谷歌、搜搜、百度、搜狗对信息类信息查询的综合性能、搜索引擎算法优化度较高，进一步也说明了，用户对这四个搜索引擎的满意度也较高。
（三）事务类信息查询结果的分析。分析事务类信息查询结果，可以得出：谷歌、搜搜和百度的MAP值也在0.4-0.5之间，但是基本持平。进一步说明：谷歌、搜搜、百度、搜狗对事务类查询的精度较其它搜索引擎要高，能够满足大部分用户的事务类信息需求。
三、密钥管理
密钥管理是加密方案中最重要的部分。公钥密码系统（Public Key Infrastructure）在key分发、完整性和不可抵赖性方面都有很好的表现，本文的密钥管理讨论就是基于PKI实现的。
使用PKI后，每个节点都有一对密钥：一个公钥和一个私钥。公钥可以公开发布，私钥只能由通信节点自身保管，使用公钥加密的信息只能用相应的私钥解密。证书发放机构（CA）管理公钥的整个生命周期，负责发放证书和用数字签名绑定公钥。在使用PKI的Ad hoc网络中，CA是整个网络安全的关键，也是网络中最容易受到攻击的节点。为了解决这一问题，我们可以使用一个受信任的节点集来进行密钥管理。
（一）系统模型
我们假设密钥管理服务主要用在同步Ad hoc网中，即所有节点使用一个公共的全局时钟，而且网络层提供了可靠连接。
图1.密钥管理服务模型图
密钥管理服务由n台服务器构成，服务作为一个整体有一对密钥：公钥K和私钥k，公钥K向所有节点开放，私钥k均分为n份，每台服务器一份。所有的服务器 都有一对密钥：公钥 和私钥 ，并且知道所有节点的公钥。其他的节点作为客户端可以发送请求得到各自的公钥或更新自己的公钥。而服务器之间互相知道各自的公钥，就可以建立安全连接。假设n台服务器中在一定时间间隔内最多同时有t（n≥3t+1）台被破坏，这样系统的健壮性和可靠性就有了保障。
（二）门限密码
密钥的分发基于门限密码学，根据Zhou和Hass提出的部分分布式认证方案，客户端密钥的分发由n台服务器共同完成。一旦其中有t台服务器被破坏，最多有t份错误信息生成。通过公钥服务可以检测到这些错误，然后从另外的t+1台服务器的子集中收集密钥信息，一直重复以上过程直到得到正确的密钥。这样的话，尽管提供CA服务的部分服务器被破坏，也不会影响其作为整体提供服务的可靠性。
（三）动態安全
除了门限密码之外，为了应对拓扑变化和移动攻击者，我们还考虑在密钥管理服务中使用份额更新（Share Refreshing）的方法。移动攻击者（Mobile Adversaries）由Yung和Ostrovsky提出，用于描述短期内攻击者破坏一个节点，然后把攻击转向另一个节点。在此模型下，攻击者可能在足够长的时间内破坏所有节点。即使被破坏的服务器会被检测和排除，但是如果有足够长的时间，还是会有超过t台服务器被破坏，产生无效和错误key是不可避免的。
动态方案（Proactive Scheme）是针对移动攻击者提出的解决方案。动态方案允许服务器定期更新其拥有的密钥份额，而服务对应的密钥保持不变。这样移动攻击者就需要在一个更新时间间隔内破坏t台服务器，才能得到密钥。
图2.份额更新模型图
如图2所示：密钥k被分成n份，每台服务器一份。为了计算出服务器新的密钥份额S ，服务器i要计算新的子份额 ， … 。计算出所有的子份额后，把子份额 通过安全通信方式发送到服务器j，服务器j就可计算出新的密钥S 。
四、结语
本文分析了Ad hoc网络面临的安全威胁，提出了针对Ad hoc网络安全需求的一种解决方案，但是还有很多工作等待进一步的探讨，包括方案在实际应用中的表现和对网络性能的影响等。但Ad hoc网络的特点决定了其在军事和特定民用领域具有广阔的发展前景。
参考文献：
[1]Y.Desmedt.Threshold cryptography.European Transactions on Telecommunications,5(4):449–457,July-August 1994.
[2]Z.J.Haas and B.Liang.Ad hoc mobility management using quorum systems.IEEE/ACM Transactions on Networking,1999.
[3]C.E.Perkins and E.M.Royer.Ad hoc on-demand distance vector routing.In IEEE WMCSA’99,New Orleans,LA,February 1999.
[4]L.Zhou and Z.J.Haas.Secure ad hoc networking.IEEE Network,13:24-30,Nov.1999.
[5]Ostrovsky R,Yung M.How to withstand mobile virus attacks[C]//Proc of the 10th ACM Symposium on the Principles in Distributed Computing.New York:ACM Press.1991,51-61
[6]陈林星.移动AD HOC网络--自组织分组无线网络技术[M].电子工业出版社,2006
关键词：Cranfield评价体系；查询样例集合构建；查询信息需求
中图分类号：G354文献标识码：A文章编号：1007-9599 (2011) 15-0000-01
Chinese Search Engine Performance Comparative Studyon Cranfield System
Li Yujun, Bao Yonghan
(Qinghai University,Xining810016,China)
Abstract:Cranfield system through the application-to build a collection of sample query,the query classification of information needs,crawling of search engine results,provided labeling guidelines,the basic computing performance evaluation process,the most commonly used Chinese search engine,Baidu,Google,Sogou,search,people search performance from a quantitative point of view,a more comprehensive evaluation.The result for the user in the selection,use these search engines for reference.
Keywords:Cranfield evaluation system;Query sample collection building;Query information needs
一、Cranfield評价体系
（一）体系的建立。二十世纪五十年代，Cleverdon等人在Cranfield University工作时提出了这样一套评价系统：由查询样例集、正确答案集、评测指标构成的完整评测方案，并从此确立了“评价”在信息检索研究中的核心地位，其核心思想沿用至今。
（二）Cranfield评价体系由三个环节组成。（1）抽取具有代表性的查询词，组成一个规模适当的查询样例集合。（2）针对查询样例集合，从检索系统的语料库中寻找对应的结果，进行标注。（3）将查询词和带有标注信息的语料库输入检索系统，对系统反馈的检索结果，使用预定义好的评价计算公式，用数值化的方法来评价检索系统结果和标注的理想结果的接近程度。
二、查询信息需求的分类
（一）导航类查询。查找某个已知存在的页面/资源，针对特定站点主页的查找。
（二）信息类查询。查找与某个主题相关的权威内容的页面，获取相关权威信息，没有明确查询目标，往往需要不止一个结果。
（三）事务类查询。查找与某个特定需求相关的资源，以进一步交互，没有明确查询目标，但往往一个好的结果就能完成需求。
三、查询样例集合的构建
根据其构建的查询样例集合，抓取常用的五个中文搜索引擎（百度、谷歌、搜狗、搜搜、人民搜索）对这部分查询词的查询结果，每个搜索引擎抓取查询结果的前十位结果，并利用这些结果构建Pooling。
四、搜索引擎性能指标评价的计算
（一）需要计算的性能指标及其公式。
1.首位相关结果倒数（Reciprocal Rank）
2.前N位准确率（Precision@N）。N=10，20：第一页结果中的准确程度。
3.前N位成功率（Success@N）。N=10，20：第一页中是否有满足需求的结果。
4.平均准确率（Average Precision）。N为标准答案的数目；Precision（i）为系统找到第i个答案时的Precision。
（二）计算性能指标值如下表所示：
表1导航类查询的MRR、MAP值
导航 谷歌 搜狗 百度 搜搜 人民搜索
MAP 0.838056 0.797633 0.725333 0.606178 0.111111
MRR 0.955556 0.904444 0.795556 0.807222 0.16
表2信息类查询的MRR、MAP值
事务 百度 谷歌 搜狗 人民搜索 搜搜
MAP 0.611875 0.6115 0.59775 0.492375 0.436375
S@10 0.825 0.9 0.875 0.525 0.9
S@5 0.825 0.9 0.875 0.525 0.775
表3事物类查询的MRR、MAP值
信息 谷歌 搜搜 百度 搜狗 人民搜索
MAP 0.460955 0.425 0.413182 0.320091 0.090909
P@10 0.550545 0.472091 0.447727 0.509909 0.181818
P@5 0.641111 0.547778 0.525556 0.295556 0.111111
五、分析
（一）导航类信息查询结果的分析。分析导航类信息查询结果，可以得出：五个常用中文搜索引擎，平均首现正确答案排序倒数（MRR）值都要比平均准确率（AMP）高，但是这几个搜索引擎在平均准确率（AP）、首先正确答案倒排序（RR）方面还是有差距，其中谷歌、搜狗在导航类信息查询方面准确率要比百度、搜搜高。
（二）信息类信息查询结果的分析。分析信息类信息查询结果，可以得出：谷歌、搜搜、百度的MAP值高于搜狗。谷歌、搜搜、百度的前5选精度都要高于前10选精度，而搜狗和人民搜索恰恰相反。以上数据说明：谷歌、搜搜、百度、搜狗对信息类信息查询的综合性能、搜索引擎算法优化度较高，进一步也说明了，用户对这四个搜索引擎的满意度也较高。
（三）事务类信息查询结果的分析。分析事务类信息查询结果，可以得出：谷歌、搜搜和百度的MAP值也在0.4-0.5之间，但是基本持平。进一步说明：谷歌、搜搜、百度、搜狗对事务类查询的精度较其它搜索引擎要高，能够满足大部分用户的事务类信息需求。
三、密钥管理
密钥管理是加密方案中最重要的部分。公钥密码系统（Public Key Infrastructure）在key分发、完整性和不可抵赖性方面都有很好的表现，本文的密钥管理讨论就是基于PKI实现的。
使用PKI后，每个节点都有一对密钥：一个公钥和一个私钥。公钥可以公开发布，私钥只能由通信节点自身保管，使用公钥加密的信息只能用相应的私钥解密。证书发放机构（CA）管理公钥的整个生命周期，负责发放证书和用数字签名绑定公钥。在使用PKI的Ad hoc网络中，CA是整个网络安全的关键，也是网络中最容易受到攻击的节点。为了解决这一问题，我们可以使用一个受信任的节点集来进行密钥管理。
（一）系统模型
我们假设密钥管理服务主要用在同步Ad hoc网中，即所有节点使用一个公共的全局时钟，而且网络层提供了可靠连接。
图1.密钥管理服务模型图
密钥管理服务由n台服务器构成，服务作为一个整体有一对密钥：公钥K和私钥k，公钥K向所有节点开放，私钥k均分为n份，每台服务器一份。所有的服务器 都有一对密钥：公钥 和私钥 ，并且知道所有节点的公钥。其他的节点作为客户端可以发送请求得到各自的公钥或更新自己的公钥。而服务器之间互相知道各自的公钥，就可以建立安全连接。假设n台服务器中在一定时间间隔内最多同时有t（n≥3t+1）台被破坏，这样系统的健壮性和可靠性就有了保障。
（二）门限密码
密钥的分发基于门限密码学，根据Zhou和Hass提出的部分分布式认证方案，客户端密钥的分发由n台服务器共同完成。一旦其中有t台服务器被破坏，最多有t份错误信息生成。通过公钥服务可以检测到这些错误，然后从另外的t+1台服务器的子集中收集密钥信息，一直重复以上过程直到得到正确的密钥。这样的话，尽管提供CA服务的部分服务器被破坏，也不会影响其作为整体提供服务的可靠性。
（三）动態安全
除了门限密码之外，为了应对拓扑变化和移动攻击者，我们还考虑在密钥管理服务中使用份额更新（Share Refreshing）的方法。移动攻击者（Mobile Adversaries）由Yung和Ostrovsky提出，用于描述短期内攻击者破坏一个节点，然后把攻击转向另一个节点。在此模型下，攻击者可能在足够长的时间内破坏所有节点。即使被破坏的服务器会被检测和排除，但是如果有足够长的时间，还是会有超过t台服务器被破坏，产生无效和错误key是不可避免的。
动态方案（Proactive Scheme）是针对移动攻击者提出的解决方案。动态方案允许服务器定期更新其拥有的密钥份额，而服务对应的密钥保持不变。这样移动攻击者就需要在一个更新时间间隔内破坏t台服务器，才能得到密钥。
图2.份额更新模型图
如图2所示：密钥k被分成n份，每台服务器一份。为了计算出服务器新的密钥份额S ，服务器i要计算新的子份额 ， … 。计算出所有的子份额后，把子份额 通过安全通信方式发送到服务器j，服务器j就可计算出新的密钥S 。
四、结语
本文分析了Ad hoc网络面临的安全威胁，提出了针对Ad hoc网络安全需求的一种解决方案，但是还有很多工作等待进一步的探讨，包括方案在实际应用中的表现和对网络性能的影响等。但Ad hoc网络的特点决定了其在军事和特定民用领域具有广阔的发展前景。
参考文献：
[1]Y.Desmedt.Threshold cryptography.European Transactions on Telecommunications,5(4):449–457,July-August 1994.
[2]Z.J.Haas and B.Liang.Ad hoc mobility management using quorum systems.IEEE/ACM Transactions on Networking,1999.
[3]C.E.Perkins and E.M.Royer.Ad hoc on-demand distance vector routing.In IEEE WMCSA’99,New Orleans,LA,February 1999.
[4]L.Zhou and Z.J.Haas.Secure ad hoc networking.IEEE Network,13:24-30,Nov.1999.
[5]Ostrovsky R,Yung M.How to withstand mobile virus attacks[C]//Proc of the 10th ACM Symposium on the Principles in Distributed Computing.New York:ACM Press.1991,51-61
[6]陈林星.移动AD HOC网络--自组织分组无线网络技术[M].电子工业出版社,2006