Distance Sensitive Bloom Filters Without False Negatives

DOI10.1137/1.9781611974782.17zbMATH Open1410.68100arXiv1607.05451OpenAlexW4212907756MaRDI QIDQ4575754FDOQ4575754

Mayank Goswami, Rasmus Pagh, Francesco Silvestri, Johan Sivertsen

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: A Bloom filter is a widely used data-structure for representing a set

S

and answering queries of the form "Is

x

in

S

?". By allowing some false positive answers (saying "yes" when the answer is in fact `no') Bloom filters use space significantly below what is required for storing

S

. In the distance sensitive setting we work with a set

S

of (Hamming) vectors and seek a data structure that offers a similar trade-off, but answers queries of the form "Is

x

close to an element of

S

?" (in Hamming distance). Previous work on distance sensitive Bloom filters have accepted false positive and false negative answers. Absence of false negatives is of critical importance in many applications of Bloom filters, so it is natural to ask if this can be also achieved in the distance sensitive setting. Our main contributions are upper and lower bounds (that are tight in several cases) for space usage in the distance sensitive setting where false negatives are not allowed.

Full work available at URL: https://arxiv.org/abs/1607.05451

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Data structures (68P05)

Cited In (2)

This page was built for publication: Distance Sensitive Bloom Filters Without False Negatives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575754)