基于BCBF+HSet布卢姆过滤器的数据流计数

摘要：

突发检测是数据流的固有问题之一,因其应用广泛而备受研究者关注.突发检测中的一个基本问题是如何保存数据流中所有元素的频数.提出了一个基于改良的计数型布卢姆过滤器BCBF+HSet保存所有元素频数的解决方案.与直观的数组存储方式相比,虽然引入了一定的错误率,但能显著减少存储空间.与两个经典的计数型布卢姆过滤器CBF和DCF相比,BCBF+HSet在存储空间、计算复杂性及错误率上更加适合数据流突发的情形.理论分析与实验测试结果验证了该结论.

关键词： 数据流 突发检测 元素频数 布卢姆过滤器 BCBF HSet 存储空间

作者: 袁志坚 缪嘉嘉 贾焰 王乐

作者单位: 国防科学技术大学计算机学院 长沙 410073

会议类型: 国内会议

会议名称: 第二十五届中国数据库学术会议(NDBC2008)

会议地点: 桂林

会议语种:中文

页码: 240-246

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