英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料

使用自组织语义覆盖网络的点对点信息检索

摘 要：

在Peer-to-Peer（P2P）系统中，基于内容的全文本搜索是一个具有挑战性的问题。传统方法要么集中化，要么使用泛洪来确保返回结果的准确性。在本文中，我们介绍了pSearch，这是一种分散式的非洪流P2P信息检索系统。pSearch根据潜在语义索引（LSI）生成的文档语义，通过P2P网络分发文档索引。由于语义相关文档的索引很可能位于网络中，因此减少了给定查询的搜索成本（就搜索的不同节点和传输的数据而言）。我们还介绍了一些技术，这些技术可帮助在节点之间更均匀地分配索引，并使用适当的索引分布以及使用索引样本和最近处理的查询来指导搜索，从而进一步减少所访问节点的数量。实验表明，通过仅搜索少量节点，pSearch可以获得与集中式信息检索系统相当的性能。对于具有128,000个节点和528,543个文档（来自新闻，杂志等）的系统，pSearch仅搜索19个节点，并且在搜索过程中仅发送95.5KB数据，而pSearch和LSI返回的前15个文档的交点为91.7％。

类别和主题描述

C.2.4 [计算机通信网络]：分布式系统

概述

算法，管理，性能，设计，实验

关键字

点对点系统，信息检索，覆盖网络

1. 介绍

根据最近的一份报告[17]，全世界93％的信息都是数字形式的。每年添加的唯一数据超过1 EB（或10¹⁸字节），并且估计将呈指数增长。这种趋势要求同样可伸缩的基础架构能够索引和搜索丰富的内容，例如HTML，纯文本，音乐和图像文件。另一方面，点对点（P2P）系统因其可伸缩性，容错性和自组织性而迅速普及，这为低成本构建大型信息检索（IR）系统带来了希望[15]。

诸如Google之类的搜索引擎似乎可以针对Web内容进行扩展，但是公众对于这些系统的实际运行方式知之甚少。在本文中，我们描述了基于P2P技术构建自组织搜索引擎的技术，该技术自然地继承了P2P的许多优良特性-可伸缩性，容错性，低维护成本等。我们系统的基本原理适用于管理良好稳定的环境（例如，

类似Google的搜索引擎，数据中心和公司）以及更动态的P2P环境。

尽管近年来已经提出了许多P2P搜索技术[16、3、20、5、22、10]，但很少有例外[6]，但大多数基于简单的关键字匹配，却忽略了高级相关性排名IR社区通过数十年的完善和评估而设计的算法[18]。没有有效的排名，由流行词组成的查询可能会返回用户无法处理的大量文档。

我们在本文中重点研究扩展经典IR算法以在P2P环境中工作的可行性。一些IR技术（例如Google的PageRank）利用超链接来标识重要的网页。但是，这种交叉引用信息并不存在于许多数字内容中。因此，我们将从最流行和研究最深入的统计IR算法，向量空间模型（VSM）和潜在语义索引（LSI）[1，7]开始，它们不依赖于交叉引用信息。VSM和LSI将文档和查询表示为笛卡尔空间中的向量，并以查询和文档之间的向量表示之间的角度的余弦值来衡量查询和文档之间的相似性。根据[28、18、13]，VSM和LSI的变体已被主要搜索引擎（例如Excite）采用。在实践中，各种IR技术相结合以构建实用的搜索引擎。关于其他技术（例如PageRank）如何补充我们的方法的研究是未来工作的主题。

使现有P2P系统中的搜索变得困难的根本问题是，就语义而言，文档是随机分布的。给定一个查询，系统要么必须搜索大量节点，要么用户冒着丢失相关文档的高风险。为了解决这个问题，我们引入了语义覆盖的概念，这是一个逻辑网络，其中内容围绕它们的语义进行组织，以使距离（例如路由跳数）网络中两个文档之间的跃点与其语义上的差异成正比。文档语义是使用LSI产生的。

查询的搜索区域

语义空间 文献 询问

图1：在语义空间中搜索

