Document Open Access Logo

Succinct Dynamic One-Dimensional Point Reporting

Authors Hicham El-Zein, J. Ian Munro, Yakov Nekrich

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2018.17.pdf
  • Filesize: 429 kB
  • 11 pages

Document Identifiers

Author Details

Hicham El-Zein
  • Cheriton School of Computer Science, University of Waterloo, Ontario, Canada N2L 3G1
J. Ian Munro
  • Cheriton School of Computer Science, University of Waterloo, Ontario, Canada N2L 3G1
Yakov Nekrich
  • Cheriton School of Computer Science, University of Waterloo, Ontario, Canada N2L 3G1

Funding

  • Munro, J. Ian: This work was sponsored by the NSERC of Canada and the Canada Research Chairs Program.

Cite AsGet BibTex

Hicham El-Zein, J. Ian Munro, and Yakov Nekrich. Succinct Dynamic One-Dimensional Point Reporting. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 17:1-17:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SWAT.2018.17

Abstract

In this paper we present a succinct data structure for the dynamic one-dimensional range reporting problem. Given an interval [a,b] for some a,b in [m], the range reporting query on an integer set S subseteq [m] asks for all points in S cap [a,b]. We describe a data structure that answers reporting queries in optimal O(k+1) time, where k is the number of points in the answer, and supports updates in O(lg^epsilon m) expected time. Our data structure uses B(n,m) + o(B(n,m)) bits where B(n,m) is the minimum number of bits required to represent a set of size n from a universe of m elements. This is the first dynamic data structure for this problem that uses succinct space and achieves optimal query time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • Succinct Data Structures
  • Range Searching
  • Computational Geometry

Metrics

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

References

  1. Stephen Alstrup, Gerth Brodal, and Theis Rauhe. Optimal static range reporting in one dimension. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 476-482. ACM, 2001. Google Scholar
  2. Prosenjit Bose, Eric Y. Chen, Meng He, Anil Maheshwari, and Pat Morin. Succinct geometric indexes supporting point location queries. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pages 635-644, 2009. Google Scholar
  3. Paul Dietz and Daniel Sleator. Two algorithms for maintaining order in a list. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 365-372. ACM, 1987. Google Scholar
  4. Hicham El-Zein, J. Ian Munro, and Yakov Nekrich. Succinct color searching in one dimension. In 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand, pages 30:1-30:11, 2017. Google Scholar
  5. Arash Farzan, J. Ian Munro, and Rajeev Raman. Succinct indices for range queries with applications to orthogonal range maxima. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming, Part I, pages 327-338, 2012. Google Scholar
  6. Richard F Geary, Rajeev Raman, and Venkatesh Raman. Succinct ordinal trees with level-ancestor queries. ACM Transactions on Algorithms (TALG), 2(4):510-534, 2006. Google Scholar
  7. Mayank Goswami, Allan Grønlund Jørgensen, Kasper Green Larsen, and Rasmus Pagh. Approximate range emptiness in constant time and optimal space. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 769-775, 2015. Google Scholar
  8. Roberto Grossi, Rajeev Raman, Satti Srinivasa Rao, and Rossano Venturini. Dynamic compressed strings with random access. In International Colloquium on Automata, Languages, and Programming, pages 504-515. Springer, 2013. Google Scholar
  9. Ankur Gupta, Wing-Kai Hon, Rahul Shah, and Jeffrey Scott Vitter. A framework for dynamizing succinct data structures. In International Colloquium on Automata, Languages, and Programming, pages 521-532. Springer, 2007. Google Scholar
  10. Meng He. Succinct and implicit data structures for computational geometry. In Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, pages 216-235, 2013. Google Scholar
  11. J Ian Munro and S Srinivasa Rao. Succinct representation of data structures. In Handbook of Data Structures and Applications, chapter 37. Chapman and Hall/CRC, 2004. Google Scholar
  12. Christiaan TM Jacobs and Peter Van Emde Boas. Two results on tables. Information Processing Letters, 22(1):43-48, 1986. Google Scholar
  13. Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 103-111. ACM, 1995. Google Scholar
  14. Christian Worm Mortensen, Rasmus Pagh, and Mihai Patrascu. On dynamic range reporting in one dimension. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 104-111. ACM, 2005. Google Scholar
  15. Ian Munro, Yakov Nekrich, and Jeffrey Scott Vitter. Dynamic data structures for document collections and graphs. In Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 277-289. ACM, 2015. Google Scholar
  16. J Ian Munro and Yakov Nekrich. Compressed data structures for dynamic sequences. In Algorithms-ESA 2015, pages 891-902. Springer, 2015. Google Scholar
  17. Gonzalo Navarro. Compact data structures: A practical approach. Cambridge University Press, 2016. Google Scholar
  18. Gonzalo Navarro and Kunihiko Sadakane. Fully functional static and dynamic succinct trees. ACM Transactions on Algorithms (TALG), 10(3):16, 2014. 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 Imprint Privacy Contact