谈过滤器基于布鲁姆过滤器P2P多关键字搜索技术

摘要：现有的基于布鲁姆过滤器的P2P网络多关键字搜索，已经提出了两类最基本的查询方式：“与查询”和“或查询”，利用布鲁姆过滤器编码有效地减少了检索历程中产生的网络流量。然而，在P2P网络中，节点的加入和离开是自由的，存储在节点上的文档可能随着节点的加入和离开而插入和删除，但布鲁姆过滤器不支持删除操作，当网络中文档删除频繁时，需要不断地重新构造布鲁姆过滤器以适应文档的删除，这样反而给系统增加其他开销。另外，传统的搜索引擎支持在关键词前冠以加号限定搜索结果中必须包含的词汇，而用减号则表示限定搜索结果不能包含的词汇。然而，在P2P网络的多关键字搜索中没有探讨过这种查询方式。本论文以P2P多关键字搜索机制为探讨对象，主要针对P2P网络的动态特性、P2P多关键字搜索机制产生大量的网络流量以及P2P网络的多关键字搜索功能扩展进行探讨，主要工作如下：一、提出基于计数布鲁姆过滤器的P2P“与查询”，利用计数布鲁姆过滤器存储关键字索引表，计数布鲁姆过滤器支持删除操作，且极易向布鲁姆过滤器转换，由此基于计数布鲁姆过滤器的P2P“与查询”既可以有效地减少网络中的流量，又可以适应P2P网络节点可以自由加入或离开的动态环境，提升了检索效率。实验结果表明，与传统的基于布鲁姆过滤器的P2P“与查询”相比，基于计数布鲁姆过滤器的P2P“与查询”在命中率上提升了5%~10%，同时在查询延迟上，减少了10ms~40ms。二、提出基于计数布鲁姆过滤器的P2P“或查询”，实验结果表明，与传统的基于布鲁姆过滤器的P2P“或查询”相比，基于计数布鲁姆过滤器的P2P“或查询”在命中率上提升了7%~11%，同时在查询延迟上，减少了12ms~45ms。三、提出一种基于布鲁姆过滤器的P2P “减查询”，扩展了P2P网络多关键字搜索的功能。实验结果表明，与直接传递文档集合的减查询相比，基于布鲁姆过滤器的P2P“减查询”在命中率上提升了7%~15%，在查询延迟上，减少了10ms~37ms。在产生网络流量方面，减少了53.01％。关键词：对等网络论文多关键字搜索论文分布式哈希表论文布鲁姆过滤器论文计数布鲁姆过滤器论文倒排索引论文减查询论文

摘要4-5

Abstract5-9

插图索引9-11

附表索引11-12

第1章 绪论12-20

1.1 探讨背景和作用12-14

1.2 国内外探讨近况14-18

1.2.1 非结构化 P2P 网络搜索机制14-15

1.2.2 结构化 P2P 网络搜索机制15-18

1.3 本论文的探讨内容18-19

1.4 本论文的组织结构19-20

第2章 相关探讨综述20-33

2.1 P2P 的介绍20-21

2.2 对等网络关键字搜索技术21-24

2.2.1 P2P 查询算法21-23

2.2.2 P2P 关键字搜索机制23-24

2.3 布鲁姆过滤器技术介绍24-28

2.3.1 标准布鲁姆过滤器介绍25-27

2.3.2 计数布鲁姆过滤器介绍27-28

2.4 倒排索引技术介绍28-32

2.4.1 全文索引原理29-30

2.4.2 创建索引的历程30-31

2.4.3 如何对索引进行搜索31-32

2.5 本章小结32-33

第3章 基于计数布鲁姆过滤器的 P2P“与查询”33-46

3.1 引言33

3.2 仿真软件介绍33-35

3.2.1 Peersim 的结构33-34

3.2.2 Peersim 的特点34-35

3.3 基于计数布鲁姆过滤器的“与查询”35-43

3.3.1 基于计数布鲁姆过滤器的“与查询”设计38-40

3.3.2 基于计数布鲁姆过滤器的“与查询”实现40-43

3.4 实验结果和浅析43-45

3.5 本章小结45-46

第4章 基于计数布鲁姆过滤器的 P2P“或查询”46-53

4.1 引言46

4.2 基于计数布鲁姆过滤器的“或查询”46-50

4.2.1 基于计数布鲁姆过滤器的“或查询”设计47-48

4.2.2 基于计数布鲁姆过滤器的“或查询”实现48-50

4.3 实验结果和浅析50-52

4.4 本章小结52-53

第5章 基于布鲁姆过滤器的 P2P“减查询”53-61

5.1 引言53-54

5.2 基于布鲁姆过滤器的“减查询”54-58

5.2.1 基于布鲁姆过滤器的“减查询”设计55-56

5.2.2 基于布鲁姆过滤器的“减查询”实现56-58

5.3 实验结果和浅析58-60

5.4 本章小结60-61

结论61-63