AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (1.3 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Comparing Set Reconciliation Methods Based on Bloom Filters and Their Variants

Zhiyao Hu, Xiaoqiang Teng, Deke Guo( ), Bangbang Ren, Pin Lv, Zhong Liu
College of Information System and Management, National University of Defense Technology, Changsha 410073, China.
School of Computer, Electronics and Information, Guangxi University, Nanning 530004, China.
Show Author Information

Abstract

Set reconciliation between two nodes is widely used in network applications. The basic idea is that each member of a node pair has an object set and seeks to deliver its unique objects to the other member. The Standard Bloom Filter (SBF) and its variants, such as the Invertible Bloom Filter (IBF), are effective approaches to solving the set reconciliation problem. The SBF-based method requires each node to represent its objects using an SBF, which is exchanged with the other node. A receiving node queries the received SBF against its local objects to identify the unique objects. Finally, each node exchanges its unique objects with the other node in the node pair. For the IBF-based method, each node represents its objects using an IBF, which is then exchanged. A receiving node subtracts the received IBF from its local IBF so as to decode the different objects between the two sets. Intuitively, it would seem that the IBF-based method, with only one round of communication, entails less communication overhead than the SBF-based method, which incurs two rounds of communication. Our research results, however, indicate that neither of these two methods has an absolute advantages over the others. In this paper, we aim to provide an in-depth understanding of the two methods, by evaluating and comparing their communication overhead. We find that the best method depends on parameter settings. We demonstrate that the SBF-based method outperforms the IBF-based method in most cases. But when the number of different objects in the two sets is below a certain threshold, the IBF-based method outperforms the SBF-based method.

Keywords

set reconciliationbloom filtercommunication overheads

References

[1]
Satyanarayanan M., A highly available file system for a distributed workstation environment, in Proc. of the Second IEEE Workshop on Workstation Operating Systems, Pacic Grove, CA, USA, 1989.
[2]
Demers A. J., Greene D. H., Hause C., Irish W., and Larson J., Epidemic algorithms for replicated database maintenance, in Proc. of 6th Annual ACM Symposium on Principles of Distributed Computing, Vancouver, Canada, 1987, pp. 1-12.
[3]
Starobinski D., Trachtenberg A., and Agarwal S., Efficient pda synchronization, IEEE Trans. on Mobile Computing, vol. 1, no. 2, 2003.
Crossref Google Scholar
[4]
Wu K., Tan H., Liu Y., Zhang J., Zhang Q., and Ni L. M., Side channel: Bits over interference, IEEE Transactions on Mobile Computing, vol. 11, no. 8, pp. 1317–1330, 2012.
Crossref Google Scholar
[5]
van Renesse R., Minsky Y., and Hayden M., A gossip-style failure detection service, presented at the IFIP International Conference on Distributed Systems Platforms and Open Distributed, London, UK, 1998.
[6]
van Renesse R., Scalable and secure resource location, in Proc. of 33rd Annual Hawaii International Conference on System Sciences, 2000.
[7]
Wu K., Li H., Wang L., Yi Y., Liu Y., Chen D., Luo X., Zhang Q., and Ni Li. M., hJam: Attachment transmission in WLANs, IEEE Transactions on Mobile Computing, vol. 12, no. 12, pp. 2334–2345, 2013.
Crossref Google Scholar
[8]
Li H., Wu K., Zhang Q., and Ni L. M., CUTS: Improving channel utilization in both time and spatial domains in WLAN, IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 6, pp. 1413–1423, 2014.
Crossref Google Scholar
[9]
Wu K., Xiao J., Yi Y., Chen D., Luo X., and Ni L. M., CSI-based indoor localization, IEEE Transactions on Parallel and Distributed Systems, vol. 24, no. 7, pp. 1300–1309, 2013.
Crossref Google Scholar
[10]
Bloom B. H., Space/time trade-offs in hash coding with allowable errors, ACM Commun., vol. 13, no. 7, pp. 422–426, 1970
Crossref Google Scholar
[11]
Eppstein D., Goodrich M. T., Uyeda F., and Varghese G., What’s the difference? Efficient set reconciliation without prior context, in Proc. of ACM SIGCOMM, Ontario, Canada, 2011, pp. 218-229.
Crossref
[12]
Guo D., He Y., and Yang P., Receiver-oriented design of bloom filters for data-centric routing, Elsevier Computer Networks Journal, vol. 54, no. 1, pp. 165–174, 2010.
Crossref Google Scholar
[13]
Guo D., Wu J., Chen H., Yuan Y., and Luo X., The dynamic bloom filters, IEEE Trans. on Knowledge and Data Engineering, vol. 22, no. 1, pp. 120–133, 2010.
Crossref Google Scholar
[14]
Tarkoma S., Rothenberg C. E., and Lagerspetz E., Theory and practice of bloom filters for distributed systems, IEEE Communications Surveys and Tutorials, vol. 14, no. 1, pp. 131–155, 2012.
Crossref Google Scholar
[15]
Goodrich M. T. and Mitzenmacher M., Invertible bloom lookup tables: 1101.2245, 2011.
Crossref
[16]
Fan L., Cao P., Almeida J., and Broder A., Summary cache: A scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking, vol. 8, no. 3, pp. 281–293, 2000.
Crossref Google Scholar
[17]
Guo D. and Li M., Set reconciliation via counting bloom filters, IEEE Trans. on Knowledge and Data Engineering, vol. 25, no. 10, pp. 2367–2380, 2013.
Crossref Google Scholar
[18]
Guo D., Liu Y., Li X., and Yang P., False negative problem of counting bloom filter, IEEE Trans. on Knowledge and Data Engineering, vol. 22, no. 5, pp. 651–664, 2010.
Crossref Google Scholar
[19]
Broder A. and Mitzenmacher M., Network applications of bloom filters: A survey, Internet Mathematics, vol. 1, no. 4, pp. 485–509, 2004.
Crossref Google Scholar
[20]
Eppstein D. and Goodrich M., Straggler identification in round-trip data streams via newton’s identities and invertible bloom filter, IEEE Trans. on Knowledge and Data Engineering, vol. 23, no. 2, pp. 297–306, 2011.
Crossref Google Scholar
[21]
Bollobas B., Random Graphs. New York, NY, USA: Academy Press, 1985.
[22]
Dietzfelbinger M., Goerdt A., Mitzenmacher M., Montanari A., Pagh R., and Rink M., Tight thresholds for cuckoo hashing via XORSAT, in Proc. of ICALP, 2010, pp. 213-225.
Crossref
[23]
Molloy M., The pure literal rule threshold and cores in random hypergraphs, in Proc. of the 43rd Annual ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 672-681.
[24]
Christensen K., Roginsky A., and Jimeno M., A new analysis of the false positive rate of a bloom filter, Inf. Processing Letters, vol. 110, no. 21, pp. 944–949, 2010.
Crossref Google Scholar
[25]
Bose P., Guo H., Kranakis E., Maheshwari A., Morin P., Morrison J., Smid M., and Tang Y., On the false-positive rate of bloom filters, School of Comp. Sci., Carleton Univ., New York, USA, 2007.
Tsinghua Science and Technology
Volume 21 Issue 2,
April 2016
Pages 157-167
DOI: 10.1109/TST.2016.7442499
Cite this article:
Hu Z, Teng X, Guo D, et al. Comparing Set Reconciliation Methods Based on Bloom Filters and Their Variants. Tsinghua Science and Technology, 2016, 21(2): 157-167. https://doi.org/10.1109/TST.2016.7442499

543

Views

83

Downloads

2

Crossref

N/A

Web of Science

3

Scopus

0

CSCD

Altmetrics
Received: 12 January 2016
Accepted: 22 February 2016
Published: 31 March 2016
© The author(s) 2016
Return