Towards tight lower bounds for range reporting on the RAM

DOI10.4230/LIPICS.ICALP.2016.92zbMATH Open1388.68086arXiv1411.0644OpenAlexW2963321552MaRDI QIDQ4598233FDOQ4598233

Authors: Allan Grønlund, Kasper Green Larsen 

Publication date: 19 December 2017

Abstract: In the orthogonal range reporting problem, we are to preprocess a set of $n$ points with integer coordinates on a $UimesU$ grid. The goal is to support reporting all $k$ points inside an axis-aligned query rectangle. This is one of the most fundamental data structure problems in databases and computational geometry. Despite the importance of the problem its complexity remains unresolved in the word-RAM. On the upper bound side, three best tradeoffs exists: (1.) Query time $O(lglgn+k)$ with $O(nl{g}^{varepsilon}n)$ words of space for any constant $varepsilon>0$. (2.) Query time $O((1+k)lglgn)$ with $O(nlglgn)$ words of space. (3.) Query time $O((1+k)l{g}^{varepsilon}n)$ with optimal $O(n)$ words of space. However, the only known query time lower bound is $Omega(loglogn+k)$, even for linear space data structures. All three current best upper bound tradeoffs are derived by reducing range reporting to a ball-inheritance problem. Ball-inheritance is a problem that essentially encapsulates all previous attempts at solving range reporting in the word-RAM. In this paper we make progress towards closing the gap between the upper and lower bounds for range reporting by proving cell probe lower bounds for ball-inheritance. Our lower bounds are tight for a large range of parameters, excluding any further progress for range reporting using the ball-inheritance reduction.

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

Recommendations

• Lower bounds for orthogonal range searching: I. The reporting case
• Dynamic orthogonal range searching on the RAM, revisited
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• On the difficulty of range searching.

zbMATH Keywords

data structureslower boundsrange reportingcell probe model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cited In (3)

• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• Maintaining range trees is secondary memory. Part II: Lower bounds
• A general approach for cache-oblivious range reporting and approximate range counting

This page was built for publication: Towards tight lower bounds for range reporting on the RAM

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