英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
使用自组织语义覆盖网络进行点对点信息检索
lowast;
春秋堂
计算机科学系大学
Rochester Rochester，
NY 14627-0226
许志辰
HP Laboratories 1501 Page Mill Rd.
Palo Alto, CA 94304-1126
Sandhya Dwarkadas
计算机科学大学系 Rochester Rochester，
NY 14627-0226
摘要
基于内容的全文搜索在点对点（P2P）系统中是一个具有挑战 性的问题。传统方法要么集中，要么使用洪水来确保返回结 果的准确性。在本文中，我们提出了一个分散的非泛洪P2P信 息检索系统pSearch。pSearch基于潜在语义索引（LSI）生成 的文档语义，通过P2P网络分发文档索引。由此，减少了针对 给定查询的搜索成本（针对搜索的不同节点和发送的数据）， 因为语义相关文档的索引可能共同位于网络中。我们还描述 了有助于在节点之间更均匀地分布索引的技术，并进一步减 少使用适当的索引分布访问的节点数量，以及使用索引样本 和最近处理的查询来指导搜索。实验表明，通过仅搜索少量 节点，pSearch可以实现与集中式信息检索系统相当的性能。 对于具有128,000个节点和528,543个文档（来自新闻，杂志 等）的系统，pSearch在搜索期间仅搜索19个节点并仅传输95.5KB数据，而pSearch和LSI返回的前15个文档具有91.7％ 的交叉点。
类别和主题描述符
C.2.4 [计算机通信网络]：分布式系统
一般条款
算法，管理，性能，设计，实验
关键词
点对点系统，信息检索，覆盖网络
介绍
根据最近的一份报告[17]，全球93％的信息都是数字形式。每年增加的独特数据
lowast;这项工作是在2002年春强在惠普实验室实习期间开始的，并于2003年在罗彻斯特大学完成。
允许将个人或教室使用的全部或部分作品的数字或硬拷贝免费授予， 前提是副本不是为了利润或商业利益而制作或分发的，并且副本承 担此通知并在第一页上完整引用。要以其他方式进行复制，重新发 布，在服务器上发布或重新分发到列表，需要事先获得特定许可和/ 或费用。
SIGCOMM#39;03，2003年8月25日至29日，德国卡尔斯鲁厄。版权 所有2003 ACM 1-58113-735-4 / 03/0008 ... $ 5.00。
超过一个exabyte（或1018 字节），估计会成倍增长。这种趋势需要能够同等扩展的基础架构，能够索引和搜索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）利用超链接来识别重要 的Web页面。然而，这种交叉引用信息在许多数字内容中不存在。因此，我们将从最流行且经过充分研究的统计IR算法，向量空 间模型（VSM）和潜在语义索引（LSI）[1,7]开始，它们不依赖 于交叉引用信息。VSM和LSI将文档和查询表示为笛卡尔空间中的向量，并将查询和文档之间的相似性测量为它们的向量表示 之间的角度的余弦。根据[28,18,13]，VSM和LSI的变体已被主要 搜索引擎如Excite采用。在实践中，组合各种IR技术以构建实用的搜索引擎。关于其他技术（例如，PageRank）如何补充我 们的方法的研究是未来工作的主题。
使搜索在现有P2P系统中困难的基本问题是，就语义而言， 文档是随机分布的。给定查询，系统要么必须搜索大量节点， 要么用户存在丢失相关文档的高风险。为了解决这个问题， 我们引入了语义覆盖的概念，这是一种逻辑网络，其中内容 围绕它们的语义进行组织，使得距离（例如，路由 -
搜索查询区域
A
B
语义空间
文献
询问
图1：在语义空间中搜索。
网络中两个文档之间的跳数与它们在语义上的不同程度成正比。文档语义是使用LSI生成的。
内容可寻址网络（CAN）[19]在笛卡尔空间上提供分布式哈希表（DHT）抽象。它们允许有效存储和检索（密钥，对象） 对。对象键是笛卡尔空间中的一个点。我们使用CAN通过使用文档的语义向量（由LSI生成）作为在CAN中存储文档索引的
关键字来创建语义覆盖。图1说明了语义叠加如何使搜索受益。当LSI生成文档的语义时，每个文档都被定位为（语义）笛卡 尔空间中的一个点。在语义空间中关闭的文档具有类似的内 容，例如文档A和B.每个查询也可以位于该语义空间中。要查 找与查询相关的文档，我们只需要将查询与以查询为中心的 小区域内的文档进行比较，因为区域外文档的相关性相对较
低。通过这样做，查询的搜索空间是有效地限制并保持准确性。
语义覆盖的基本思想很简单，涉及到覆盖到CAN中物理节点 的映射。然而，它因许多因素而变得复杂。（1）我们将CAN 的维度设置为等于LSI语义空间的维度，通常在50到350之间。然而，CAN的“实际”维度要低得多，因为没有足够的节点来 划分高维CAN的所有尺寸。沿着这些未分区的维度，搜索空间 不会减少。（2）语义向量不均匀地分布在语义空间中。从语 义空间到CAN的直接映射将导致跨节点的索引的不均衡分布。
（3）由于被称为维数灾难的问题，已经表明在高维空间中限
制搜索区域是困难的[26]。
我们通过利用的属性来解决这些问题
新闻，杂志等），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节总结了论文。
背景
在pSearch中，我们使用VSM和LSI [1,7]的扩展来生成语义空间，并使用CAN [19]将节点组织成叠加层。在本节中，我们将概述这些概念，以便为我们的算法描述设置阶段。
向量空间模型（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，因为它们已经标准化。因此，相似性
仅仅是两个向量的内积。
效率和/或存储的语义空间和交易准确性
必要时开销。利用更高的重要性
对于语义向量的低维元素，我们的滚动索引方案通过旋转语
义向量来沿着更多维度划分语义空间。我们的内容感知节点引导有助于在节点之间更均匀地分布索引。使用索引样本和最近处理的查询来指导搜索，我们的内容导向搜索算法大大减少了高维语义空间中的搜索区域。
我们已经构建了一个名为pSearch的原型P2P IR系统[24]。pSearch的工作原理是将文档表示为向量，并围绕其向量表示在网络中组织内容。虽然我们的实验专注于全文搜索，但这种方法也可以应用于搜索音乐和图像文件[9]。我们的评估表明，通过仅搜索少量节点，pSearch可以实现与集中式IR系统相当的性能。对于具有128,000个节点和528,543个文档的系统（来自
潜在语义索引（LSI）
诸如VSM之类的文字匹配方案受到文档中的同义词和噪声的影响。LSI通过使用统计推导的概念指数而不是检索术语来克服这些问题。它使用奇异值分解（SVD）[1]将高维项矢量
（从VSM计算）转换为低维语义向量，方法是将前者投影到语义子空间中。语义向量的每个元素对应于文档或查询中抽象概念的重要性。与在VSM中一样，语义向量被归一化并且使用等式1来测量它们的相似性。
设d表示语料库中的文档数，t表示词汇表中的术语数。VSM 将此语料库表示为times;d矩阵A，其条目aij表示重要性
区域坐标
B
0-0.5
C
D
0.5-1
0.5-0.75 0.75-1
0.5-1 0.5-1
A
0-0.5
0.4
E
0.5-1
0-0.5
0.1
0-0.5
0
1
对象键
1
文档索引查询
A
pSearch引擎
F
G
B
图2：二维CAN。
在文件j中的术语i。假设A的等级是r。SVD将A分解为三个 矩阵的乘积，A =USigma;V t ，其中U =（u1，...，ur）是一个ttimes;r 矩阵，Sigma;= diag（ sigma;1，...，sigma;r）是一个rtimes;r对角线矩阵，并且V =（v1，...，vr）是一个dtimes;r矩阵。sigma;i是A的奇异值，sigma;1ge;sigma;2ge;. ..ge;sigma;r。
C D
E
图3：pSearch系统概述。
示例CAN如图2所示。覆盖中有五个节点AE。每个节点在笛卡尔空间中拥有一个区域。最初C拥有右上角的整个区域。当D加入时，C分割所拥有的区域和区域的一部分被赋予D.当D想要用密钥（0.4,0.1）检索对象时，它将请求发送给E和E将请求转发给A.
LSI通过省略除了l个最大奇异值之外的所有奇异值来近
似秩r的矩阵A和具有较低秩l的矩阵Al 。设Ul =（u1，...， ul ），Sigma;l = diag（sigma;1 ，...，sigma;l ），Vl = （v1 ，...， vl）。
psearch系统概述
在pSearch中，大量机器被组织成一个
mantic overlay提供
全文共7453字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[1650]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
