2014/07/10 by Mayank Goswami, Goswami, Mayank, Allan Grønlund +5
Computer Science · #Algorithms and Data Compression #Caching and Content Delivery #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.1407.2907
arxiv created 2014/07/10 · openalex publication_date 2014/07/10 · arxiv updated 2014/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies the ε-approximate range emptiness problem, where the task is to represent a set S of n points from \0,…,U-1\ and answer emptiness queries of the form "[a ; b]∩ S ≠ ∅ ?" with a probability of false positives allowed. This generalizes the functionality of Bloom filters from single point queries to any interval length L. Setting the false positive rate to ε/L and performing L queries, Bloom filters yield a solution to this problem with space O(n \lg(L/ε)) bits, false positive probability bounded by ε for intervals of length up to L, using query time O(L \lg(L/ε)). Our first contribution is to show that the space/error trade-off cannot be improved asymptotically: Any data structure for answering approximate range emptiness queries on intervals of length up to L with false positive probability ε, must use space Ω(n \lg(L/ε)) - O(n) bits. On the positive side we show that the query time can be improved greatly, to constant time, while matching our space lower bound up to a lower order additive term. This result is achieved through a succinct data structure for (non-approximate 1d) range emptiness/reporting queries, which may be of independent interest.