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

发布时间：2018-04-04 18:06

本文选题：对等网络　切入点：多关键字搜索　出处：《湖南大学》2012年硕士论文

【摘要】：现有的基于布鲁姆过滤器的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％。
[Abstract]:The existing P2P network multi-keyword search based on Bloom filter has proposed two basic query modes: "and query" and "or query".The use of Bloom filter encodes effectively reduces the network traffic generated in the retrieval process.However, in P2P networks, nodes are free to join and leave, and documents stored on nodes may be inserted and deleted as nodes join and leave, but the Bloom filter does not support delete operations, and when documents are deleted frequently in the network,It is necessary to constantly reconstruct the Bloom filter to accommodate the deletion of documents, which adds other overhead to the system.In addition, the traditional search engine supports the words that must be included in the search results by a plus sign before the keywords, while the minus sign is used to denote the words that cannot be included in the restricted search results.However, this query mode has not been studied in the multi-keyword search in P2P networks.In this paper, the P2P multi-keyword search mechanism as the research object, mainly aimed at the dynamic characteristics of P2P network, P2P multi-keyword search mechanism generated a large number of network traffic and P2P network multi-keyword search function expansion, the main work is as follows:First, the P2P "and query" based on counting Bloom filter is proposed. The counter Bloom filter is used to store the key index table. The count Bloom filter supports deletion operation, and it is easy to convert to the Bloom filter.Therefore, P2P "and query" based on counting Bloom filter can not only effectively reduce the traffic in the network, but also adapt to the dynamic environment in which P2P nodes can join or leave freely, and improve the retrieval efficiency.The experimental results show that compared with the traditional P2P "and query" based on Bloom filter, the hit ratio of P2P "and query" based on counting Bloom filter is increased by 51010cm, and the query delay is reduced by 10ms / 40ms.Secondly, the P2P "or query" based on counting Bloom filter is proposed. The experimental results show that compared with the traditional P2P "or query" based on Bloom filter,Peer-to-Peer (P2P) or query based on count Bloom filter increases the hit rate by 7% and reduces query latency by 12 Ms / 45 Ms.Thirdly, a P2P "subtractive query" based on Bloom filter is proposed, which extends the function of multi-keyword search in P2P network.The experimental results show that, compared with subtractive queries that directly transfer document sets, the hit rate of P2P subtractive queries based on Bloom filter is increased by 7 / 15, and the query delay is reduced by 10 Ms / 37 ms.In the generation of network traffic, reduced the number of 53.01.
【学位授予单位】：湖南大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP393.02;TP391.3

【参考文献】