P2P Web搜索中一种有效的查询路由策略

admin管理员组

文章数量:1530977

2024年3月9日发(作者：)

总第２６４期　

２０１１年第１Ｏ期　

计算机与数字工程　

Ｃｏｍｐｕｔｅｒ＆Ｄｉｇｉｔａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ　

Ｖｏ１．３９　Ｎｏ．１０　

１３　

Ｐ２Ｐ　Ｗｅｂ搜索中一种有效的查询路由策略　

王振华李妹芳　申德荣于戈　

（东北大学信息科学与工程学院沈阳　１１０８１９）　

摘要有效的多关键字查询路由是Ｐ２Ｐ　Ｗｅｂ搜索中的一个关键问题。文章提出一种基于收益代价比的查询处理方　

法。该方法基于ＤＨＴ的Ｐ２Ｐ覆盖网，挖掘关键字的关联性和节点间覆盖度和重叠度。利用最小独立置换进行重叠检测，　

因此避免了对相同记录的冗余路由。实验证明了该方法显著减少了查询时间，同时提高了查全率和查准率。　

关键词Ｐ２Ｐ　Ｗｅｂ搜索；多关键字查询处理；最小独立置换　

中图分类号ＴＰ３０１　

Ａｎ　Ｅｆｆｅｃｔｉｖｅ　Ｑｕｅｒｙ　Ｒｏｕｔｉｎｇ　Ｓｔｒａｔｅｇｙ　ｏｖｅｒ　Ｐ２Ｐ　Ｗｅｂ　Ｓｅａｒｃｈ　

Ｗａｎｇ　Ｚｈｅｎｈｕａ　Ｌｉ　Ｍｅｉｆａｎｇ　Ｓｈｅｎ　Ｄｅｒｏｎｇ　Ｙｕ　Ｇｅ　

（Ｃｏｌｌｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎｏｒｔｈｅａｓｔｅｒｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ　１１Ｏ８１９）　

Ａｂｓｔｒａｃｔ　Ｅｆｆｅｃｔｉｖｅ　ｍｕｌｔｉ—ｋｅｙｗｏｒｄ　ｑｕｅｒｙ　ｒｏｕｔｉｎｇ　ｉｓ　ｔｈｅ　ｋｅｙ　ｐｒｏｂｌｅｍ　ｏｖｅｒ　Ｐ２Ｐ　Ｗｅｂ　ｓｅａｒｃｈ．Ａ　ｎｏｖｅｌ　ｑｕｅｒｙ　ｐｒｏｃｅｓｓｉｎｇ　

ｓｔｒａｔｅｇｙ　ｂａｓｅｄ　ＯＤ　ｂｅｎｅｆｉｔ　ｃＯＳｔ　ｒａｔｉｏ　ｗａｓ　ｐｒｏｐｏｓｅｄ．Ａ　Ｐ２Ｐ　ｏｖｅｒｌａｙ　ｂａｓｅｄ　ｏｎ　ＤＨＴ　ｈａｓ　ｂｅｅｎ　ｂｕｉｌｔ，ａｎｄ　ｔａｋｅ　ｉｎｔｏ　ａｃｃｏｕｎｔ　ｏｆ　ｔｈｅ　

ｃｏｒｒｅｌａｔｉｏｎ　ｏｆ　ｋｅｙｗｏｒｄｓ　ａｓ　ｗｅｌｌ　ａｓ　ｔｈｅ　ｃｏｖｅｒａｇｅ　ａｎｄ　ｏｖｅｒｌａｐ　ａｍｏｎｇ　ｐｅｅｒｓ．Ｍｉｎ－ｗｉｓｅ　ｉｎｄｅｐｅｎｄｅｎｔ　ｐｅｒｍｕｔａｔｉｏｎ　ｗａｓ　ａｐｐｌｉｅｄ　ｆｏｒ　

