公开(公告)号：CN103970744B

公开(公告)日：2016-12-28

申请号：CN201310028726.1

申请日：2013-01-25

Applicant: 华中科技大学

Inventor： 王桦 ,  周可 ,  李春花 ,  张攀峰 ,  魏建生

IPC: G06F17/30

Abstract: 一种可扩展的重复数据检测方法，属于计算机存储技术领域，解决现有重复数据检测方法中存储容量无法高效扩展的问题，以适应存储需求扩大，重删系统面临升级换代的现状。本发明包括分块处理、指纹提取、布隆过滤器检索、指纹子集表检索、未满布隆过滤器判断、新指纹标记、布隆过滤器数量判断以及布隆过滤器阵列扩展步骤。本发明采用布隆过滤器阵列来检索指纹数据，可快速定位检索范围，提高检索效率，实现重复数据的检测，具有高扩展性、高查询性能、支持元素定位、可控制误判率，有效减少内存开销。布隆过滤器阵列由同构的一系列布隆过滤器构成，只需提供误判率ε’及预估检索的指纹总数量nmax，就能计算出需要的布隆过滤器的数量及哈希函数的个数。

公开(公告)号：CN102253820B

公开(公告)日：2013-03-20

申请号：CN201110162619.9

申请日：2011-06-16

Applicant: 华中科技大学

Inventor： 周可 ,  魏建生 ,  张攀峰 ,  李春花 ,  王桦

IPC: G06F5/06

Abstract: 本发明提供了一种流式重复数据检测方法，通过构建一个计时型布隆过滤器阵列TBFA，在滑动窗口模型内灵活高效地检测重复数据。TBFA由多个同构的计时型布隆过滤器TBF构成，每个TBF包含一个布隆过滤器和一个分离的用于保存时间戳的计时器组，整个TBFA以一种循环先入先出队列的方式工作，在记录新元素的同时，淘汰已经移出数据流监控窗口的旧元素。本发明在滑动窗口模型下工作，对元素的监测可以精确到一个元素，从而使基于本发明的统计结果具有稳定性，另外TBFA中的部分计时器组可以被卸载到磁盘中，从而减少内存开销。理论分析和实验数据表明，DCBA在加载10%以内数据内容到内存的情况下，能够保持95%以上的查询效率，从而使本发明在空间效率和可扩展性上优于现有技术方案。

公开(公告)号：CN103970744A

公开(公告)日：2014-08-06

申请号：CN201310028726.1

申请日：2013-01-25

Applicant: 华中科技大学

Inventor： 王桦 ,  周可 ,  李春花 ,  张攀峰 ,  魏建生

IPC: G06F17/30

CPC classification number: G06F3/0641

Abstract: 一种可扩展的重复数据检测方法，属于计算机存储技术领域，解决现有重复数据检测方法中存储容量无法高效扩展的问题，以适应存储需求扩大，重删系统面临升级换代的现状。本发明包括分块处理、指纹提取、布隆过滤器检索、指纹子集表检索、未满布隆过滤器判断、新指纹标记、布隆过滤器数量判断以及布隆过滤器阵列扩展步骤。本发明采用布隆过滤器阵列来检索指纹数据，可快速定位检索范围，提高检索效率，实现重复数据的检测，具有高扩展性、高查询性能、支持元素定位、可控制误判率，有效减少内存开销。布隆过滤器阵列由同构的一系列布隆过滤器构成，只需提供误判率ε’及预估检索的指纹总数量nmax，就能计算出需要的布隆过滤器的数量及哈希函数的个数。

公开(公告)号：CN102253820A

公开(公告)日：2011-11-23

申请号：CN201110162619.9

申请日：2011-06-16

Applicant: 华中科技大学

Inventor： 周可 ,  魏建生 ,  张攀峰 ,  李春花 ,  王桦

IPC: G06F5/06

Abstract: 本发明提供了一种流式重复数据检测方法，通过构建一个计时型布隆过滤器阵列TBFA，在滑动窗口模型内灵活高效地检测重复数据。TBFA由多个同构的计时型布隆过滤器TBF构成，每个TBF包含一个布隆过滤器和一个分离的用于保存时间戳的计时器组，整个TBFA以一种循环先入先出队列的方式工作，在记录新元素的同时，淘汰已经移出数据流监控窗口的旧元素。本发明在滑动窗口模型下工作，对元素的监测可以精确到一个元素，从而使基于本发明的统计结果具有稳定性，另外TBFA中的部分计时器组可以被卸载到磁盘中，从而减少内存开销。理论分析和实验数据表明，DCBA在加载10%以内数据内容到内存的情况下，能够保持95%以上的查询效率，从而使本发明在空间效率和可扩展性上优于现有技术方案。