Duplicate elimination algorithm for data streams with SKIP Bloom filter - Hai-na TANG; Xiao-la LIN; Chun-jing HAN (Tongxin xuebao)
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(1﹣(1﹣1/(2m))＜sup＞w·k＜/sup＞)＜sup＞k＜/sup＞.The experiment shows that the new SKIP Bloom filter improves the accuracy of 2～12 times in real networks compared with other existing algorithm.