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

Bernard Chazelle; Joe Kilian; Ronitt Rubinfeld; Ayellet Tal

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

Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, Ayellet Tal

Research output: Contribution to conference › Paper › peer-review

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 language	English (US)
Pages	30-39
Number of pages	10
State	Published - 2004
Event	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States Duration: Jan 11 2004 → Jan 13 2004

Other

Other	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	New Orleans, LA.
Period	1/11/04 → 1/13/04

All Science Journal Classification (ASJC) codes

Software
General Mathematics

Cite this

@conference{09482def41d54146ae0505bbb097edf1,

title = "The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables",

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.",

author = "Bernard Chazelle and Joe Kilian and Ronitt Rubinfeld and Ayellet Tal",

year = "2004",

language = "English (US)",

pages = "30--39",

note = "Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 11-01-2004 Through 13-01-2004",

}

TY - CONF

T1 - The Bloomier Filter

T2 - Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms

AU - Chazelle, Bernard

AU - Kilian, Joe

AU - Rubinfeld, Ronitt

AU - Tal, Ayellet

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=1842473700&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1842473700&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:1842473700

SP - 30

EP - 39

Y2 - 11 January 2004 through 13 January 2004

ER -

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

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this