ｏｖｅｒｌａｐ　ｄｅｔｅｃｔｉｏｎ。ＳＯ　ｔｈｅ　ｒｅｄｕｎｄａｎｔ　ｒｏｕｔｉｎｇ　ｔＯ　ｔｈｅ　ｓａｍｅ　ｒｅｓｕｌｔ　ｉｓ　ａｖｏｉｄｅｄ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａ１　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｍｅｔｈｏｄ　ｉｍ—　

ｐｒｏｖｅｓ　ｔｈｅ　ｓｅａｒｃｈ　ｐｅｒｆｏｒｍａｎｃｅ　ｇｒｅａｔｌｙ．　

Ｋｅｙ　Ｗｏｒｄｓ　Ｐ２Ｐ　Ｗｅｂ　ｓｅａｒｃｈ，ｍｕｌｔｉ—ｋｅｙｗｏｒｄ　ｑｕｅｒｙ　ｐｒｏｃｅｓｓｉｎｇ，ｍｉｎ－ｗｉｓｅ　ｉｎｄｅｐｅｎｄｅｎｔ　ｐｅｒｍｕｔａｔｉｏｎ　

Ｃｌａｓｓ　Ｎｕｍｂｅｒ　ＴＰ３０１　

１　引言　

基于Ｐ２Ｐ的Ｗｅｂ搜索具有分布性、扩展性、自　

和重叠度以提高搜索性能，并利用最小独立置换进　

行重叠探测，因此避免了对相同记录的冗余路由，　

提高了查询效率。　

组织性和负载平衡等特征，可以弥补传统集中式搜　

索引擎的诸多不足Ｌ１］。要实现一个真正实用的　

Ｐ２Ｐ　Ｗｅｂ搜索系统面临巨大的挑战ｌ２］，一个主要　

２　相关工作　

经典的查询路由算法如ＣＯＲＩ：　，ＧＬＯＳＳＥ　，　

还有基于统计语言模型的路由算法Ｅ引，这些都只适　

用于文档集合稳定且规模较小的情况，都没有考虑　

到属性间的关联或节点间的特性。ＯＤＩＳＳＥＡＥ　］采　

的困难是如何有效地查找资源，也就是说高效地选　

择最有希望满足用户查询请求的那些节点。　

本文研究了基于Ｐ２Ｐ的Ｗｅｂ搜索中的查询关　

键字分布和各种特征，关注于有效的多关键字查询　

路由，这是Ｐ２Ｐ　Ｗｅｂ搜索中的一个关键问题。基　

于ＤＨＴ的结构化Ｐ２Ｐ网络，我们提出一种新的基　

于收益代价比的多关键字查询路由策略，有效地利　

用了两层的搜索引擎结构，其中全局搜索引擎可能　

会在发布元数据时造成网络通信拥塞。为了衡量　

节点与查询之间的相似度，ＰｌａｎｅｔＰ［　］中提出一种　

基于逆节点频率（ｉｎｖｅｒｓｅ　ｐｅｅｒ　ｆｒｅｑｕｅｎｃｙ，ＩＰＦ）的相　

用统计信息，挖掘关键字的关联性和节点间覆盖度　

＊

关度排序算法。ＰｌａｎｅｔＰ基于无结构化的Ｐ２Ｐ网　

收稿日期：２０１１年３月３１日，修回日期：２０１１年５月１８日　

基金项目：国家自然科学基金（编号：６０９７３０２１，６１００３０６０）资助。　

作者简介：王振华，男，博士，讲师，研究方向：分布式数据管理。李妹芳，女，硕士研究生，研究方向：分布式数据管理。　

申德荣，女，教授，博士生导师，研究方向：Ｄｅｅｐ　Ｗｅｂ。于戈，男，教授，博士生导师，研究方向：分布式数据库。　

１４　王振华等：Ｐ２Ｐ　Ｗｅｂ搜索中一种有效的查询路由策略　第３９卷　

