Document Open Access Logo

Towards Tight Lower Bounds for Range Reporting on the RAM

Authors Allan Grønlund, Kasper Green Larsen

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.92.pdf
  • Filesize: 484 kB
  • 12 pages

Document Identifiers

Author Details

Allan Grønlund
Kasper Green Larsen

Cite As Get BibTex

Allan Grønlund and Kasper Green Larsen. Towards Tight Lower Bounds for Range Reporting on the RAM. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 92:1-92:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.92

Abstract

In the orthogonal range reporting problem, we are to preprocess a set of n points with integer coordinates on a UxU 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 exist, all 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.

Subject Classification

Keywords
  • Data Structures
  • Lower Bounds
  • Cell Probe Model
  • Range Reporting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Stephen Alstrup, Gerth Stølting Brodal, and Theis Rauhe. New data structures for orthogonal range searching. In Proc. 41st IEEE Symposium on Foundations of Computer Science, pages 198-207, 2000. Google Scholar
  2. Lars Arge, Vasilis Samoladas, and Jeffrey Scott Vitter. On two-dimensional indexability and optimal range search indexing. In Proc. 18th ACM Symposium on Principles of Database Systems, pages 346-357, 1999. Google Scholar
  3. Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509-517, 1975. Google Scholar
  4. Gerth Stølting Brodal and Kasper Green Larsen. Optimal planar orthogonal skyline counting queries. In Proc. 14th Scandinavian Workshop on Algorithms Theory, pages 110-121, 2014. Google Scholar
  5. Timothy M. Chan, Kasper Larsen, and Mihai Pǎtraşcu. Orthogonal range searching on the ram, revisited. In Proc. 27th ACM Symposium on Computational Geometry, pages 354-363, 2011. See also arXiv:1011.5200. Google Scholar
  6. Timothy M. Chan and Bryan T. Wilkinson. Adaptive and approximate orthogonal range counting. In Proc. 24th ACM/SIAM Symposium on Discrete Algorithms, pages 241-251, 2013. Google Scholar
  7. Bernard Chazelle. Filtering search: a new approach to query answering. SIAM Journal on Computing, 15(3):703-724, 1986. URL: http://dx.doi.org/10.1137/0215051.
  8. Bernard Chazelle. Lower bounds for orthogonal range searching: I. the reporting case. Journal of the ACM, 37(2):200-212, 1990. Google Scholar
  9. Johannes Fischer. Optimal succinctness for range minimum queries. In Proc. 9th Latin American Theoretical Informatics Symposium, pages 158-169, 2010. Google Scholar
  10. Kasper Green Larsen. Higher cell probe lower bounds for evaluating polynomials. In Proc. 53rd IEEE Symposium on Foundations of Computer Science, pages 293-301, 2012. Google Scholar
  11. Yakov Nekrich. Orthogonal range searching in linear and almost-linear space. Computational Geometry: Theory and Applications, 42:342-351, 2009. Google Scholar
  12. Mihai Pǎtraşcu and Mikkel Thorup. Time-space trade-offs for predecessor search. In Proc. 38th ACM Symposium on Theory of Computation, pages 232-240, 2006. Google Scholar
  13. Mihai Pǎtraşcu and Mikkel Thorup. Higher lower bounds for near-neighbor and further rich problems. SIAM Journal on Computing, 39(2):730-741, 2010. Google Scholar
  14. Mihai Pǎtraşcu and Mikkel Thorup. Randomization does not help searching predecessors. In Proc. 18th ACM/SIAM Symposium on Discrete Algorithms, pages 555-564, 2007. Google Scholar
  15. Yaoyu Wang and Yitong Yin. Certificates in data structures. In Proc. 41st International Colloquium on Automata, Languages, and Programming, pages 1039-1050, 2014. Google Scholar
  16. Andrew Chi Chih Yao. Should tables be sorted? Journal of the ACM, 28(3):615-628, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact