Affordable Access

Publisher Website

Efficient false positive free set synchronization using an extended bloom filter approach

Authors
Journal
Computer Communications
0140-3664
Publisher
Elsevier
Volume
36
Identifiers
DOI: 10.1016/j.comcom.2013.03.007
Keywords
  • Set Reconciliation
  • Opportunistic Networks
  • Bloom Filter
Disciplines
  • Communication

Abstract

Abstract Synchronization between two sets is an important requirement for many distributed applications. A basic prerequisite is to find out which elements of set A are not in set B and vice versa. A very space efficient data structure for such membership queries that has been used a lot in networking applications is the Bloom filter. Unfortunately, the Bloom filter owes its high efficiency to the fact that there is a chance of false positives when querying the filter. This precludes the adoption of Bloom filters in applications that cannot tolerate such errors. In this paper we present an approach that augments Bloom filters with a trie-based mechanism that deterministically and efficiently finds the false positives after using the Bloom filter to synchronize two sets. We show that the added communication overhead for our approach is negligible compared to the overhead of a plain Bloom filter.

There are no comments yet on this publication. Be the first to share your thoughts.