内容可寻址网络（CAN）[19]在笛卡尔空间上提供分布式哈希表（DHT）抽象。它们允许有效存储和检索（键，对象）对。对象键是笛卡尔空间中的一个点。我们使用CAN通过将文档的语义向量（由LSI生成）作为关键字来创建语义叠加，以将文档索引存储在CAN中。

图1说明了语义覆盖如何使搜索受益。当LSI生成文档的语义时，每个文档都被定位为（语义）笛卡尔空间中的一个点。语义空间中接近的文档具有相似的内容，例如文档A和B。每个查询也可以位于此语义空间中。要查找与查询相关的文档，我们只需要将查询与以查询为中心的小区域内的文档进行比较，因为该区域以外的文档的相关性相对较低。这样，查询的搜索空间为有效限制并保持准确性。

语义覆盖的基本思想很简单，涉及将覆盖映射到CAN中的物理节点。但是，它受许多因素的影响而变得复杂。（1）我们将CAN的维数设置为与LSI语义空间的维数相等，通常在50到350之间。但是，CAN的“实际”维数要低得多，因为没有足够的节点可划分高维CAN的所有尺寸。沿着那些未分区的维度，搜索空间不会减少。（2）语义向量在语义空间中分布不均匀。从语义空间到CAN的直接映射将导致索引在节点之间的不平衡分配。（3）由于一个被称为维数诅咒的问题，已经表明限制高维空间中的搜索区域是困难的[26]。

我们通过利用语义空间和交易准确性，以提高效率和/或存储必要时的开销。利用语义向量的低维元素的更高重要性，我们的滚动索引方案通过旋转语义向量在更多维度上划分语义空间。我们的内容感知节点引导程序有助于在各个节点之间更均匀地分配索引。使用索引样本和最近处理的查询来指导搜索，我们的内容定向搜索算法大大缩小了高维语义空间中的搜索区域。

我们已经建立了一个名为pSearch [24]的原型P2P IR系统。pSearch的工作方式是将文档表示为矢量，并围绕它们的矢量表示组织网络中的内容。尽管我们的实验着重于全文搜索，但该方法也可以应用于搜索音乐和图像文件[9]。我们的评估表明，pSearch通过仅搜索少量节点即可达到与集中式IR系统相当的性能。对于具有128,000个节点和528,543个文档的系统（来自新闻，杂志等），pSearch仅搜索19个节点，并且在搜索过程中仅传输95.5KB数据，而pSearch和LSI返回的前15个文档的交点为91.7％。尽管我们的原型实现不包括近年来提出的一些IR技术，但我们的评估（在7.4节中）表明pSearch具有随着高级IR技术的未来发展而改善的巨大潜力。

在本文的其余部分安排如下。第2节提供有关IR和CAN的背景信息。第3部分概述了pSearch，并重点介绍了主要挑战。第4至6节介绍了我们针对这些挑战的解决方案。第7节介绍了pSearch的原型以及我们的实验结果。第8节讨论了相关工作。第9节总结了本文。

2. 背景

在pSearch中，我们使用对VSM和LSI [1，7]的扩展来生成语义空间，并使用CAN [19]将节点组织为覆盖。在本节中，我们将概述这些概念，以便为描述我们的算法奠定基础。

2.1 向量空间模型（VSM）

VSM将文档和查询表示为术语向量。向量的每个元素对应于文档或查询中术语的重要性。元素的权重通常是使用统计术语频率*反向文档频率 * IDF）方案[1]计算的。其直觉是两个因素决定了术语在文档中的重要性-术语在文档中的出现频率和在其他文档中的出现频率。如果某个术语以较高的频率出现在文档中，则很有可能会使用该术语将文档与其他文档区分开。但是，如果该术语也出现在许多其他文档中，则其重要性应受到惩罚。

在检索操作中，根据文档向量和查询向量之间的相似度对文档进行排名，并返回相似度最高的那些文档。相似性的常用度量是向量之间的角度的余弦值。一些VSM实现将术语向量X标准化为单位长度（| X | = 1），以补偿文档中的差异

长度。形式上，给定的项向量X =（x1，x2，...，xl）并且Y =（y1，y2，...，yl），它们之间的相似性在公式1中定义，其中cos（X，Y）表示在以下位置的角度的余弦值，补间向量X和Y。注意| X |= 1和| Y |= 1，因为他们已经标准化。因此，相似度只是两个向量的内积。