络来传播节点集合的信息，但是Ｐｅｅｒ的节点数目　

有限。ＭＩＮＥＲＶＡＥ　］是一个基于ＤＨＴ覆盖网络构　

建的Ｐ２Ｐ　Ｗｅｂ搜索引擎。ＭＩＮＥＲＶＡ维护节点集　

合统计信息的全局索引信息，提出了一种采用统计　

方法评估各数据集之间的重叠关系来进行数据集　

选择的算法。　

３　Ｐ２Ｐ　Ｗｅｂ搜索面临的挑战　

在Ｐ２Ｐ　ｗｅｂ搜索中，基本的功能就是找到那　

些拥有高质量查询结果的节点。高效的Ｐｅｅｒ路由　

机制是Ｐ２Ｐ　Ｗｅｂ搜索的核心，要通过Ｐ２Ｐ网络中　

的本地数据集合的统计概要信息来选择最优节点。　

另一方面，对于一个给定的关键字，是通过关键字　

来组织节点路由的。因此，在查询处理之前，每个　

节点向全局路由发布一个关于每个数据项在它本　

地索引中的概要信息。利用ＤＨＴ来路由负责该　

数据项的目录节点，因为它维护了在整个网络中的　

所有概要信息的节点列表。　

多关键字查询处理是Ｐ２Ｐ　Ｗｅｂ搜索系统中的　

常见问题。当一个节点发出一个多关键字查询时，　

要对每一个关键字分别执行ＤＨＴ上的查找操作　

以联系目录节点，然后将多个结果进行合成、排序，　

返回给用户，查询将被转发到最有可能提供相关结　

果的节点。　

在该方法中，需要很多回合的查询传送，代价　

很大。另一个问题是它完全不考虑关键字间的关　

联和节点之间的覆盖重叠，这可能导致查询结果不　

准确。考虑一个包含３个关键字的查询Ｑ一｛ｔ　，　

ｔ　，ｔ。）。假定节点Ｐ　有大量的数据项包含这些关　

键字，但没有一个数据项包含所有这些关键字。由　

于在这种方法中，查询处理都是独立执行的，因此　

仍然会认为Ｐ　是一个包含相关信息的节点，而事　

实上，Ｐ　并不满足需要。　

４基于收益代价比的查询处理　

４．１相关定义　

针对Ｐ２Ｐ　Ｗｅｂ搜索中多关键字查询处理面临　

的挑战，本文提出基于收益的多关键字查询处理策　

略，它考虑了关键字问的关联和节点间的关系来提　

高查询性能。　

在进行查询路由时，我们的目标是找到结果质　

量高且通信代价小的节点，为此，我们将收益代价　

比作为衡量的标准。收益代价比表示为：　

Ｂ　ｅｎｅｆ

ｉｔ

ｒ—

一　

幽　（１）　

Ｌ　０Ｓ￡　

．

ｅｘｅｃ　ｔｚ０竹ＣＯＳｔ　

其中Ｂｅｎｅｆｉｔ表示收益，由结果质量决定。Ｃｏｓｔ表　

示执行代价，主要考虑带宽等因素。为计算收益代　

价比，我们给出如下定义：　

定义１关联度：给定两个关键字ｔ　与ｔ，，则ｔ，　

与ｔ　之间的关联度Ｃｏｔ（　，ｔ，）定义如下：　

Ｃｏｒ（ｔｉ，　）一　（／　－－ｔｉ）（／　，一　）／（ｎ－－１）　，仃，

，　

一

∑　／ｎ　

＝＝＝　

ｔ　ｎ　（２）　

其中，－厂，

．

是节点户　中关键字ｔ　的频度，ｎ是节点的　

数量，ｔ　是关键字ｔ，的频度均值，　是ｔ，的标准差。　

该定义可以很容易地扩展到多个关键字上。为了　

简化，我们在以下的定义中用ＣＯＦ（Ｕｔ，）来表示多个　

