Improving the performance of Invertible Bloom Lookup Tables

Salvatore Pontarelli*, Pedro Reviriego, Michael Mitzenmacher

*Corresponding author for this work

Research output: Contribution to journalArticle (Academic Journal)peer-review

6 Citations (Scopus)

Abstract

Invertible Bloom Lookup Tables (IBLTs) have been recently introduced as an extension of traditional Bloom filters. IBLTs store key-value pairs. Unlike traditional Bloom filters, IBLTs support both a lookup operation (given a key, return a value) and an operation that lists out all the key-value pairs stored. One issue with IBLTs is that there is a probability that a lookup operation will return "not found" for a key. In this paper, a technique to reduce this probability without affecting the storage requirement and only moderately increasing the search time is presented and evaluated. The results show that it can significantly reduce the probability of not returning a value that is actually stored in the IBLT. The overhead of the modified search procedure, compared to the standard IBLT search procedure, is small and has little impact on the average search time.

Original languageEnglish
Pages (from-to)185-191
Number of pages7
JournalInformation Processing Letters
Volume114
Issue number4
DOIs
Publication statusPublished - 1 Apr 2014

Keywords

  • Algorithms
  • Bloom filters
  • Data structures
  • Hash

Fingerprint

Dive into the research topics of 'Improving the performance of Invertible Bloom Lookup Tables'. Together they form a unique fingerprint.

Cite this