基于分层计数型Bloom过滤器的进化数据流计数

摘要：

许多应用场景所产生的数据流中，元素的频数分布符合重尾分布的特点，即大部分元素的频数较小而少部分元素的频数较大。为了解决数据流中所有相异元素及其频数的高效存储问题，提出了一个基于分层的计数型布卢姆过滤器(hierarchical counting Bloomfilter，HCBF)保存所有元素频数的方法。该方法采用长度递减、计数单位递增的多层计数型布卢姆过滤器作为存储数据结构，多层过滤器共同组成元素的频数.与两个经典的计数型布卢姆过滤器CBF和DCF相比，HCBF更加适合真实数据流元素频数分布的重尾特点，在不影响查询性能和错误率的前提下，能够显著地降低空间开销.理论分析与实验结果验证了该结论.

关键词： 数据流管理 重尾分布 元素频数 布卢姆过滤器

作者: 袁志坚 杨圣洪 蔡建宇 贾焰 杨树强

作者单位: 国防科学技术大学计算机学院 长沙 410073 国防科学技术大学计算机学院 长沙 410073;湖南大学计算机与通信学院 长沙 410082 通信指挥学院 武汉 430010

会议类型: 国内会议

会议名称: 第八届全国信息隐藏与多媒体安全学术大会暨湖南省计算机学会第十一届学术年会(CIHW 2009)

会议地点: 长沙

会议语种:中文

页码: 411-415

在线出版日期: 2009-03-01（万方平台首次上网日期，不代表论文的发表时间）