关键字的关联度。　

以下定义均是基于关键字的关联度的基础上　

计算得来。　

定义２覆盖度：每个节点Ｐ　对于一个查询Ｑ　

一

｛ｔｌ，ｔ２，…，￡　｝的覆盖度ｃｏｙ（Ｐ　），指对于查询Ｑ　

返回的结果属于节点Ｐ，的概率，表示为　

ｃｏｖ（Ｐ　）＝＝＝Ｐ（Ｐ　ｌＱ）　

一　

（Ｌ厂（ｆ口．　ｆ）＊ｃｏｒ（Ｕ　，ｔ　ｒ）｝（３）　

ＩＧ｛１，…，ｍ｝　七　ｔ　

１＜【Ｉ｛　

其中，Ｌ厂（ｆ　ｎ　ｔ　｛）是关键字同时在Ｐ，中出现的概　

率，ｃｏｒ（Ｕ　ｔ，）是它们的关联度。因此，通过探测关　

键字间的关联，可以处理原始查询策略中存在的问　

题。由于每个节点通常只提供结果的一个子集，覆　

盖度表明每个节点覆盖查询Ｑ的结果的程度。　

定义３重叠度：考虑两个数据项集合，Ｓ　与　

ｓ，，每个数据元素由唯一ＩＤ标识，这两个集合的重　

叠度被定义为ｌＳ　ｎＳ　ｌ，即交集的势　

　１Ｓ　ｎ　Ｓ，Ｉ—Ｊ　Ｓ　Ｉ＋Ｊ　Ｓ　ｌ～Ｉ　Ｓ　Ｕ　Ｓ　Ｊ　（４）　

由于要考虑多节点的重叠情况，我们利用　

Ｐｏｉｎｃａｒ４和Ｓｙｌｖｅｓｔｅｒ筛选公式，式（４）可以被扩展为：　

　ＩＳ　Ｉ一∑（一１）抖　∑　｝ｌｎ　Ｓ　Ｉ（５）　

一

ｌ　Ｊ　｛１，…，”）　

ｉＩＩ＝　

其中，　是节点个数。因此，假定Ｐ　和ＰＪ分别包含　

数据集Ｓ　和Ｓ　，定义Ｐ　和其它节点间的重叠度　

ｏｖｅｒｌａｐ（Ｐ　）用如下公式：　

ｏｖｅｒｌａｐ（Ｐｉ）一　ｌＳｉ

，

ｆ］　ｓ　ｌ　（６）　

１Ｇｆ１．１…，　｝　Ｊｃ　’Ｊ　

　ｌＪＩ一＂一１　

注意覆盖度指的是节点与查询之间的关系，而　

重叠度指节点之间的相互关系。对于一个查询Ｑ，　

我们想要获得对Ｑ具有高覆盖度并且节点间具有　

２０１１年第１Ｏ期　计算机与数字工程　

低重叠度的节点。因此，节点的收益表示为：　

１　

是不存在的。然而，可以通过随机线性变换（ｒａｎ－　

（７）　Ｂ　ｆｉｔ（Ｐ　）一ｃｏｖ（Ｐ，）　

ｄｏｍ　ｌｉｎｅａｒ　ｔｒａｎｓｆｏｒｍａｔｉｏｎ）来近似最小独立置换。　

给定ｍ个节点，应用最小独立置换进行重叠　

４．２查询处理过程　

探测的工作过程如下：　

１）使用线性哈希函数计算一个随机的置换，　

然后排序哈希值。哈希函数形如ｈ　（　）一（ｎ　＊ｚ＋　

首先根据ＤＨＴ从全局索引目录中能够得到　

所有包含某一个关键字的节点列表，通过交集运算　

能够得到包含所有查询关键字的节点列表。这就　

ｂ　）ｍｏｄ　ｋ，其中是是一个大的素数，以　，ｂ　为随机选　

