| 一种面向数据流模型的流计数算法 |
| |
| 引用本文： | 廖豪,梁峰,谭建龙. 一种面向数据流模型的流计数算法[J]. 计算机工程, 2010, 36(23): 31-33,35 |
| |
| 作者姓名： | 廖豪 梁峰 谭建龙 |
| |
| 作者单位： | (1.中国科学院计算技术研究所， 北京 100190； 2.中国科学院研究生院， 北京 100049；3.湘潭大学信息工程学院， 湖南 湘潭 411105) |
| |
| 基金项目： | 国家"973"计划基金资助项目 |
| |
| 摘 要： | 在研究数据流过程中，基于现有的概要数据结构Bloom Filter，给出改进的K Bloom Filter结构，从理论上对假阳性误判进行分析，得出两者具有相同的在误判率f0下表示集合规模的上限n0，因此，K Bloom Filter的误判率在可控范围内。提出基于K Bloom Filter的流计数算法，与基于Bloom Filter的流计数算法相比，在相同的空间复杂度O(m)和插入操作时间复杂度O(k)情况下，该算法降低了统计结果的误差。
|
| 关 键 词： | 数据流 布鲁姆过滤器 概要数据结构 |
Flow Counting Algorithm for Data Stream Model |
| |
| LIAO Hao,LIANG Feng,TAN Jian-long. Flow Counting Algorithm for Data Stream Model[J]. Computer Engineering, 2010, 36(23): 31-33,35 |
| |
| Authors: | LIAO Hao LIANG Feng TAN Jian-long |
| |
| Affiliation: | (1.Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China;2.Graduate University of Chinese Academy of Sciences, Beijing 100049, China;3.College of Information Engineering, Xiangtan University, Xiangtan 411105, China) |
| |
| Abstract: | During the process of studying data stream,this paper proposes the K-Bloom Filter structure which is based on the existing synopsis data structure,analyses the false positive misjudgment theoretically,concludes that both can present the upper limits of set scale n_（0）under the same misjudgment rate f_0,so the misjudgment rate of K-Bloom Filter is within the controllable range.The flow counting algorithm based on the K-Bloom Filter structure is gived,under the same space complexity O（m） and insert time complexity O（k）,compared to the flow counting algorithm based on the Bloom Filter structure,the error of the counting result is lower. |
| |
| Keywords: | data stream Bloom Filter synopsis data structure |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载免费的PDF全文 |
|
