A Bloom filter is a space-efficient data structure that answers set membership queries with some chance of a false positive. We introduce the problem of designing generalizations of Bloom filters designed to answer queries of the form, "Is x close to an element of S?" where closeness is measured under a suitable metric. Such a data structure would have several natural applications in networking and database applications. We demonstrate how appropriate data structures can be designed using locality-sensitive hash functions as a building block, and we specifically analyze the performance of a natural scheme under the Hamming metric.
Kirscsh and Mitzenmacher REF propose a generalization of the Bloom filter to answer queries of the form "Is x close to an element of the filter?" where closeness or similarity is defined under the hamming metric.
Distance-Sensitive Bloom Filters
In Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments (ALENEX
Computer Science