择的整数。这随机生成的　对（　，６）值，构成了　

个哈希函数。　

得到了能够满足查询的初始节点集合。　

出于性能的考虑，为了节省带宽，要对初始节　

点集合进行修剪，目录节点对每个关键字只返回最　

优的节点，生成备选节点集合。　

但这仍然可能生成很大的节点集合，最后，计　

算备选节点集合中各节点的收益代价比，根据收益　

代价比评估备选节点，从中选择ｋ个最优的节点。　

４．３重叠探测　

在大规模网络环境下，由于Ｐ２Ｐ系统中节点　

的自治性，查询返回的结果列表中的节点相互之间　

通常具有高度的重叠性，因此节点返回重复结果的　

概率很大，重复的结果是无用的，导致了带宽的浪　

费，这不是我们希望得到的。例如，当节点发起查　

询，查找某歌手最近一年的歌曲，通常我们更希望　

得到互补的结果，而不是相同的结果。　

因此，我们要考虑数据集之间的重叠关系。然　

而，两节点之间的重叠度很难得到，我们可以利用　

最小独立置换（Ｍｉｎ—ｗｉｓｅ　Ｉｎｄｅｐｅｎｄｅｎｔ　Ｐｅｒｍｕｔａ－　

ｔｉｏｎ，ＭＩＰ）方法进行重叠探测，估算节点间的重叠　

度。最小独立置换的定义如下：　

定义４最小独立置换：令ｓ　为［　］上的全排　

列，如果置换集合Ｆ　Ｓ　对于Ｘ　ｊ”ｌ，　∈Ｘ，随　

１　

机选取丌∈Ｆ，有Ｐｒ（ｍｉｎ｛ｒｒ（Ｘ）｝一７【（　））一　，则　

Ｉ　Ａ　ｌ　

称Ｆ是最小独立置换。其中，Ｐｒ表示成为最小元　

素的概率。　

ＭＩＰ的原理是：通过散列函数丌对集合Ｘ的　

映射，使集合Ｘ中的每一个元素　的散列值７ｒ（ｚ）　

一ｍｉｎ（７ｃ（　】），７【（　２），…，７【（　））的概率相等，丌为　

置换函数。即在随机置换的情况下，每个元素成为　

最小元素（即位置最小处的值）的概率是相同的。　

可以采用集合中对应位置的元素相等的数量来估　

算相似度，ＭＩＰ能够以很小的错误率和合理的空间　

及带宽提供评估集合相似度。　

可以通过采样的方法估算两个集合的相似度，　

即计算二者之间的Ｊａｃｃａｒｄ距离。文献［９］指出，由　

于无法做到随机均匀地选取，因此满足条件的置换　

２）获得数据项有序集合的ｍ个随机置换。　

３）使用　维的ＭＩＰ评估集合中的两两相似　

性。统计两个向量拥有相同位的位置数量，然后除　

以　。　

４）对ｍ个置换中的每一个置换，应用ＭＩＰ确　

定最小的哈希值，把它存储在ｍ维的向量中，因此　

获得这些随机置换中每一个置换的最小的集合元　

素。　

Ｈａｓｈ　Ｓｋｅｔｃｈｅｓ［９＿和Ｂｌｏｏｍ　Ｆｉｌｔｅｒ［　］方法也可　

以用于重叠探测，然而它们的不足之处在于所有的　

ｈａｓｈ　ｓｋｅｔｃｈ必须具有相同的比特位长度或者所有　

的过滤器集合必须大小相同，这在多关键字查询处　

理情况下是一个很大的限制。而采用最小独立置　

换时，对于两个最小独立置换向量，大小分别是ｍ　

和ｍ　，我们能够处理ｍｉｎ（ｍ　，ｍ：）置换。因此，我　

们使用ＭＩＰ进行重叠探测，确定要返回给查询发　

起节点的结果，通过这种方式提高搜索质量。　

５　实验分析　

