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

论文摘要

Internet的飞速发展使P2P技术成为研究热点。P2P技术为充分挖掘网络上空闲的计算机资源提供了一种手段,实现了网络资源的全面共享。如何设计与之对应的分布式索引结构来支持海量数据下的高效查询成为当前P2P技术研究的核心问题。Bloom Filter哈希算法采用位向量来存储数据集合,能有效支持元素的哈希查找,是一种能够简洁地表示数据集合并支持集合查询的索引结构,广泛应用于数据库、网络和分布式系统中。但是Bloom Filter哈希算法的“假通过”现象造成了查询的效率低下,而且其存储动态数据集合的能力很差,所以本文提出了一种分片Bloom Filter哈希算法。分片Bloom Filter哈希算法采用了由多个位向量构成的哈希表,增加了哈希函数的个数但对位向量的填充率没有影响,所以减少了查询的“假通过率”。而且分片Bloom Filter还可以动态改变位向量的个数来适应数据集合的变化,很好地适应了P2P系统的动态性。本文还分析了采用分片Bloom Filter作为数据集合的索引来简化数据集合运算的方法,分析了在四种集合运算(交,并,差,异或)中分片Bloom Filter索引结构的适用性。实验评估和性能分析表明,分片Bloom Filter可以减少Bloom Filter哈希算法的错误率,并且具有良好的动态性。采用分片Bloom Filter作为数据集合的索引结构可以有效的简化集合操作,大大减少P2P系统中的通讯代价并提高查询效率。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 P2P系统的产生
• 1.2 P2P系统的拓扑结构
• 1.3 P2P系统的研究热点
• 1.4 本文论文内容及结构
• 第二章 哈希技术
• 2.1 哈希算法
• 2.1.1 哈希算法原理
• 2.1.2 Probability哈希算法
• 2.1.3 哈希算法的发展
• 2.2 Bloom Filter哈希算法
• 2.3 哈希算法性能分析
• 2.4 Bloom Filter哈希算法分析
• 2.5 Bloom Filter哈希算法的应用
• 2.5.1 Bloom Filter在web Cache中的应用
• 2.5.2 Bloom Filter在XML path query中的应用
• 2.5.3 Bloom Filter在分布式索引结构中的应用
• 第三章 分片BLOOM FILTER哈希算法
• 3.1 Bloom Filter哈希算法的扩展
• 3.1.1 计数型Bloom Filter
• 3.1.2 压缩型Bloom Filter
• 3.2 分片Bloom Filter哈希算法
• 3.3 分片Bloom Filter算法性能分析
• 3.4 分片Bloom Filter哈希算法的动态性
• 3.5 算法测试与分析
• 3.5.1 算法实现
• 3.5.2 测试结果与性能分析
• 第四章 DBF数据索引的集合运算
• 4.1 P2P系统中的数据集合运算
• 4.2 DBF位向量的逻辑运算
• 4.3 DBF索引结构的集合运算查询算法
• 4.3.1 DBF过滤器"并"运算查询算法
• 4.3.2 DBF过滤器"交"运算查询算法
• 4.3.3 DBF过滤器"异或"运算
• 4.3.4 DBF过滤器"差"运算
• 第五章 DBF索引结构在P2P系统中的应用
• 5.1 资源定位算法的设计
• 5.2 路由选择算法的设计
• 5.2.1 数据结构的设计
• 5.2.2 函数设计
• 5.3 实验过程
• 5.4 实验结果与分析
• 5.4.1 DBF"并"运算实验结果
• 5.4.2 DBF"交"运算实验结果
• 5.4.3 DBF"异或"运算实验结果
• 5.4.4 DBF"差"运算实验结果
• 第六章 结束语
• 参考文献
• 致谢
• 攻读硕士期间发表的论文