TY - GEN
T1 - Approximate Range Emptiness in Constant Time and Optimal Space
AU - Goswami, Mayank
AU - Jørgensen, Allan Grønlund
AU - Larsen, Kasper Green
AU - Pagh, Rasmus
N1 - Conference code: 15
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
M3 - Article in proceedings
SP - 769
EP - 775
BT - Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '15
PB - Society for Industrial and Applied Mathematics
T2 - ACM-SIAM Symposium on Discrete Algorithms
Y2 - 4 January 2015 through 6 January 2015
ER -