کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
448320 693558 2013 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Efficient false positive free set synchronization using an extended bloom filter approach
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر شبکه های کامپیوتری و ارتباطات
پیش نمایش صفحه اول مقاله
Efficient false positive free set synchronization using an extended bloom filter approach
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer Communications - Volume 36, Issues 10–11, June 2013, Pages 1245–1254
نویسندگان
, , ,