本文模拟了１０００个节点，实验数据集是利用　

Ｗｉｋｉｐｅｄｉａ字典上的文档子集，文档总数ｉ００００个。　

我们比较了基于收益代价比的多关键字查询　

处理方法（ＢＣＲ—Ｍｅｔｈｏｄ）和基本方法（ＤＨＴ—Ｍｅｔｈ—　

ｏｄ）。比较了两种方法的时间代价以及查准率，实　

验结果如图１和图２所示。结果表明ＢＣＲ－Ｍｅｔｈ—　

ｏｄ具有更好的性能。　

１　０　

６００　

ｊｌ三　Ｒ—＊－ＢＣ—　Ｍ　ｆ／ｅｔ　ｈｏ　ｄ　三　　

ｃ　０　８　

０　

，ｒ　

●　

８　４００　

０６　

Ｏ４　

一　

ｌ　２００　

／

／一　一　——．一　

０　２　

Ｏ　

０　２０　４０　６０　８０　

Ｏ　

三　｝　

Ｎｕｍｂｅｒ　ｏｆ　ｒｅｓｕｌｔｓ　

图１时间代价比较　图２查准率比较　

我们评估了在不同节点数量和返回结果的情　

况下，不使用最小独立置换与使用最小独立置换检　

（下转第１７９页）　

２０１１年第１Ｏ期　计算机与数字工程　１７９　

结合针对标牌行业进行标牌特殊图形的ＡｕｔｏＣＡＤ　

二次开发，拓宽了ＡｕｔｏＣＡＤ二次开发的范围，改　

进了ＡｕｔｏＣＡＤ的绘制方法对特殊图形不能快速　

１－４］于萧榕，郭昌言，陈刚．结合Ｏｂｊｅｃｔａｒｘ和Ｃ进行Ａｕｔｏ—　

ＣＡＤ二次开发框架的研究ＥＪ］．科学技术与工程，２０１０　

（２０）：５０８５～５０９０　

获取参数的问题，不能利用参数化的方法绘制并记　

录到扩展数据集中的问题，解决特殊图形的绘制定　

位不精确的问题，减少了绘制时间，提高了工作效　

率，保证了标牌制作质量。　

参考文献　

［５］孙江宏，丁立伟，米洁．ＡｕｔｏＣＡＤ　ＯｂｊｅｃｔＡＲＸ开发工具　

及应用［Ｍ］．北京：清华大学出版社，１９９９　

－Ｉ６］薛长健，黄靖．ＡｕｔｏＣＡＤ　２０００高级使用及开发［Ｍ］．北　

京：人民邮电出版社，２０００：４１３￣４９６　

Ｅ７］于萧榕．基于ＯｂｊｅｃｔＡＲＸ的标牌印刷分色拼版的研究　

［Ｊ］．科学技术与工程，２０１１（２）：３８３￣３８７　

Ｅｌｉ王大鹏，张立文，张国梁，等．ＯｂｊｅｃｔＡＲＸ中结合ＭＦＣ　

开发ＡｕｔｏＣＡＤ　ＡＲＸ应用程序［Ｊ］．计算机辅助工程，　

２００１，１０（４）：５５～５８　

Ｅ８］李长勋．ＡｕｔｏＣＡＤ　ＯｂｊｅｃｔＡＲＸ程序开发技术ＦＭ］．北　

京：国防工业出版社，２００５　

［９］杜刚，刘东学，张磊．基于ＯｂｊｅｃｔＡＲＸ的ＡｕｔｏＣＡＤ二次　

开发及应用实例［Ｊ］．机械设计与制造，２００４（３）：３０￣３２　

［１Ｏ］杜立，赵韩，董玉德，等．基于ＯｂｊｅｃｔＡＲＸ齿轮设计系　

统的开发与研究［Ｊ］．机械设计与制造，２００８（１２）：７５～　

７７　

