一种新型的P2P信息检索系统性能评估方法
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种新型的P2P信息检索系统性能评估方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：对等计算作为学术界和工业界的关注焦点，其在实践中的重要应用主要是信息资源共享。但随着对等计算信息检索系统的广泛应用，如何对其进行客观公正的评价，确定有效、实用的评估标准已迫在眉睫。于是，在以上趋势背景下，文章经过详细研究分析对等计算的信息共享系统后，指出目前P2P信息检索系统面临的实现机制和关键技术问题。之后，经过认真总结和分析，勾勒出评价系统性能的四项指标体系，提出系统性能评估的CTL定律，这对P2P信息检索系统的评价和开发将具有实际指导意义。同时，在此基础上确定今后对等计算信息检索系统研究工作的重点――关键技术及其相应策略。
关键词：信息检索；对等计算；性能评估
中图法分类号：TP311文献标识码：A 文章编号：1009-3044(2007)16-30927-02
A Novel Approach to Evaluate Information Retrieval Systems Based on P2P
HONG Dao-cheng1,2
(1.Shanghai Key Laboratory of Intelligent Information Processing, Fudan University, Shanghai 200433, China;2.Department of Computer Science & Engineering, Fudan University, Shanghai 200433, China)
Abstract:As a hot spot in the computer research and industrial fields, P2P has been mainly applied to information sharing. With P2P-based information retrieval systems applied frequently, the coming issues are how to evaluate the system objectively and fairly, and how to plot the common criteria for system performance evaluation. After having conducted a comprehensive study on P2P-based systems, we point out the implementation mechanism and key techniques in this area. We propose a novel approach to evaluate information retrieval systems based on P2P: Constraint Triangle Law, which will guide the development and evaluation of P2P-based information retrieval systems in the future. Furthermore we fix the key-point research on P2P-based systems: key techniques and strategies.
Key words:Information Retrieval; P2P; Performance Evaluation
1 引言
从2000年中期新一轮对等计算（简称P2P）研究热兴起开始，P2P已被学者认为是重构基于Internet应用的关键技术[1]，是影响Internet未来的四项科技之一[2]，并由此产生了多个著名的对等计算信息共享系统[3]，如Gnutella、Chord等。著名系统CAN的设计者之一Shenker，曾将对等计算系统的主要应用归纳为“以数据为中心的网络”（data-centric networks）[4]。这反映了现阶段对等计算的研究主要围绕数据信息共享的事实。同时，数据信息共享本身是其他基于P2P应用类型的基础，是对等计算应用研究的焦点。
目前的P2P信息共享系统，依据系统拓扑结构的关系可以分为：中心化拓扑（Centralized Topology），全分布式非结构化拓扑（Decentralized Unstructured Topology），全分布式结构化拓扑（Decentralized Structured Topology），半分布式拓扑（Partially Decentralized Topology）。然而，现有P2P系统研究的关键集中在信息检索方面。因此，对相关P2P信息检索系统进行客观公正的评价，确定有效、实用的评估标准已是大势所趋。本文的研究是在以上背景下展开。
2 系统分析
综合分析现有的基于对等计算的信息检索，可以发现各种类型结构系统特点各异，但是却存在共同的局限性，并严重影响着查询效率和效果，导致实际应用结果已与构建基于P2P的信息检索系统的初衷大相径庭。限于实际应用和技术的约束，目前基于对等计算的检索系统存在的问题有：（1）由于数据共享粒度太大，大多数系统仅支持文件层的共享，即以文件为共享单位，导致系统查询、路由的精确度下降；（2）由于系统语义检索的水平较低，包括仅支持弱语义甚至缺乏语义的检索、查询，忽略了自然语言理解，导致检索结果的准确度严重降低；（3）前两个影响因素和现有系统结构的特点都直接导致信息检索的效率低下，造成系统资源浪费。文献[5]对此有详细论述。
仔细分析系统存在的以上问题，挖掘深层次原因，可以发现以上系统均没有充分发挥基于P2P的信息检索技术的特长，包括：系统的协议和检索算法；系统对文件共享粒度、语义检索的支持程度。涉及的具体技术有：系统结构的设计；系统信息资源的管理；系统信息资源的定位和查询路由；系统检索结果的优化和排序；安全和隐私；等等。
通过以上分析可以发现，对等计算系统中信息检索实现的机制，可以归结为三个阶段：信息资源的放置管理、信息资源的定位查找、查询结果的优化和排序。在对等计算信息检索系统中，为保证检索效果和效率，在一定体系结构的基础上，首先要进行资源的放置管理，要合理有效地设计资源的分配和存储机制，为查找资源和优化查询结果提供较好的方便。其次，在真正进行信息检索时，资源查找就成为关键步骤。在合理安排、管理信息数据的基础上，设计出搜索高效的查找和路由算法，已成为问题的核心。最后，由于系统语义理解的有限性，检索结果势必会产生一定的偏差。为了提供高质量的信息资源，减轻用户浏览压力，需要对检索结果进行必要的优化和排序。研究显示，系统实现过程中的评价指标、标准已成为高质量检索系统实现的基础和关键。
3 系统性能评估指标
3.1 系统性能评估定律
基于对等计算的信息检索实质是在预定体系结构的基础上，根据信息查询需求的描述，定位信息资源所在节点，并按照一定策略对这些节点的顺序进行优化和排列。考察系统的性能，衡量评估标准应包括：查询时间（Query Time，简称QT）、查全率（Recall，简称R）、网络负载（Network Load，简称NL）和查准率（Precision，简称P）。在对等计算系统中：（1）假定消息从一个节点传递至其他任意一个节点的时间都相等并规定为单位时间，那么查询时间就可以用消息传递的路径长度来表示，并以此来衡量系统的时间复杂度；（2）查全率要求尽可能多地路由相关节点，保证客观存在的目标信息没有遗漏。节点的路由机制要求计算查询空间，即系统的空间复杂度，在此可以将节点路由存储任一个节点信息定义为一个单位空间；（3）系统查询中，消息的路由传递会增加网络的流量，即网络负载。为有效衡量具体增加的负载程度，在此定义节点的一个消息路由到下一个节点就是一个单位的网络负载；（4）由于系统的动态变化特点，查准率不仅仅指与查询要求匹配，而且要求提供正确、有效和可用的资源链接。
系统性能的四项评估指标是统一整体，指标之间相互依存，相互制约，其关系可以表示成如图1所示的相互牵制的三角图形（Constraint Triangle，简称CT）。
图1系统性能评估指标间的制约关系
在如图1所示的牵制三角形中，查询时间（QT）、查全率（R）、网络负载（NL）位于图形的三个角，查准率（P）位于图形的中央，因为它是用户关心的焦点，是系统性能的重要制约和评价因素。四项评估指标相互擎制，相互制衡，任何一个指标发生变动，都将直接影响其他指标。例如，提高系统的检索正确率将导致时间复杂度的增长，加重网络负载，增加空间复杂度。因此，系统性能评估是四项指标的平衡，为了提高某一项性能指标，必然以牺牲其他的指标为代价，相反也可以理解为通过降低系统的其他性能指标，来提高或者获得某一性能的高效。以上系统性能评估规律总结为Constraint Triangle Law （简称CTL）[6]。
3.2 系统性能评估定律的作用
CTL定律对基于P2P信息检索系统的评价和开发具有实际指导意义。不同的P2P系统对性能提高的侧重点不同，因此对系统的评价就不应该局限在某一点，要统筹兼顾，根据不同的实际应用，做出科学评价。同时，在设计开发P2P信息检索系统时，要根据实际应用需要，制定相应的性能策略，通过相对降低某些性能指标，来达到某一项指标的较优。
通过以上论述，在系统性能评估CTL定律的基础上，我们将在以后的工作中探讨对等计算检索系统的四个主要技术问题：体系结构、资源放置管理机制、资源查找定位机制、检索结果的优化和排序，同时论述相应的问题策略。
4 结束语
通过详细研究分析对等计算的信息共享系统，指出目前基于对等计算的信息检索面临的实现机制和具体技术措施问题。在认真总结和分析的基础上，给出评价系统性能的四项指标体系，提出系统性能评估的CTL定律。在此基础上确定即将开发的P2P信息检索系统的准则，和下一步对等计算信息检索系统研究重点――关键技术问题及其相应策略。
参考文献：
[1]S.Gribble, A.Halevy, Z.Ives, M.Rodrig, and D.Suciu. What can database do for peer-to-peer[A]. In WebDB, 2001.
[2]L. Gong. Peer-to-Peer networks in action. IEEE Internet Computing. 2002, 6(1):37~39.
[3]S. Saroiu, P. K. Gummadi, and S. D. Gribble. A measurement study of peer-to-peer file sharing systems. In Proceedings of the Conference on Multimedia Computing and Networking 2002 (MMCN’2002).
[4]Ryan Huebsch, Joseph M. Hellerstein, Nick Lanham, Boon Thau Loo, Scott Shenker, Ion Stoica. Querying the Internet with PIER. VLDB 2003: 321-332.
[5]黄维雄，等.一种基于自配置策略的新型Peer to Peer平台系统[J]. 软件学报,2003,Vol.14 (2).
[6]洪道诚.基于对等计算的信息检索研究[D].复旦大学图书馆,2007.