Invertible Bloom Lookup Tables and Applications

Monday, March 16, 2015 - 2:50pm - 3:30pm
Klaus 2443
Michael Mitzenmacher (Harvard University)
We provide an overview and some recent work on Invertible Bloom Lookup Tables (IBLTs) and their applications. The Invertible Bloom Lookup Table is a simple hash-based data structure that allows insertion, deletion, and under suitable conditions listing of inserted items, with a small amount of space. Such data structures have natural applications to set reconciliation problems, which can form the basis for solutions for distributed database reconciliation. We also describe recent extensions to multi-party reconciliation settings, and how this related to connections between IBLTs and various coding techniques.