Invertible Bloom lookup tables (IBLTs) are probabilistic (hashing- based) data structures with the following property: they can represent sets so that the differences between two sets can be recovered from their representations provided that the number of differences is small. Remarkably, in this framework, the size of the IBLTs depends only on the number of differences and does not depend on the size of the underlying sets which can be arbitrarily large. Therefore, IBLTs can act as sketches supporting set difference recovery (set reconciliation).

In this talk, we will introduce IBLTs and their possible variants, together with an associated mathematical background. We explain how IBLTs apply to set reconciliation. We then briefly present the main result of our work (just accepted to ICALP) improving performance guarantees of IBLTs. Then we talk about possible application of IBLTs to comparison of genomic datasets mentioning some related earlier results we presented to WABI'22.