Document Open Access Logo

Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing

Authors Younan Gao, Meng He, Yakov Nekrich

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.54.pdf
  • Filesize: 0.54 MB
  • 18 pages

Document Identifiers

Author Details

Younan Gao
  • Faculty of Computer Science, Dalhousie University, Halifax, Canada
Meng He
  • Faculty of Computer Science, Dalhousie University, Halifax, Canada
Yakov Nekrich
  • Department of Computer Science, Michigan Technological University, Houghton, MI, USA

Cite AsGet BibTex

Younan Gao, Meng He, and Yakov Nekrich. Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.54

Abstract

Under the word RAM model, we design three data structures that can be constructed in O(n √{lg n}) time over n points in an n × n grid. The first data structure is an O(n lg^ε n)-word structure supporting orthogonal range reporting in O(lg lg n+k) time, where k denotes output size and ε is an arbitrarily small constant. The second is an O(n lg lg n)-word structure supporting orthogonal range successor in O(lg lg n) time, while the third is an O(n lg^ε n)-word structure supporting sorted range reporting in O(lg lg n+k) time. The query times of these data structures are optimal when the space costs must be within O(n polylog n) words. Their exact space bounds match those of the best known results achieving the same query times, and the O(n √{lg n}) construction time beats the previous bounds on preprocessing. Previously, among 2d range search structures, only the orthogonal range counting structure of Chan and Pǎtraşcu (SODA 2010) and the linear space, O(lg^ε n) query time structure for orthogonal range successor by Belazzougui and Puglisi (SODA 2016) can be built in the same O(n √{lg n}) time. Hence our work is the first that achieve the same preprocessing time for optimal orthogonal range reporting and range successor. We also apply our results to improve the construction time of text indexes.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Data structures design and analysis
Keywords
  • orthogonal range search
  • geometric data structures
  • orthogonal range reporting
  • orthogonal range successor
  • sorted range reporting
  • text indexing
  • word RAM

Metrics

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

Related Versions

