The space complexity of 2-dimensional approximate range counting

DOI10.1137/1.9781611973105.19MaRDI QIDQ5741727zbMATH OpenOpenAlexFDO

Authors Zhewei Wei, Ke Yi

Publication date 15 May 2019

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

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

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We study the problem of $2$-dimensional orthogonal range counting with additive error. Given a set $P$ of $n$ points drawn from an $nimesn$ grid and an error parameter $eps$, the goal is to build a data structure, such that for any orthogonal range $R$, it can return the number of points in $PcapR$ with additive error $epsn$. A well-known solution for this problem is the {em $eps$-approximation}, which is a subset $AsubseteqP$ that can estimate the number of points in $PcapR$ with the number of points in $AcapR$. It is known that an $eps$-approximation of size $O(frac1epslo{g}^{2.5}frac1eps)$ exists for any $P$ with respect to orthogonal ranges, and the best lower bound is $Omega(frac1epslogfrac1eps)$. The $eps$-approximation is a rather restricted data structure, as we are not allowed to store any information other than the coordinates of the points in $P$. In this paper, we explore what can be achieved without any restriction on the data structure. We first describe a simple data structure that uses $O(frac1eps(lo{g}^{2}frac1eps+logn))$ bits and answers queries with error $epsn$. We then prove a lower bound that any data structure that answers queries with error $epsn$ must use $Omega(frac1eps(lo{g}^{2}frac1eps+logn))$ bits. Our lower bound is information-theoretic: We show that there is a collection of $2^{Omega(nlogn)}$ point sets with large {em union combinatorial discrepancy}, and thus are hard to distinguish unless we use $Omega(nlogn)$ bits.

Recommendations

• Tight space bounds for two-dimensional approximate range counting
• Data structures for approximate orthogonal range counting
• Adaptive and approximate orthogonal range counting
• Adaptive and approximate orthogonal range counting
• Approximate range searching

Cited in

(8)

• The space complexity of approximating the frequency moments
• The Encoding Complexity of Two Dimensional Range Minimum Data Structures
• Data structures for approximate orthogonal range counting
• Tight space bounds for two-dimensional approximate range counting
• Approximate range counting revisited
• Approximate range emptiness in constant time and optimal space
• scientific article; zbMATH DE number 7740901 (Why is no real title available?)
• Range counting over multidimensional data streams

This page was built for publication: The space complexity of 2-dimensional approximate range counting

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