Comparing Set Reconciliation Methods Based on Bloom Filters and Their Variants  

作　　者：Zhiyao Hu Xiaoqiang Teng Deke Guo Bangbang Ren Pin Lv Zhong Liu 

机构地区：[1]College of Information System and Management,National University of Defense Technology,Changsha 410073,China [2]School of Computer,Electronics and Information,Guangxi University,Nanning 530004,China.

出　　处：《Tsinghua Science and Technology》2016年第2期157-167,共11页清华大学学报（自然科学版（英文版）

基　　金：supported in part by the National Natural Science Foundation of China(Nos.61422214 and 61402513);the National Key Basic Research and Development(973)Program of China(No.2014CB347800);the Program for New Century Excellent Talents in University and Distinguished Young Scholars of National University of Defense Technology(No.JQ14-05-02);the Preliminary Research Funding of National University of Defense Technology(No.ZDYYJCYJ20140601)

摘　　要：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.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.

关 键 词：set reconciliation bloom filter communication overheads 

分 类 号：TN713[电子电信—电路与系统]