A Space Lower Bound for Approximate Membership with Duplicate Insertions or Deletions of Nonelements

Aryan Agarwala, Guy Even · 2024

Read A Space Lower Bound for Approximate Membership with Duplicate Insertions or Deletions of Nonelements by Aryan Agarwala, Guy Even (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-19249.txt.

Introduction

Aryan Agarwala and Guy Even prove that two common limits on approximate membership data structures do real work. Structures that answer membership queries with false positives most often bar duplicate insertions. They also bar the deletion of items that are not members. Under those rules, known designs use close to the least space in theory.

Agarwala and Even show that if both limits are lifted, the space needed jumps. Any structure for a set under any duplicate insertions and deletions of non-members needs far more bits. The count scales with the logarithm of the number of sets that can be drawn from the universe. The bound splits the well-behaved setting from the fully general one. The rules are not mere ease of use. They are what makes near-best space possible.

Catalog record

CREATORAryan Agarwala, Guy Even
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-19249

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Space Lower Bound for Approximate Membership with Duplicate Insertions or Deletions of Nonelements Aryan Agarwala, Guy Even Abstract Designs of data structures for approximate membership queries with false-positive errors that support both insertions and deletions stipulate the following two conditions: (1) Duplicate insertions are prohibited, i.e., it is prohibited to insert an element x x if x x is currently a member of the dataset. (2) Deletions of nonelements are prohibited, i.e., it is prohibited to delete x x if x x is not currently a member of the dataset. Under these conditions, the space required for the approximate representation of a datasets of cardinality n n with a false-positive probability of ϵ + \epsilon^{+} is at most ( 1 + o ⁡ ( 1 ) ) ​ n ⋅ log 2 ⁡ ( 1 / ϵ + ) + O ⁡ ( n ) (1+o(1))n\cdot\log_{2}(1/\epsilon^{+})+O(n) bits [Bender et al., 2018; Bercea and Even, 2019]. We prove that if these conditions are lifted, then the space required for the approximate representation of datasets of cardinality n n from a universe of cardinality u u is at least 1 2 ⋅ ( 1 − ϵ + − 1 n ) ⋅ log ⁡ ( u n ) − O ⁡ ( n ) \frac{1}{2}\cdot(1-\epsilon^{+}-\frac{1}{n})\cdot\log\binom{u}{n}-O(n) bits. Keywords— Data Structures, Approximate Membership, Bloom Filter, Dynamic Filters 1 Introduction Dynamic data structures for approximate membership store an approximate representation of a dataset subject to insert and delete operations. The output of such data structures for membership queries may be wrong, specifically false-positive errors are allowed. We refer to such data structures in short as dynamic filters . 1 1 1 Static filters store an approximate representation of a fixed dataset. Incremental filters support insertions but not deletions. We refer to static/incremental/dynamic filters simply as filters. Filters are randomized data structures, and the probability of a false-positive error is bounded by a (tunable) parameter denoted by \epsilon^{+} . The main advantage of the approximate representation used by a filter over exact error-free representation is the reduction in space (i.e., number of bits needed to store the representation). Indeed, consider a universe of cardinality u and datasets of cardinality n . Because there are \binom{u}{n} different subsets of u cardinality n , it follows that exact representation of such datasets requires at least \log\binom{u}{n}\geq n\log(u/n) bits. 2 2 2 All logarithms in this paper are base 2 . On the other hand, dynamic filters with a false-positive error probability of at most \epsilon^{+} require only (1+o(1))n\log(1/\epsilon^{+})+O(n) bits [ BFCG+18 , BE19 , BEED24 ] . If \log(1/\epsilon^{+}) is much smaller than \log(u/n) , then the space of a filter is smaller than the space required for exact representation. Such a reduction in space often enables the storage of the approximate representation in fast yet small memory [ Blo70 ] which is advantageous in many applications (see [ BM04 ] for a survey). Dynamic filter designs, such as Cuckoo filters [ FAKM14 , Epp16 ] , Quotient filters [ PPR05 , BFCJ+11 ] , Broom filters [ BFCG+18 ] , and [ BE19 ] are based on the framework suggested by Carter et al. [ CFG+78 ] . Carter et al. presented a general framework for incremental filters that support insertions and approximate membership queries. To obtain a false-positive error probability of at most \epsilon^{+} , the framework hashes the n keys to strings of \log(n/\epsilon^{+}) bits. The images of the keys are called fingerprints and are stored in a dictionary (i.e., hashtable) that supports exact representation of datasets [ ANS10 ] . That is, an \ins(x) operation to the filter translates to an \ins(\FP(x)) to the dictionary, where \FP(x) is the fingerprint of x . A query for x simply searches for \FP(x) in the dictionary. To support deletions in this framework, the dictionary needs to store multisets of fingerprints [ PPR05 ] (i.e., the multiplicity of a fingerprint equals the number of elements in the dataset that map to that fingerprint). When a \del(x) operation is issued to the filter, the multiplicity of \FP(x) in the dictionary is decremented (e.g., deletion of a copy of \FP(x) ). For a dataset S , we refer to x\in S as an element and to x\not\in S as a nonelement . Previous designs of dynamic filters [ FAKM14 , PPR05 , BFCJ+11 , BFCG+18 , BE19 , EM24 ] stipulate the following conditions: 1. Duplicate insertions are prohibited . One may not perform an \ins(x) operation if x is an element (i.e., already an element in the dataset). 2. Deletions of nonelements are prohibited. One may not perform a \del(x) operation if x is a nonelement (i.e. not an element in the dataset). These two conditions arise from the limitations of the framework for designing a dynamic filter by storing a multiset of fingerprints. The reason for prohibiting duplicate insertions is the inability of the framework to distinguish between a duplicate insertion of an element x and an insertion of a nonelement x whose fingerprint collides with a fingerprint of an element y . Observe that these two events should have a different influence on the approximate representation of the dataset: (1) An \ins(x) operation, where x is an nonelement, y is an element, and \FP(y)=\FP(x) should increment the multiplicity of \FP(x) . Otherwise, a subsequent \del(y) operation (that decrements the multiplicity of \FP(y) ) would zero the multiplicity of \FP(y) and thus introduce a false-negative error for \query(x) . (2) A duplicate insertion \ins(x) does not modify the dataset and should be ignored. In other words, if the multiplicity of \FP(x) is incremented, then a \del(x) followed by \query(x) would definitely return a false-positive error. The reason for prohibiting a deletion of a nonelement x is that there might exist an element y such that \FP(x)=\FP(y) . Because the framework cannot distinguish between a deletion of x and a deletion of y , a \del(x) operation would delete \FP(y) , leading to a false-negative error for \query(y) . In this paper we address the following question: Is it possible to design a small space dynamic filter that permits duplicate-insertions or deletions-of-nonelements? We answer this question negatively (see Theorem 14 for a precise formulation), and prove that if a dynamic filter permits duplicate-insertions or deletions-of-nonelements, then the space required to store the approximate representation of the dataset is \Omega\mathopen{}\mathclose{{\left({\binom{u}{n}}\right)}} bits (if u\geq 2n ). This means that the space of such a filter is at least a constant fraction of the space required for exact representation (i.e., the fraction is at least (1-\epsilon^{+}-o(1))/2 if deletions-of-nonelements are allowed). The lower bound does not make assumptions about the running time of the filter or the number of memory accesses. Moreover, the lower bound does not count the random bits of the filter or temporary memory used for processing operations. The lower bound holds with respect to an oblivious adversary. 1.1 Related Work 1.1.1 Upper Bounds The first filter that supports insertions and approximate membership queries (but no deletions) was presented by Bloom [ Blo70 ] . Carter et al [ CFG+78 ] presented a general framework for filters that support insertions and approximate membership queries. The framework suggests to

Read the complete text