2024/12/26 by Aryan Agarwala, Agarwala, Aryan, Guy Even +1
Computer Science · Mathematics · #Advanced Topology and Set Theory #Data Structures and Algorithms (cs.DS) #E.1 #E.2 #FOS: Computer and information sciences #Mathematical Approximation and Integration #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2412.19249
openalex publication_date 2024/12/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 if x is currently a member of the dataset. (2) Deletions of nonelements are prohibited, i.e., it is prohibited to delete x if 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 with a false-positive probability of ε+ is at most (1+o(1))n⋅log2 (1/ε+) + 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 from a universe of cardinality u is at least \frac 12 ⋅ (1-ε+ -\frac 1n)⋅ log \binomun -O(n) bits.