p2p环境下的分布式哈希索引结构的研究与实现

《p2p环境下的分布式哈希索引结构的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一，●0，．{^东北大学硕士学位论文摘要P2P环境下的分布式哈希索引结构的研究与实现摘要Intemet的飞速发展使P2P技术成为研究热点。P2P技术为充分挖掘网络上空闲的计算机资源提供了一种手段，实现了网络资源的全面共享。如何设计与之对应的分布式索引结构来支持海量数据下的高效查询成为当前P2P技术研究的核心问题。BloomFilter哈希算法采用位向量来存储数据集合，能有效支持元素的哈希查找，是一种能够简洁地表示数据集合并支持集合查询的索引结构，广泛应用于数据库、网络和分布式系统中。但是BloomFilter哈希算法的“假通过”现象造成了查询的效率低

2、下，而且其存储动态数据集合的能力很差，所以本文提出了一种分片BloomFilter哈希算法。分片BloomFilter哈希算法采用了由多个位向量构成的哈希表，增加了哈希函数的个数但对位向量的填充率没有影响，所以减少了查询的“假通过率"。而且分片B100mFilter还可以动态改变位向量的个数来适应数据集合的变化，很好地适应了P2P系统的动态性。本文还分析了采用分片BloomFilter作为数据集合的索引来简化数据集合运算的方法，分析了在四种集合运算(交，并，差，异或)中分片BloomFilter索引结构的适用性。实验评估和性能分析表明，分片B100m

3、Filter可以减少BloomFilter哈希算法的错误率，并且具有良好的动态性。采用分片BloomFilter作为数据集合的索引结构可以有效的简化集合操作，大大减少P2P系统中的通讯代价并提高查询效率。关键词：P2P系统：BloomFilter；分片BloomFilter；分布式索引；集合运算一II—t一}；)东北大学硕士学位论文摘要P2P环境下的分布式哈希索引结构的研究与实现摘要Intemet的飞速发展使P2P技术成为研究热点。P2P技术为充分挖掘网络上空闲的计算机资源提供了一种手段，实现了网络资源的全面共享。如何设计与之对应的分布式索引结构来支

4、持海量数据下的高效查询成为当前P2P技术研究的核心问题。BloomFilter哈希算法采用位向量来存储数据集合，能有效支持元素的哈希查找，是一种能够简洁地表示数据集合并支持集合查询的索引结构，广泛应用于数据库、网络和分布式系统中。但是B100mFilter哈希算法的“假通过"现象造成了查询的效率低下，而且其存储动态数据集合的能力很差，所以本文提出了一种分片BloomFilter哈希算法。分片BloomFilter哈希算法采用了由多个位向量构成的哈希表，增加了哈希函数的个数但对位向量的填充率没有影响，所以减少了查询的“假通过率”。而且分片B100mFi

5、lter还可以动态改变位向量的个数来适应数据集合的变化，很好地适应了P2P系统的动态性。本文还分析了采用分片BloomFilter作为数据集合的索引来简化数据集合运算的方法，分析了在四种集合运算(交，并，差，异或)中分片B100mFilter索引结构的适用性。实验评估和性能分析表明，分片BloomFilter可以减少B100mFilter哈希算法的错误率，并且具有良好的动态性。采用分片B100mFilter作为数据集合的索引结构可以有效的简化集合操作，大大减少P2P系统中的通讯代价并提高查询效率。关键词：P2P系统；BloomFilter；分片BIo

6、omFilter；分布式索引；集合运算●一；。≯』StudyandImplementationonDistributedHashIndexStructureinP2PEnvironmentsAbstractWitllmerapiddevelopmentofIntemet，Peer．to-Peer(P2P)datamanagementtechnologyisbecomingahotspotinmeresearchfield．TheP2Psystemoa’ersmepossibilit)，fordigging也eidleresourcessumcient

7、ly．ThesharingaIldcooperatingofmeentirenetworkresourcesarerealized．Howtodesignadistributedindex咖turet0support器tronomicaldatafore航cientimerarctionbec锄etllecoreoft11ecurrentP2Ptechn0109y．B100mFilterhashalgoritllmusesabitvectortodenotedataset，anditisabletosupporthaLshqueryemcicntly

8、．BloomFilterisanexcellentdatastructIⅡe，wllichcaIlsucci