Document Open Access Logo

Algorithms and Hardness for Multidimensional Range Updates and Queries

Authors Joshua Lau , Angus Ritossa

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.35.pdf
  • Filesize: 0.6 MB
  • 20 pages

Document Identifiers

Author Details

Joshua Lau
  • Sydney, Australia
Angus Ritossa
  • University of New South Wales, Sydney, Australia

Acknowledgements

We thank Tunan Shi, for suggesting the reduction from 2RangeInversionsQuery to Static Trellised 2D Grid Range (+, set). We also thank Ray Li and anonymous reviewers for helpful suggestions and comments.

Cite As Get BibTex

Joshua Lau and Angus Ritossa. Algorithms and Hardness for Multidimensional Range Updates and Queries. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITCS.2021.35

Abstract

Traditional orthogonal range problems allow queries over a static set of points, each with some value. Dynamic variants allow points to be added or removed, one at a time. To support more powerful updates, we introduce the Grid Range class of data structure problems over arbitrarily large integer arrays in one or more dimensions. These problems allow range updates (such as filling all points in a range with a constant) and queries (such as finding the sum or maximum of values in a range). In this work, we consider these operations along with updates that replace each point in a range with the minimum, maximum, or sum of its existing value, and a constant. In one dimension, it is known that segment trees can be leveraged to facilitate any n of these operations in Õ(n) time overall. Other than a few specific cases, until now, higher dimensional variants have been largely unexplored.
Despite their tightly-knit complexity in one dimension, we show that variants induced by subsets of these operations exhibit polynomial separation in two dimensions. In particular, no truly subquadratic time algorithm can support certain pairs of these updates simultaneously without falsifying several popular conjectures. On the positive side, we show that truly subquadratic algorithms can be obtained for variants induced by other subsets.
We provide two general approaches to designing such algorithms that can be generalised to online and higher dimensional settings. First, we give almost-tight Õ(n^{3/2}) time algorithms for single-update variants where the update and query operations meet a set of natural conditions. Second, for other variants, we provide a general framework for reducing to instances with a special geometry. Using this, we show that O(m^{3/2-ε}) time algorithms for counting paths and walks of length 2 and 3 between vertex pairs in sparse graphs imply truly subquadratic data structures for certain variants; to this end, we give an Õ(m^{(4ω-1)/(2ω+1)}) = O(m^1.478) time algorithm for counting simple 3-paths between vertex pairs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
  • Mathematics of computing → Graph algorithms
Keywords
  • Orthogonal range
  • Range updates
  • Online and Dynamic Data Structures
  • Fine-grained complexity
  • Cycle counting

Metrics

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

Related Versions

