通信学报2012，Vol.33Issue(2)：7-14,8.
基于移动指针的数据流冗余消除算法
Duplicate elimination algorithm for data streams with SKIP Bloom filter
摘要
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(l-(l-l/(2m))w-k)k. The experiment shows that the new SKIP Bloom filter improves the accuracy of 2-12 times in real networks compared with other existing algorithm.关键词
数据流/冗余消除/Bloom filter/散列函数Key words
data streams/ duplicate elimination/ Bloom filter/ hash function分类
信息技术与安全科学引用本文复制引用
唐海娜,林小拉,韩春静..基于移动指针的数据流冗余消除算法[J].通信学报,2012,33(2):7-14,8.基金项目
国家自然科学基金资助项目(61073055) （61073055）
科技部国家科技支撑计划基金资助项目(2012BAH01B03) （2012BAH01B03）