2.2 潜在语义索引（LSI）

诸如VSM之类的文字匹配方案在文档中存在同义词和噪音。LSI通过使用统计得出的概念索引而不是检索术语来克服这些问题。它通过将奇异值分解（SVD）投影到语义子空间中，使用奇异值分解（SVD）[1]将高维术语向量（从VSM计算）转换为低维语义向量。语义向量的每个元素对应于文档或查询中抽象概念的重要性。与VSM中一样，对语义向量进行归一化，并使用等式1测量其相似性。

区域坐标

对象键

图二：二维CAN

令d表示语料库中文档的数量，而t表示词汇表中术语的数量。VSM代表该语料库，如x d矩阵A所示，其项aij表示在文件j中的i项。假设A的等级为r。SVD分解A进入三个矩阵的乘积A = USigma;V^T，其中U =（u₁，...，u_r）在ttimes;r矩阵，Sigma;= diag（sigma;₁，...，sigma;_r）是rtimes; r对角矩阵，并且V =（v₁， ...，v_r）是dtimes;r矩阵。sigma;_i是A的奇异值，sigma;₁ge;sigma;₂ge;...ge; sigma;_r 。

LSI通过忽略除l个最大奇异值之外的所有奇异值，用较低等级l的矩阵A₁来近似等级r的矩阵A。设U₁ ＝（u₁，...，u_l），sum;_l ＝ diag（sigma;₁，...，sigma;_l），并且V₁ ＝（v₁，...，v_l）。

V_lSigma;₁的行是语料库中文档的语义向量。给定U_l，V_l和Sigma;_l，可以通过折叠原始查询，术语或原始不在A中的文档的语义矢量进入语义子空间[1]。

通过为A_l选择适当的l，可以保留语料库的重要结构，同时消除了单词用法中的噪声或变异性（小的sigma;i）。以前对LSI的研究建议将l设置为50到350之间的值，并报告说其精度比VSM提高了30％[7]。此外，LSI还可以通过学习共同出现的单词用法来收集语义相关的文档，即使它们不共享术语也是如此。例如，有关汽车的搜索可能会在文本中返回实际使用汽车的相关文档。

Raghavan [18]认为昂贵的SVD组件是其中之一LSI的主要可扩展性障碍。近年来，已经提出了许多有效的LSI变体，例如概念索引[12]。SVD的并行实现也使这个问题更容易解决[14]。作为这些进步的证据，据报道Excite使用LSI的变体对Web进行索引[28]。

总之，LSI将文档和查询表示为（语义）笛卡尔空间中的向量（点）。查询和文档之间的相似度以其向量表示之间的角度的余弦表示。给定一个查询作为笛卡尔空间中的一个点，查找最相关文档的问题被简化为定位最靠近查询点的文档点。因此，pSearch中的中心问题是将语义空间映射到网络中的节点，并以分散的方式进行有效的最近邻居搜索。

2.3 内容可寻址网络（CAN）

最近的覆盖网络，例如CAN，Chord，Pastry和Tapestry，提供了无需管理且容错的分布式哈希表（DHT），该表将“键”映射为“值”。CAN将三维笛卡尔空间划分为区域，并将每个区域分配给一个节点。对象键是笛卡尔空间中的一个点，并且对象存储在其区域包含该点的节点上。定位对象简化为路由到承载该对象的节点。路由转换为在笛卡尔空间中从一个区域穿越到另一个区域。节点联接对应于在笛卡尔空间中随机选择一个点，路由到包含该点的区域，并用其当前所有者分割该区域。

图2中显示了一个CAN示例。覆盖中有五个节点AE。每个节点在笛卡尔空间中拥有一个区域。最初，C拥有右上角的整个区域。当D加入时，C拥有的区域将分割，并将该区域的一部分分配给D。当D想要检索具有键（0.4，0.1）的对象时，它将请求发送给E，并且E将请求转发给A。

图三：pSearch系统概述

3. psearch系统概述

在pSe

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[234084]，资料为PDF文档或Word文档，PDF文档可免费转换为Word