References

  1. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 41-50. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746594.
  2. Peyman Afshani, Lars Arge, and Kasper Dalgaard Larsen. Orthogonal range reporting in three and higher dimensions. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 149-158. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/FOCS.2009.58.
  3. Peyman Afshani, Lars Arge, and Kasper Dalgaard Larsen. Orthogonal range reporting: query lower bounds, optimal structures in 3-d, and higher-dimensional improvements. In David G. Kirkpatrick and Joseph S. B. Mitchell, editors, Proceedings of the 26th ACM Symposium on Computational Geometry, Snowbird, Utah, USA, June 13-16, 2010, pages 240-246. ACM, 2010. URL: https://doi.org/10.1145/1810959.1811001.
  4. Pankaj K. Agarwal. Range searching. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, Second Edition, pages 809-837. Chapman and Hall/CRC, 2004. URL: https://doi.org/10.1201/9781420035315.ch36.
  5. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. CoRR, abs/2010.05846, 2020. URL: http://arxiv.org/abs/2010.05846.
  6. Arturs Backurs, Nishanth Dikkala, and Christos Tzamos. Tight hardness results for maximum weight rectangles. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 81:1-81:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.81.
  7. Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):509-517, 1975. URL: https://doi.org/10.1145/361002.361007.
  8. Jon Louis Bentley. Solutions to klee’s rectangle problems. Unpublished manuscript, pages 282-300, 1977. Google Scholar
  9. Timothy M. Chan. A (slightly) faster algorithm for klee’s measure problem. In Monique Teillaud, editor, Proceedings of the 24th ACM Symposium on Computational Geometry, College Park, MD, USA, June 9-11, 2008, pages 94-100. ACM, 2008. URL: https://doi.org/10.1145/1377676.1377693.
  10. Timothy M. Chan. Klee’s measure problem made easy. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 410-419. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.51.
  11. Timothy M. Chan, Kasper Green Larsen, and Mihai Pǎtraşcu. Orthogonal range searching on the ram, revisited. In Ferran Hurtado and Marc J. van Kreveld, editors, Proceedings of the 27th ACM Symposium on Computational Geometry, Paris, France, June 13-15, 2011, pages 1-10. ACM, 2011. URL: https://doi.org/10.1145/1998196.1998198.
  12. Timothy M. Chan, Yakov Nekrich, and Michiel H. M. Smid. Orthogonal range reporting and rectangle stabbing for fat rectangles. In Zachary Friggstad, Jörg-Rüdiger Sack, and Mohammad R. Salavatipour, editors, Algorithms and Data Structures - 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings, volume 11646 of Lecture Notes in Computer Science, pages 283-295. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-24766-9_21.
  13. Bernard Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput., 17(3):427-462, 1988. URL: https://doi.org/10.1137/0217026.
  14. Lech Duraj, Krzysztof Kleiner, Adam Polak, and Virginia Vassilevska Williams. Equivalences between triangle and range query problems. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 30-47. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.3.
  15. Jim Gray, Adam Bosworth, Andrew Layman, and Hamid Pirahesh. Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-total. In Stanley Y. W. Su, editor, Proceedings of the Twelfth International Conference on Data Engineering, February 26 - March 1, 1996, New Orleans, Louisiana, USA, pages 152-159. IEEE Computer Society, 1996. URL: https://doi.org/10.1109/ICDE.1996.492099.
  16. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 21-30. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746609.
  17. Nabil Ibtehaz, M. Kaykobad, and M. Sohel Rahman. Multidimensional segment trees can do range queries and updates in logarithmic time. CoRR, abs/1811.01226, 2018. URL: http://arxiv.org/abs/1811.01226.
  18. Ruyi Ji. Interval maximum value operation and historical maximum value problem. Informatics Olympiad China National Team Candidates Essay Collection, 2016. Article written in Chinese. The author (Ji) has written a blog post in English, outlining the main techniques: https://codeforces.com/blog/entry/57319. Google Scholar
  19. Tuukka Korhonen. On multidimensional range queries. Technical report, University of Helsinki, 2019. Google Scholar
  20. D. T. Lee and C. K. Wong. Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees. Acta Informatica, 9:23-29, 1977. URL: https://doi.org/10.1007/BF00263763.
  21. George S. Lueker. A data structure for orthogonal range queries. In 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16-18 October 1978, pages 28-34. IEEE Computer Society, 1978. URL: https://doi.org/10.1109/SFCS.1978.1.
  22. Yuzuru Okajima and Kouichi Maruyama. Faster linear-space orthogonal range searching in arbitrary dimensions. In Ulrik Brandes and David Eppstein, editors, Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments, ALENEX 2015, San Diego, CA, USA, January 5, 2015, pages 82-93. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973754.8.
  23. Mark H. Overmars and Chee-Keng Yap. New upper bounds in klee’s measure problem. SIAM J. Comput., 20(6):1034-1045, 1991. URL: https://doi.org/10.1137/0220065.
  24. Chung Keung Poon. Dynamic orthogonal range queries in OLAP. Theor. Comput. Sci., 296(3):487-510, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00741-7.
  25. Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, and Huacheng Yu. Finding four-node subgraphs in triangle time. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1671-1680. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.111.
  26. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 645-654. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.67.
  27. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.023.
  28. Virginia Vassilevska Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In Thore Husfeldt and Iyad A. Kanj, editors, 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, volume 43 of LIPIcs, pages 17-29. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.IPEC.2015.17.
  29. Raphael Yuster and Uri Zwick. Detecting short directed cycles using rectangular matrix multiplication and dynamic programming. In J. Ian Munro, editor, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004, pages 254-260. SIAM, 2004. URL: http://dl.acm.org/citation.cfm?id=982792.982828.
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