| 基于移动指针的数据流冗余消除算法 |
| |
| 引用本文： | 唐海娜,林小拉,韩春静.基于移动指针的数据流冗余消除算法[J].通信学报,2012(2):7-14. |
| |
| 作者姓名： | 唐海娜 林小拉 韩春静 |
| |
| 作者单位： | 中山大学信息科学与技术学院;中国科学院计算机网络信息中心 |
| |
| 基金项目： | 国家自然科学基金资助项目(61073055);科技部国家科技支撑计划基金资助项目(2012BAH01B03)~~ |
| |
| 摘 要： | 针对数据流的动态特性,提出了一种基于移动指针的数据流冗余消除算法—SKIP Bloom filter,其核心思想是通过动态指针和双Bloom filter来区分历史数据映射与当前数据映射,从而有效提升了算法的性能和准确度。理论证明,它具有O(n)的时间复杂度与O(1-(1-1/(2 m))w-k)k的假阳性误判率。实验结果表明,算法在实际网络环境中与已有算法相比,准确度提高了2-12倍。
|
| 关 键 词： | 数据流 冗余消除 Bloom filter 散列函数 |
Duplicate elimination algorithm for data streams with SKIP Bloom filter |
| |
| TANG Hai-na,LIN Xiao-la,HAN Chun-jing.Duplicate elimination algorithm for data streams with SKIP Bloom filter[J].Journal on Communications,2012(2):7-14. |
| |
| Authors: | TANG Hai-na LIN Xiao-la HAN Chun-jing |
| |
| Affiliation: | 1.School of Information Science and Technology,Sun Yat-sen University,Guangzhou 510006,China; 2.Computer Network Information Center,Chinese Academy of Sciences,Beijing 100190,China) |
| |
| Abstract: | According to the dynamic characteristics of data streams,a duplicate elimination algorithm was proposed with low time complexity and high accuracy based on SKIP Bloom filter.A moving cursor and double Bloom filter were used to differentiate history data and current data mapping.Theoretically,it proves that the algorithm has the time complexity of O(n) and the false positive rate of O.The experiment shows that the new SKIP Bloom filter im-proves the accuracy of 2-12 times in real networks compared with other existing algorithm. |
| |
| Keywords: | data streams duplicate elimination Bloom filter hash function |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《通信学报》浏览原始摘要信息 |
|
点击此处可从《通信学报》下载全文 |
