论文部分内容阅读
为了解决传统集中式搜索引擎所面临的性能瓶颈,研究人员提出将搜索引擎构建于P2P网络之上,通过P2P网络将分散的众多节点联系起来,整合它们的运算能力和存储资源,从而以较低的硬件代价形成巨大的服务性能。P2P搜索引擎的特点是每个节点都是一个独立文档数据库,各节点处于对等地位,不存在中央节点,相互协作地响应查询请求。目前P2P搜索引擎的实现依赖一个假设：所有节点是合作性的,即所有节点能够按照统一协议返回资源描述、参与维护索引、转发或执行查询等等。通常情况下,这种合作性机制是由每个节点安装一个客户端工具来实现的。然而,Web中有许多站点包含大量高质量的文档,且能够提供站内检索服务,例如新闻网站,论坛,电子图书馆。这些资源节点属于不同的商业公司或机构,难以要求这类节点能够合作地遵照统一协议参与系统的运行。在文献中,这类节点常被称为非合作性节点,包含非合作性节点的运行环境被称为非合作性环境。由于Web中非合作节点数量巨大,整合这类资源将极大地提高搜索引擎的查询质量和效果。本论文提出一个非合作性环境下的P2P搜索引擎框架,并基于这个框架,深入研究了P2P搜索引擎的关键问题,包括资源描述获取方法,资源选择算法,结果合并算法,索引目录维护机制等,取得了若干研究成果。具体来说,本文的研究成果包括：(1)本文提出一种非合作性环境下的P2P搜索引擎架构,称为PISA (P2P Information Search with unccoperAtive Peers),实现融合非合作性节点。本文给出PISA的网络拓扑结构、索引目录的数据结构及构建过程、PISA的查询过程。(2)本文提出一种非合作性环境下的启发式查询采样方法HQBS (Heuristic Query-based Sampling),从非合作性节点中获取资源描述信息。传统的方法是对非合作性节点发起一系列查询,并下载若干结果文档。当采样文档达到一定数量时,停止采样文档。这种方法在P2P环境中容易造成对大节点采样不足和对小节点过度采样。针对这些问题,HQBS方法采用启发式判定采样终止的条件,使得采样文档的数量能够依节点大小而动态调整,尽可能对每个节点都获取高质量的资源描述信息,且不浪费采样资源。(3)本文提出一种非合作性环境下的兼顾重叠和相关度的资源选择算法OPS (Overlap-aware Peer Selection)。与传统的资源选择算法忽略资源间重叠不同,OPS用于在非合作性环境下,通过对查询结果提取覆盖统计信息,近似地估算出节点资源间的重叠度,实现兼顾重叠和相关度的资源选择算法,提高查询的效率。随着查询的进行,OPS提取的覆盖统计信息越来越全面,OPS能够有效地提高新颖结果的总量。(4)本文提出非合作环境下的两个结果合并算法RISE/RISE+(Result mergIng in Score-absent Environments),将非合作性节点返回的结果列表合并成单个有序的结果列表。传统的方法依赖各资源节点提供的本地相关度分值(local relevance score),通过一系列的映射规范化等操作,计算得到全局相关度分数。然而,在非合作性环境下,节点在返回的结果时,可能并不附带本地相关度分值。本文提出两种结果合并算法RISE/RISE+,能够在非合作性节点不返回相关度分值的情况下,实现高效的结果合并。实验结果表明,这两种算法的结果合并准确性略高于传统方法。(5)本文提出一种非合作性环境下的索引目录更新机制CSU,使得索引目录在节点颠簸(churn)和内容演化时保持更新。传张的索引目录更新机制是一种基于生命周期(Time-To-Live, TTL)定时更新。各节点在每隔TTL时间更新索引目录一次。这种方法在各节点颠簸,内容演化速率相差很大时,系统难以选择一个合适的TTL值。如果TTL过大,造成索引目录更新不及时,影响资源选择的准确度；反之,会造成索引目录维护开销过大,影响系统的性能。针对这些问题,本文提出一种更为节约高效的非合作性环境下的索引目录更新机制CSU。CSU基于受控更新原则充分地减小更新索引目录的次数,基于选择性更新原则充分地减小每次更新索引目录的Posts数量,运用基于划分消息的更新方法,减小更新消息在网络的传输开销。