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!
|
| _version_ | 1841539940825956352 |
|---|---|
| author | Hai-na TANG Xiao-la LIN Chun-jing HAN |
| author_facet | Hai-na TANG Xiao-la LIN Chun-jing HAN |
| author_sort | Hai-na TANG |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-69902bb73f014e49926168644e2840c9 |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2012-02-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-69902bb73f014e49926168644e2840c92025-01-14T06:31:06ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2012-02-013371459659950Duplicate elimination algorithm for data streams with SKIP Bloom filterHai-na TANGXiao-la LINChun-jing HANAccording 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.http://www.joconline.com.cn/zh/article/doi/1000-436X(2012)02-0007-08/data streamsduplicate eliminationBloom filterhash function |
| spellingShingle | Hai-na TANG Xiao-la LIN Chun-jing HAN Duplicate elimination algorithm for data streams with SKIP Bloom filter Tongxin xuebao data streams duplicate elimination Bloom filter hash function |
| title | Duplicate elimination algorithm for data streams with SKIP Bloom filter |
| title_full | Duplicate elimination algorithm for data streams with SKIP Bloom filter |
| title_fullStr | Duplicate elimination algorithm for data streams with SKIP Bloom filter |
| title_full_unstemmed | Duplicate elimination algorithm for data streams with SKIP Bloom filter |
| title_short | Duplicate elimination algorithm for data streams with SKIP Bloom filter |
| title_sort | duplicate elimination algorithm for data streams with skip bloom filter |
| topic | data streams duplicate elimination Bloom filter hash function |
| url | http://www.joconline.com.cn/zh/article/doi/1000-436X(2012)02-0007-08/ |
| work_keys_str_mv | AT hainatang duplicateeliminationalgorithmfordatastreamswithskipbloomfilter AT xiaolalin duplicateeliminationalgorithmfordatastreamswithskipbloomfilter AT chunjinghan duplicateeliminationalgorithmfordatastreamswithskipbloomfilter |