References

  1. Stephen Alstrup, Gerth Stølting Brodal, and Theis Rauhe. New data structures for orthogonal range searching. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, pages 198-207. IEEE Computer Society, 2000. URL: https://doi.org/10.1109/SFCS.2000.892088.
  2. Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka, and Tatiana Starikovskaya. Wavelet trees meet suffix trees. In 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 572-591. Society for Industrial and Applied Mathematics, 2015. Google Scholar
  3. Djamal Belazzougui, Fabio Cunial, Juha Kärkkäinen, and Veli Mäkinen. Linear-time string indexing and analysis in small space. ACM Transactions on Algorithms (TALG), 16(2):1-54, 2020. Google Scholar
  4. Djamal Belazzougui and Simon J Puglisi. Range predecessor and lempel-ziv parsing. In 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2053-2071. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  5. Michael A Bender and Martın Farach-Colton. The level ancestor problem simplified. Theoretical Computer Science, 321(1):5-12, 2004. Google Scholar
  6. Philip Bille and Inge Li Gørtz. Substring range reporting. Algorithmica, 69(2):384-396, 2014. URL: https://doi.org/10.1007/s00453-012-9733-4.
  7. Philip Bille, Inge Li Gørtz, and Frederik Rye Skjoldjensen. Deterministic indexing for packed strings. In 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, pages 6:1-6:11, 2017. URL: https://doi.org/10.4230/LIPIcs.CPM.2017.6.
  8. Prosenjit Bose, Meng He, Anil Maheshwari, and Pat Morin. Succinct orthogonal range search structures on a grid with applications to text indexing. In 11th International Symposium on Algorithms and Data Structures, volume 5664 of Lecture Notes in Computer Science, pages 98-109. Springer, 2009. Google Scholar
  9. Timothy M. Chan. Persistent predecessor search and orthogonal point location on the word RAM. In 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1131-1145, 2011. URL: https://doi.org/10.1137/1.9781611973082.85.
  10. Timothy M Chan, Meng He, J Ian Munro, and Gelin Zhou. Succinct indices for path minimum, with applications. Algorithmica, 78(2):453-491, 2017. Google Scholar
  11. Timothy M Chan, Kasper Green Larsen, and Mihai Pătraşcu. Orthogonal range searching on the ram, revisited. In 27th Symposium on Computational Geometry, pages 1-10. ACM, 2011. Google Scholar
  12. Timothy M. Chan and Mihai Pǎtraşcu. Counting inversions, offline orthogonal range counting, and related problems. In 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pages 161-173, 2010. URL: https://doi.org/10.1137/1.9781611973075.15.
  13. Bernard Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM Journal on Computing, 17(3):427-462, 1988. URL: https://doi.org/10.1137/0217026.
  14. Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, M. Sohel Rahman, German Tischler, and Tomasz Walen. Improved algorithms for the range next value problem and applications. Theoretical Computer Science, 434:23-34, 2012. URL: https://doi.org/10.1016/j.tcs.2012.02.015.
  15. Maxime Crochemore, Marcin Kubica, Tomasz Walen, Costas S. Iliopoulos, and M. Sohel Rahman. Finding patterns in given intervals. Fundamenta Informaticae, 101(3):173-186, 2010. URL: https://doi.org/10.3233/FI-2010-283.
  16. Johannes Fischer and Volker Heun. Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM Journal on Computing, 40(2):465-492, 2011. Google Scholar
  17. Joseph JáJá, Christian Worm Mortensen, and Qingmin Shi. Space-efficient and fast algorithms for multidimensional dominance reporting and counting. In 15th International Symposium on Algorithms and Computation, volume 3341 of Lecture Notes in Computer Science, pages 558-568. Springer, 2004. Google Scholar
  18. Jesper Jansson, Zhaoxian Li, and Wing-Kin Sung. On finding the adams consensus tree. Information and Computation, 256:334-347, 2017. URL: https://doi.org/10.1016/j.ic.2017.08.002.
  19. Marek Karpinski and Yakov Nekrich. Space efficient multi-dimensional range reporting. In 15th Annual International Conference on Computing and Combinatorics (COCOON), pages 215-224, 2009. URL: https://doi.org/10.1007/978-3-642-02882-3_22.
  20. Orgad Keller, Tsvi Kopelowitz, and Moshe Lewenstein. Range non-overlapping indexing and successive list indexing. In 10th Workshop on Algorithms and Data Structures, Proceedings, volume 4619 of Lecture Notes in Computer Science, pages 625-636. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-73951-7_54.
  21. Hans-Peter Lenhof and Michiel H. M. Smid. Using persistent data structures for adding range restrictions to searching problems. Informatique Theorique et Applications, 28(1):25-49, 1994. URL: https://doi.org/10.1051/ita/1994280100251.
  22. Moshe Lewenstein. Orthogonal range searching for text indexing. In Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, pages 267-302, 2013. URL: https://doi.org/10.1007/978-3-642-40273-9_18.
  23. Veli Mäkinen and Gonzalo Navarro. Position-restricted substring searching. In 7th Latin American Symposium on Theoretical Informatics, pages 703-714. Springer, 2006. Google Scholar
  24. Veli Mäkinen and Gonzalo Navarro. Rank and select revisited and extended. Theoretical Computer Science, 387(3):332-347, 2007. URL: https://doi.org/10.1016/j.tcs.2007.07.013.
  25. J. Ian Munro, Gonzalo Navarro, and Yakov Nekrich. Text indexing and searching in sublinear time. In 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, pages 24:1-24:15, 2020. URL: https://doi.org/10.4230/LIPIcs.CPM.2020.24.
  26. J Ian Munro, Yakov Nekrich, and Jeffrey S Vitter. Fast construction of wavelet trees. Theoretical Computer Science, 638:91-97, 2016. Google Scholar
  27. Yakov Nekrich. A data structure for multi-dimensional range reporting. In 23rd ACM Symposium on Computational Geometry (SoCG), pages 344-353, 2007. URL: https://doi.org/10.1145/1247069.1247130.
  28. Yakov Nekrich and Gonzalo Navarro. Sorted range reporting. In 13th Scandinavian Symposium and Workshops, 2012. Proceedings, pages 271-282, 2012. URL: https://doi.org/10.1007/978-3-642-31155-0_24.
  29. Mihai Patrascu and Mikkel Thorup. Time-space trade-offs for predecessor search. In 38th Annual ACM Symposium on Theory of Computing, 2006, pages 232-240. ACM, 2006. URL: https://doi.org/10.1145/1132516.1132551.
  30. Dan E. Willard. On the application of sheared retrieval to orthogonal range queries. In 2nd Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry (SoCG) 1986, pages 80-89. ACM, 1986. URL: https://doi.org/10.1145/10515.10524.
  31. Chih-Chiang Yu, Wing-Kai Hon, and Biing-Feng Wang. Improved data structures for the orthogonal range successor problem. Computational Geometry, 44(3):148-159, 2011. URL: https://doi.org/10.1016/j.comgeo.2010.09.001.
  32. Gelin Zhou. Two-dimensional range successor in optimal time and almost linear space. Information Processing Letters, 116(2):171-174, 2016. URL: https://doi.org/10.1016/j.ipl.2015.09.002.
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 Imprint Privacy Contact