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.
|Number of pages
|Published - 2004
|Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
Duration: Jan 11 2004 → Jan 13 2004
|Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
|New Orleans, LA.
|1/11/04 → 1/13/04
All Science Journal Classification (ASJC) codes
- General Mathematics