Duplicate elimination algorithm for data streams with SKIP Bloom filter
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 prov...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2012-02-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/1000-436X(2012)02-0007-08/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1000-436X |