动态可扩展Cuckoo过滤器设计及应用

摘要

实际应用中大规模动态数据集合的涌现给近似集合成员判定技术带来了日益严峻的挑战：1）集合成员表示数据结构的容量应该支持灵活的扩展和缩小来适应集合大小的动态变化；2）集合成员表示数据结构应该支持可靠删除操作。现有的近似集合成员判定技术，例如，Cuckoo过滤器、布隆过滤器以及布隆过滤器的一系列变种均不能同时满足动态集合的上述两个要求。 为了解决这个问题，设计了动态Cuckoo过滤器。动态Cuckoo过滤器是一种支持可靠删除操作，同时支持弹性容量伸缩的结构，可以高效的进行集合的表示和近似集合成员判定。促使动态Cuckoo过滤器高效性的因素有两点：第一，动态Cuckoo过滤器所使用的数据结构具有可伸缩性，并且使用了通过基于“The power of two choice”思想的重定位技术解决了哈希碰撞带来的低空间使用率问题，使得在动态集合成员的表示中动态Cuckoo过滤器具有很高的空间效率。第二，动态Cuckoo过滤器使用一种独占的指纹来表示数据元素的存在性以此保证可靠的删除操作。 实验结果表明和目前最高效的近似数据集合成员判定技术相比，动态Cuckoo过滤器减少了75%的空间消耗，50%的构建时间，并且将近似集合成员判定速度提升了80%。通过将动态Cuckoo过滤器应用在数据去重模块上并且测试，实验结果进一步证实了动态Cuckoo过滤器的高效性。

目录

第一个书签之前

摘 要

Abstract

目 录

1 绪论

1.1 研究背景及意义

1.2 国内外研究现状

1.2.1 Cuckoo哈希表

1.2.2 Cuckoo过滤器

1.2.3 动态布隆过滤器

1.3 本文主要研究内容

1.4 论文组织结构

2 动态可扩展Cuckoo过滤器设计

2.1 数据结构设计

2.2 动态可扩展结构原理

2.3 基本操作算法

2.3.1 插入操作

2.3.2 查询操作

2.3.3 删除操作

2.3.4 紧凑操作

2.4 本章小结

3 理论分析及空间优化

3.1 假阳性概率分析

3.2 可靠删除分析

3.2.1 多地址问题

3.2.2 多重值问题

3.2.3 重复值问题

3.3 参数影响

3.3.1 插入元素的期望值

3.3.2 总重定位次数的期望值

3.4 空间优化

3.5 本章小结

4 实验设计与结果分析

4.1 实验设计

4.2 实验结果

4.2.1 元素插入操作

4.2.2 集合成员判定操作

4.2.3 元素删除操作

4.2.4 空间紧凑操作

4.3 本章小结

5 动态Cuckoo过滤器的应用

5.1 应用背景

5.2 系统架构

5.3 重删模块实现

5.4 实验设置

5.5 结果分析

5.6 本章小结

6 总结与展望

6.1 总结

6.2 展望

致谢

参考文献

附录1 攻读硕士学位期间发表学术论文目录

附录2 攻读硕士学位期间申请专利和软件著作权目录

附录3 攻读硕士学位期间参与的科研项目