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!
|
| _version_ | 1841539903699025920 |
|---|---|
| author | Xiao-mei TIAN Da-fang ZHANG Kun XIE Can HU Xiao-bo YANG Chang-qiong SHI |
| author_facet | Xiao-mei TIAN Da-fang ZHANG Kun XIE Can HU Xiao-bo YANG Chang-qiong SHI |
| author_sort | Xiao-mei TIAN |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-610d2af334d24e60bd4b29faa449cc1c |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2012-08-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-610d2af334d24e60bd4b29faa449cc1c2025-01-14T06:32:51ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2012-08-013311912759664908Set reconciliation based on counting Bloom filtersXiao-mei TIANDa-fang ZHANGKun XIECan HUXiao-bo YANGChang-qiong SHIA 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.http://www.joconline.com.cn/zh/article/doi/1000-436X(2012)08-0119-09/set reconciliationcounting Bloom filterdistributed systemscontent delivery |
| spellingShingle | Xiao-mei TIAN Da-fang ZHANG Kun XIE Can HU Xiao-bo YANG Chang-qiong SHI Set reconciliation based on counting Bloom filters Tongxin xuebao set reconciliation counting Bloom filter distributed systems content delivery |
| title | Set reconciliation based on counting Bloom filters |
| title_full | Set reconciliation based on counting Bloom filters |
| title_fullStr | Set reconciliation based on counting Bloom filters |
| title_full_unstemmed | Set reconciliation based on counting Bloom filters |
| title_short | Set reconciliation based on counting Bloom filters |
| title_sort | set reconciliation based on counting bloom filters |
| topic | set reconciliation counting Bloom filter distributed systems content delivery |
| url | http://www.joconline.com.cn/zh/article/doi/1000-436X(2012)08-0119-09/ |
| work_keys_str_mv | AT xiaomeitian setreconciliationbasedoncountingbloomfilters AT dafangzhang setreconciliationbasedoncountingbloomfilters AT kunxie setreconciliationbasedoncountingbloomfilters AT canhu setreconciliationbasedoncountingbloomfilters AT xiaoboyang setreconciliationbasedoncountingbloomfilters AT changqiongshi setreconciliationbasedoncountingbloomfilters |