Set reconciliation based on counting Bloom filters
A new set reconciliation algorithm was presented,which called counting-Bloom-filter based set reconciliation(CBFSR).This method represented sets S<sub>A</sub> and S<sub>B</sub> as counting Bloom filters,subtracts S<sub>A</sub>'s counting Bloom filter from S&l...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2012-08-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/1000-436X(2012)08-0119-09/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | A new set reconciliation algorithm was presented,which called counting-Bloom-filter based set reconciliation(CBFSR).This method represented sets S<sub>A</sub> and S<sub>B</sub> as counting Bloom filters,subtracts S<sub>A</sub>'s counting Bloom filter from S<sub>B</sub>'s counting Bloom filter,the differences denoted CBF(S<sub>B</sub>)−CBF(S<sub>A</sub>),then determined S<sub>B</sub>−S<sub>A</sub> elements in S<sub>B</sub> with CBF(S<sub>B</sub>)−CBF(S<sub>A</sub>),and finally performed union operation on S<sub>B</sub>−S<sub>A</sub> and S<sub>A</sub>.Simulation resdts show counting-Bloom-filter based set reconciliation combines the advantages of exact set reconciliation and approximate set reconciliation,besides gaining all S<sub>B</sub>−S<sub>A</sub> elements with single-round messgage exchanges,it can apply to update-intensive distributed systems because counting Bloom filters support element deletion operation. |
|---|---|
| ISSN: | 1000-436X |