一种非合作环境下的资源选择方法

摘要

本发明公开了一种非合作环境下的资源选择方法，本发明在非合作环境中利用基于相关度的资源选择方法，计算出每个资源的相关度并排序，得到一个依据相关度排序的资源列表；通过指纹提取技术从每个资源中提取覆盖统计信息，并利用布隆过滤器进行压缩；采用基于查询关键词语义的分发策略进行高效存储和检索；然后通过比较布隆过滤器来比较相应指纹集的重叠度，从而获取每个资源的新颖度；然后计算每个资源的新颖度，并根据新颖度重新调整候选资源的排列顺序；最后，利用相关度和新颖度进行加权运算，得到最优资源列表。本发明在资源选择时兼顾资源相关度和重叠程度，提高了查询的效率。

说明书

技术领域

本发明涉及一种非合作环境下的资源选择方法，更具体的说，本发明涉及一种兼顾资源相关度和重叠程度的、非合作环境下的资源选择方法。

背景技术

资源选择是分布式信息检索领域的一个热门研究主题。对于给定一个查询Q，分布式搜索引擎利用资源选择方法确定与该查询最相关资源列表，然后将查询发给最相关资源列表中的资源。优秀的资源选择方法能够使得对每个查询，只需要少量资源参与查询就可以达到和全部资源参与查询接近的结果。因此，资源选择的效果直接决定了查询执行过程的效率和查询结果的质量。

大部分传统的资源选择方法关注于资源与查询的相关度。这些方法通常假定各个资源的文档集不存在重叠，或者认为重叠较小以致可以忽略不计。然而，在一个非合作性环境下的P2P搜索引擎中，各个资源独立维护其文档集，不可避免地使得非合作性环境下的资源之间会有相当数量相同或者非常相似的文档。例如，著名的电子图书馆如ACM、IEEE之间存在很多相似的论文，新闻类网站如网易、新浪等，也会包含大量的相似的新闻网页。

面对这种问题，如果资源选择方法不考虑资源文档集的重叠，就可能将一个查询转发给两个重叠程度很高的资源（如两个镜像站点），造成网络资源浪费并降低查询的效率。因此，有必要研究一种兼顾资源重叠和相关度的资源选择方法。

发明内容

针对上述问题，本发明公开了一种非合作环境下的资源选择方法，该方法在选择资源时能够同时兼顾资源重叠度和相关度，最大化预期新颖结果总量，改进资源选择的有效性，从而提高查询的效率。

本发明解决其技术问题采用的技术方案步骤如下：

一种非合作环境下的资源选择方法，是在资源选择时兼顾资源相关度和重叠程度，从而提高查询的效率，该方法采用以下步骤实现：

步骤1：首先利用基于相关度的资源选择方法，计算出每个资源相关度并排序，得到一个依据资源相关度排序的资源列表。

步骤2：从查询结果中获取结果文档的指纹集；假定一个资源组<P1,P2…Pi…Pn>，并假定一个节点产生一个查询Q，当节点收到返回结果后，对每个结果文档，利用指纹提取技术提取出一串固定长度的数字来表示一个结果文档的标题内容。

步骤3：管理覆盖统计信息；这个过程包含了三个子过程：从结果指纹集中提取覆盖统计信息的过程、覆盖统计信息的存储过程、覆盖统计信息检索的过程；所述的管理包含两类操作：存储和检索；当一组覆盖统计信息产生后，系统需要根据覆盖统计信息中查询的语义，分发到系统的各个资源中进行存储，方便覆盖统计信息的检索。

步骤4：计算每个资源的新颖度；根据给定一组资源及其覆盖统计信息，计算出每个资源含新颖结果的数量，进而计算出每个资源对查询结果的新颖度。

步骤5：根据步骤1中计算得出的资源相关度，结合新颖度对资源排序的列表进行调整，使得新颖结果数量最大化。

本发明的有益效果：

1.本发明能够从查询结果中提取覆盖统计信息，这些覆盖统计信息在后续的查询过程中能够用于计算资源间的重叠程度，在资源选择时最大化预期的新颖结果总量，从而改进资源选择的有效性。

2.本发明将覆盖统计信息依其查询的语义向量空间存储到Chord网络中，从而使得相似语义查询集，能够共享覆盖统计信息，极大地减小系统覆盖统计信息的存储空间，并增大了覆盖统计信息的命中率，解决多词同义的问题。

3.在资源间存在重叠的情况下，本发明相比于其他资源选择方法，能够减小查询消息的浪费，有效地提高查询效率。

附图说明

图1为本发明在非合作环境下执行资源选择方法的步骤。

具体实施方式

下面结合附图，对本发明的具体实施方案作进一步详细描述。其具体步骤描述如图1所示：

步骤1.生成初始资源列表。利用基于相关度的资源选择方法，计算出每个资源的相关度并排序，得到一个依据相关度排序的列表。

步骤2. 从查询结果中获取结果文档的指纹集。包括两个子步骤：

1）从结果中提取指纹集。对每个结果文档，利用指纹提取技术提取出一串固定长度的数字来表示一个结果文档的标题内容。两个内容很接近的标题能够用同一个指纹来表现。对某个资源和查询，所有指纹的集合就是该资源的覆盖统计信息。为了更好地解决从短文本提取指纹的问题，本发明采用一种高效的，健壮的，不需要全局统计信息的指纹技术（Shingle-based Discrete Cosine Transform，S-DCT）。为过滤噪音词汇，S-DCT将停用词和标点符号删除；从词序列中生成一组shingle，利用DCT将每个shingle转化成一个指纹。具体地说，S-DCT方法包括以下步骤：

