Approximate range emptiness in constant time and optimal space

DOI10.1137/1.9781611973730.52MaRDI QIDQ5362992zbMATH OpenOpenAlexFDO

Authors Mayank Goswami, Allan Grønlund, Kasper Green Larsen, Rasmus Pagh

Publication date 5 October 2017

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

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

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Abstract: This paper studies the emph{$varepsilon$-approximate range emptiness} problem, where the task is to represent a set $S$ of $n$ points from $0,ldots,U-1$ and answer emptiness queries of the form "$[a;b]capSeqemptyset$ ?" with a probability of emph{false positives} allowed. This generalizes the functionality of emph{Bloom filters} from single point queries to any interval length $L$. Setting the false positive rate to $varepsilon/L$ and performing $L$ queries, Bloom filters yield a solution to this problem with space $O(nlg(L/varepsilon))$ bits, false positive probability bounded by $varepsilon$ for intervals of length up to $L$, using query time $O(Llg(L/varepsilon))$. 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 $varepsilon$, must use space $Omega(nlg(L/varepsilon))-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.

Recommendations

• An optimal bloom filter replacement
• A space lower bound for dynamic approximate membership data structures
• The space complexity of 2-dimensional approximate range counting
• Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)
• Approximate range searching

Cited in

(6)

• Dynamic relative compression, dynamic partial sums, and substring concatenation
• Range Majority in Constant Time and Linear Space
• Succinct dynamic one-dimensional point reporting
• Succinct color searching in one dimension
• Bloom maps
• A space lower bound for dynamic approximate membership data structures

This page was built for publication: Approximate range emptiness in constant time and optimal space

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