［２］童时中，李平．二次开发是ＣＡＤ取得实效的关键环节　

ＥＪ］．电子机械工程，１９９９（４）：６４￣６８　

ｆ３］赵雪．中文ＡｕｔｏＣＡＤ　２００６标准教程［Ｍ］．西安：西北工　

业大学音像电子出版社，２００５：３～１０　

乖　秘　石　乖　乖　尔　币　不　矫　铞　

（上接第１５页）　

索到重复结果的数量。图３显示了重复结果相当　

多，是不可忽略的，因此重叠探测对于获得更好的　

ｔｅｎｔ　ｓｅａｒｃｈ：ｇｉｖｅ　ｔｈｅ　ｗｅｂ　ｂａｃｋ　ｔｏ　ｔｈｅ　ｐｅｏｐｌｅ　Ｅ　ｃ］／／　

ＩＰＴＰＳ．Ｓａｎｔａ　Ｂａｒｂａｒａ　ＵＳＡ。２００６　

结果质量很有必要。　

】６　

Ｉ－３］Ｃａｌｌａｎ　Ｊ．Ｐ．，Ｚ．Ｌｕ，ｗ．Ｂ．Ｃｒｏｆｔ．Ｓｅａｒｃｈｉｎｇ　ｄｉｓｔｒｉｂｕ—　

ｔｅｄ　ｃｏｌｌｅｃｔｉｏｎｓ　ｗｉｔｈ　ｉｎｆｅｒｅｎｃｅ　ｎｅｔｗｏｒｋｓ［Ｃ］／／ＳＩＧＩＲ．　

Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，１９９５：２１～２８　

１４　

Ｅ４］Ｌ．Ｇｒａｖａｎｏ，Ｈ．Ｇａｒｃｉａ－Ｍｏｌｉｎａ，Ａ．Ｔｏｍａｓｉｃ．Ｇｌｏｓｓ：　

１２　

鼍１ｏ　

｛　

￣４

ｔｅｘｔ—ｓｏｕｒｃｅ　ｄｉｓｃｏｖｅｒｙ　ｏｖｅｒ　ｔｈｅ　ｉｎｔｅｒｎｅｔ［Ｊ］．ＡＣＭ　

Ｔｒａｎｓ．Ｄａｔａｂａｓｅ　Ｓｙｓｔ．，１９９９，２４（２）：２２９～２６４　

－８２　

Ｅ５］Ｌ．Ｓｉ，Ｒ．Ｊｉｎ，Ｊ．Ｃａｌｌａｎ，ｅｔ　ａ１．Ａ　ｌａｎｇｕａｇｅ　ｍｏｄｅｌｉｎｇ　

ｆｒａｍｅｗｏｒｋ　ｆｏｒ　ｒｅｓｏｕｒｃｅ　ｓｅｌｅｃｔｉｏｎ　ａｎｄ　ｒｅｓｕｌｔｓ　ｍｅｒｇｉｎｇ　

童６　

主４　

２　

０　

［Ｃ］／／ＣＩＫＭ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２００２：３９１￣３９７　

［６］Ｔ．Ｓｕｅｌ，Ｃ．Ｍａｔｈｕｒ，Ｊ．ｗｕ，ｅｔ　ａ１．Ｏｄｉｓｓｅａ：Ａ　ｐｅｅｒ－　

ｌＯ　２０　３Ｏ　４０　５０　６０　７０　８０　

ｔｏ－ｐｅｅｒ　ａｒｃｈｉｔｅｃｔｕｒｅ　ｆｏｒ　ｓｃａｌａｂｌｅ　ｗｅｂ　ｓｅａｒｃｈ　ａｎｄ　ｉｎｆｏｒ—　

Ｎｕｍｂｅｒ　ｏｆ　ｑｕｅｒｉｅｄ　ｐｅｅｒｓ　

