Approximate Range Emptiness in Constant Time and Optimal Space

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

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

16 Citations (Scopus)

Abstract

This paper studies the \emph{ε-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 \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 ε/L and performing L queries, Bloom filters yield a solution to this problem with space O(nlg(L/ε)) bits, false positive probability bounded by ε for intervals of length up to L, using query time O(Llg(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 Ω(nlg(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.

Original languageEnglish
Title of host publicationProceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '15
Number of pages7
PublisherSociety for Industrial and Applied Mathematics
Publication date2015
Pages 769-775
Publication statusPublished - 2015
EventACM-SIAM Symposium on Discrete Algorithms - San Diego, United States
Duration: 4 Jan 20156 Jan 2015
Conference number: 15

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
Number15
Country/TerritoryUnited States
CitySan Diego
Period04/01/201506/01/2015

Fingerprint

Dive into the research topics of 'Approximate Range Emptiness in Constant Time and Optimal Space'. Together they form a unique fingerprint.

Cite this