(1) 获得一个结果                                               的标题内容。

(2) 删除停用词和标点符号。

(3) 对每个词执行取词根操作。

(4) 对剩余词按字典序排列，生成一个词序。

(5) 利用滑动窗口技术，对词序生成一组shingles。

(6) 对每个shingle，计算shingle中的哈希值。

(7) 对所有哈希值进行垂直变换，使之哈希值的均值落在0。

(8) 用哈希最大值，规范化所有的哈希值。

(9) 对所有规范化的哈希值进行DCT变换。

(10) 对每个DCT系数量化为少量的bit位上。

(11) 合并所有bit位，创建指纹。

(12) 所有shingles的指纹，用于表示这个结果。

2）压缩指纹集。为了节省带宽和存储空间，利用布隆过滤器来存储指纹集。从而，一个资源的覆盖统计信息的结构表示为：

通常情况下，一个文档的指纹应该基于文档的所有内容产生。

步骤3.管理覆盖统计信息。

当一组覆盖统计信息产生后，系统需要根据统计信息中查询词的语义，分发到P2P网络中。语义相近的查询对应的覆盖统计信息，能够被放在同一个资源上。相应地，查询一个特定关键词的覆盖统计信息，是依据该关键词的语义在语义空间里查询。相应地，给定一个查询，该查询相关的覆盖统计信息通过该查询的语义向量进行检索。从而能够在高效存储和检索覆盖统计信息的同时，减小系统的存储开销和提高系统的可扩展性。

为了减小系统的存储开销和提高系统的可扩展性，本发明采用基于查询关键词语义的分发策略，利用潜在语义索引将每个查询向量映射到其语义向量，再将语义向量映射到一个位于Chord ID范围的整数值，决定该覆盖统计信息应该放在哪个资源。这个过程包含了三个子过程：从结果指纹集中提取覆盖统计信息的过程、覆盖统计信息的存储过程、覆盖统计信息检索的过程。

1）从结果指纹集中提取覆盖统计信息，算法流程为：

其中建立潜在语义索引并映射到语义空间的步骤如下：

(1) 分析文档集合，构建文档集对应的词-文档的矩阵；

(2) 对词-文档矩阵进行奇异值分解（SVD）；

(3) 对SVD分解后的矩阵进行降维；

(4) 使用降维后的矩阵构建潜在语义空间。

2）覆盖统计信息的存储过程，算法执行过程如下：

(1) 当资源A获取一个查询Q的覆盖统计信息CV (Q)后，资源A利用潜在语义索引得到该查询的语义向量VQ。

(2) 然后，将VQ映射到Chord的ID空间，路由指向资源B。

(3) 最后，CV (Q)被发送到它的目的地资源B。

3）覆盖统计信息检索过程。当一个资源（假定为A）发起一个查询Q后，该查询被转换到语义向量VQ，进而映射到一个Chord ID，指向资源B。如果资源B存有查询Q对应的覆盖统计信息CV (Q)，则将覆盖统计信息CV (Q)发给资源A。如果不存在，则资源B寻找是否存在与查询Q相似的查询Q’，满足。如果找到，则返回覆盖统计信息CV (Q’)；如果仍然没有找到相似，则返回一个查询覆盖统计信息失败的消息，并通知资源A在结果返回后需要提取查询Q的覆盖统计信息。

步骤 4.估算每个资源的新颖度

比较资源的布隆过滤器与布隆过滤器，其中S是已选中的资源的集合。表示已经覆盖的文档空间。定义一个资源的新颖度为：

即在布隆过滤器中置为1而布隆过滤器中为0的bit位的数量。类似地，定义布隆过滤器和布隆过滤器的重叠度为：

步骤 5.综合相关度和新颖度对资源进行排序。包括三个子过程：

（1）利用CORI方法，计算每个资源与查询的相关度，并按相关度从高到低排序，得到一个候选资源列表。其中计算所有资源的相关度relevance[i]的算法流程为：

其中s_max是所有候选资源的相关度得分的最大值。为了得到规一化的相关度分值relevance[i]，每个资源的相关度为原始得分s[i]除以s_max。

（2）计算每个资源的新颖度，并根据新颖度重新调整候选资源的排列顺序。资源新颖度novelty[i]计算过程为：

它调用两个函数novelDocs()和overlapDocs()分别计算出每个资源相对于已经选择出的资源列表的新颖文档数n[i]和o[i]，计算n[i]和o[i]的比值c[i]，最后对c[i]规一化得到新颖度novelty[i]。

其中，函数novelDocs()返回布隆过滤器中bit位为1且布隆过滤器中bit位为0的数量。具体来说，其计算公式表示为：

函数overlapDocs()返回布隆过滤器和布隆过滤器中均为1的bit位总数，其计算公式表示为：

（3）计算最优资源列表。综合相关度和新颖度的详细流程为：

每个资源的相关度分值s[i]及其布隆过滤器bf[i]作为算法的输入。算法首先将相关度最高的资源作为种子，每次从剩余资源中挑选最优的一个资源加入到新的资源列表中。其中，计算最优的方法是通过对每个资源的相关度和新颖度加权运算而获得：

其中是一个[0,1]之间的参数。