TY - GEN
T1 - Bloom filters, adaptivity, and the dictionary problem
AU - Bender, Michael A.
AU - Farach-Colton, Martín
AU - Goswami, Mayank
AU - Johnson, Rob
AU - McCauley, Samuel
AU - Singh, Shikha
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/11/30
Y1 - 2018/11/30
N2 - An approximate membership query data structure (AMQ)-such as a Bloom, quotient, or cuckoo filter-maintains a compact, probabilistic representation of a set S of keys from a universe U. It supports lookups and inserts. Some AMQs also support deletes. A query for x ∈ S returns PRESENT. A query for x ∉ S returns PRESENT with a tunable false-positive probability ϵ, and otherwise returns ABSENT. AMQs are widely used to speed up dictionaries that are stored remotely (e.g., on disk or across a network). The AMQ is stored locally (e.g., in memory). The remote dictionary is only accessed when the AMQ returns PRESENT. Thus, the primary performance metric of an AMQ is how often it returns ABSENT for negative queries. Existing AMQs offer weak guarantees on the number of false positives in a sequence of queries. The false-positive probability ϵ holds only for a single query. It is easy for an adversary to drive an AMQ's false-positive rate towards 1 by simply repeating false positives. This paper shows what it takes to get strong guarantees on the number of false positives. We say that an AMQ is adaptive if it guarantees a false-positive probability of ϵ for every query, regardless of answers to previous queries. We establish upper and lower bounds for adaptive AMQs. Our lower bound shows that it is impossible to build a small adaptive AMQ, even when the AMQ is immediately told whenever a query is a false positive. On the other hand, we show that it is possible to maintain an AMQ that uses the same amount of local space as a non-adaptive AMQ (up to lower order terms), performs all queries and updates in constant time, and guarantees that each negative query to the dictionary accesses remote storage with probability ϵ, independent of the results of past queries. Thus, we show that adaptivity can be achieved effectively for free.
AB - An approximate membership query data structure (AMQ)-such as a Bloom, quotient, or cuckoo filter-maintains a compact, probabilistic representation of a set S of keys from a universe U. It supports lookups and inserts. Some AMQs also support deletes. A query for x ∈ S returns PRESENT. A query for x ∉ S returns PRESENT with a tunable false-positive probability ϵ, and otherwise returns ABSENT. AMQs are widely used to speed up dictionaries that are stored remotely (e.g., on disk or across a network). The AMQ is stored locally (e.g., in memory). The remote dictionary is only accessed when the AMQ returns PRESENT. Thus, the primary performance metric of an AMQ is how often it returns ABSENT for negative queries. Existing AMQs offer weak guarantees on the number of false positives in a sequence of queries. The false-positive probability ϵ holds only for a single query. It is easy for an adversary to drive an AMQ's false-positive rate towards 1 by simply repeating false positives. This paper shows what it takes to get strong guarantees on the number of false positives. We say that an AMQ is adaptive if it guarantees a false-positive probability of ϵ for every query, regardless of answers to previous queries. We establish upper and lower bounds for adaptive AMQs. Our lower bound shows that it is impossible to build a small adaptive AMQ, even when the AMQ is immediately told whenever a query is a false positive. On the other hand, we show that it is possible to maintain an AMQ that uses the same amount of local space as a non-adaptive AMQ (up to lower order terms), performs all queries and updates in constant time, and guarantees that each negative query to the dictionary accesses remote storage with probability ϵ, independent of the results of past queries. Thus, we show that adaptivity can be achieved effectively for free.
KW - Adaptive data structures
KW - Approximate membership query data structures
KW - Bloom filters
KW - Dictionary data structures
UR - http://www.scopus.com/inward/record.url?scp=85059802049&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85059802049&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2018.00026
DO - 10.1109/FOCS.2018.00026
M3 - Conference contribution
AN - SCOPUS:85059802049
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 182
EP - 193
BT - Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
A2 - Thorup, Mikkel
PB - IEEE Computer Society
T2 - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
Y2 - 7 October 2018 through 9 October 2018
ER -