The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables

Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, Ayellet Tal

Research output: Contribution to conferencePaper

221 Scopus citations

Abstract

We introduce the Bloomier filter, a data structure for compactly encoding a function with static support in order to support approximate evaluation queries. Our construction generalizes the classical Bloom filter, an ingenious hashing scheme heavily used in networks and databases, whose main attribute - space efficiency - is achieved at the expense of a tiny false-positive rate. Whereas Bloom filters can handle only set membership queries, our Bloomier filters can deal with arbitrary functions. We give several designs varying in simplicity and optimality, and we provide lower bounds to prove the (near) optimality of our constructions.

Original languageEnglish (US)
Pages30-39
Number of pages10
StatePublished - Apr 15 2004
EventProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
Duration: Jan 11 2004Jan 13 2004

Other

OtherProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityNew Orleans, LA.
Period1/11/041/13/04

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., Kilian, J., Rubinfeld, R., & Tal, A. (2004). The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables. 30-39. Paper presented at Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA., United States.