ｍａｔｉｏｎ　ｒｅｔｒｉｅｖａｌ［Ｒ］．Ｔｅｃｈｎｉｃａ１　ｒｅｐｏｒｔ　ＴＲ－ＣＩＳ－２００３—　

０１，Ｐｏｌｙｔｅｃｈｎｉｃ　Ｕｎｉｖ．，２００３　

图３重叠探测　

６　结语　

本文研究了基于Ｐ２Ｐ的Ｗｅｂ搜索中的查询关　

键字分布和各种特征，关注于有效的多关键字查询　

路由，这是Ｐ２Ｐ　Ｗｅｂ搜索中的一个关键问题。我　

们提出了一种新的基于收益代价比的查询处理策　

略，应用最小独立置换进行重叠探测。实验结果表　

［７］Ｆ．Ｍ．Ｃｕｅｎｃａ—Ａｃｕｎａ，Ｃ．Ｐｅｅｒｙ，Ｒ．Ｐ．Ｍａｒｔｉｎ，ｅｔ　ａ１．　

ＰｌａｎｅｔＰ：Ｕｓｉｎｇ　Ｇｏｓｓｉｐｉｎｇ　ｔｏ　Ｂｕｉｌｄ　Ｃｏｎｔｅｎｔ　Ａｄｄｒｅｓｓａｂｌｅ　

Ｐｅｅｒ－ｔｏ－Ｐｅｅｒ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｈａｒｉｎｇ　Ｃｏｍｍｕｎｉｔｉｅｓ［Ｒ］．　

Ｔｅｃｈｎｉｃａｌ　Ｒｅｐｏｒｔ　ＤＣ　Ｔ１　４８７，Ｄｅｐｔ．　ｏｆ　Ｃｏｍｐｕｔｅｒ　

Ｓｃｉｅｎｃｅ，Ｒｕｔｇｅｒｓ　Ｕｎｉｖｅｒｓｉｔｙ，２００２　

　ｌ８　Ｉ　Ｍ　Ｂｅｎｄｅｒ，Ｓ．Ｍｉｃｈｅ１，Ｐ．Ｔｒｉａｎｔａｆｉｌｌｏｕ，ｅｔ　ａ１．ＭＩ—　

ＮＥＲＶＡ：ｃｏｌｌａｂｏｒａｔｉｖｅ　Ｐ２Ｐ　ｓｅａｒｃｈ［Ｃ］／／ＶＬＤＢ．Ｎｅｗ　

Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２００５：１２６３４１２６６　

明，该方法能够提高查询性能。　

参考文献　

［９］Ａ．Ｚ．Ｂｒｏｄｅｒ，Ｍ．Ｃｈａｒｉｋａｒ，Ａ．Ｍ．Ｆｒｉｅｚｅ，ｅｔ　ａ１．　

Ｍｉｎ－ｗｉｓｅ　ｉｎｄｅｐｅｎｄｅｎｔ　ｐｅｒｍｕｔａｔｉｏｎｓ［Ｃ］／／ＳＴＯＣ．Ｎｅｗ　

Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，１９９８：３２７～３３６　

［１］方启明，杨广文，武永卫，等．基于Ｐ２Ｐ的Ｗｅｂ搜索技　

术¨Ｊ］．软件学报，２００８，１９（１０）：２７０６－－２７１９　

［１Ｏ］Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒ．Ｃｏｍｐｒｅｓｓｅｄ　Ｂｌｏｏｍ　ｆｉｌｔｅｒｓ［Ｊ］．　

ＩＥＥＥ／ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｎｅｔｗｏｒｋｉｎｇ，２００２，１０　

（５）：６０４～６１２　

Ｅ２］Ｂｅｎｄｅｒ　Ｍ，Ｍｉｃｈｅｌ　Ｓ，Ｔｒｉａｎｔａｆｉｌｌｏｕ　Ｐ，ｅｔ　ａ１．Ｐ２Ｐ　ｃｏｎ　

本文标签： 节点查询关键字重叠集合