Document Open Access Logo

Path Queries on Functions

Authors Travis Gagie, Meng He, Gonzalo Navarro

PDF

File

Thumbnail PDF
PDF
LIPIcs.CPM.2017.5.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Subject Classification

Keywords
  • succinct data structures
  • integer functions
  • range queries
  • trees and permutations

Metrics

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

Abstract

Let f : [1..n] -> [1..n] be a function, and l : [1..n] -> [1..s] indicate a label assigned to each element of the domain. We design several compact data structures that answer various queries on the labels of paths in f. For example, we can find the minimum label in f^k (i) for a given i and any k >= 0 in a given range [k1..k2], using n lg n + O(n) bits, or the minimum label in f^(-k) (i) for a given i and k > 0, using 2n lg n + O(n) bits, both in time O(lg n/ lg lg n). By using n lg s + o(n lg s) further bits, we can also count, within the same time, the number of elements within a range of labels, and report each such element in O(1 + lg s / lg lg n) additional time. Several other possible queries are considered, such as top-t queries and t-majorities.

Cite As Get BibTex

Travis Gagie, Meng He, and Gonzalo Navarro. Path Queries on Functions. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CPM.2017.5

Author Details

Travis Gagie
Meng He
Gonzalo Navarro

References

  1. Djamal Belazzougui, Travis Gagie, J. Ian Munro, Gonzalo Navarro, and Yakov Nekrich. Range majorities and minorities in arrays, 2016. URL: http://arxiv.org/abs/1606.04495.
  2. Prosenjit Bose, Meng He, Anil Maheshwari, and Pat Morin. Succinct orthogonal range search structures on a grid with applications to text indexing. In Frank K. H. A. Dehne, Marina L. Gavrilova, Jörg-Rüdiger Sack, and Csaba D. Tóth, editors, Proceedings of the 11th International Symposium on Algorithms and Data Structures (WADS 2009), volume 5664 of LNCS, pages 98-109. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-03367-4_9.
  3. Timothy M. Chan, Meng He, J. Ian Munro, and Gelin Zhou. Succinct indices for path minimum, with applications to path reporting. In Andreas S. Schulz and Dorothea Wagner, editors, Proceedings of the 22nd Annual European Symposium on Algorithms (ESA 2014), volume 8737 of LNCS, pages 247-259. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_21.
  4. 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 (SoCG 2011), pages 1-10. ACM, 2011. URL: http://dx.doi.org/10.1145/1998196.1998198.
  5. David R. Clark. Compact PAT Trees. PhD thesis, University of Waterloo, Canada, 1996. URL: http://hdl.handle.net/10012/64.
  6. Johannes Fischer and Volker Heun. Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput., 40(2):465-492, 2011. URL: http://dx.doi.org/10.1137/090779759.
  7. Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. High-order entropy-compressed text indexes. In Martin Farach-Colton, editor, Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pages 841-850. ACM/SIAM, 2003. URL: http://dl.acm.org/citation.cfm?id=644108.644250.
  8. Meng He, J. Ian Munro, and Gelin Zhou. Succinct data structures for path queries. In Leah Epstein and Paolo Ferragina, editors, Proceedings of the 20th Annual European Symposium on Algorithms (ESA 2012), volume 7501 of LNCS, pages 575-586. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33090-2_50.
  9. Joseph JáJá, Christian Worm Mortensen, and Qingmin Shi. Space-efficient and fast algorithms for multidimensional dominance reporting and counting. In Rudolf Fleischer and Gerhard Trippen, editors, Proceedings of the 15th International Symposium on Algorithms and Computation (ISAAC 2004), volume 3341 of LNCS, pages 558-568. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-30551-4_49.
  10. J. Ian Munro, Rajeev Raman, Venkatesh Raman, and Srinivasa Rao Satti. Succinct representations of permutations and functions. Theor. Comput. Sci., 438:74-88, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.03.005.
  11. Gonzalo Navarro. Compact Data Structures: A practical approach. Cambridge University Press, 2016. URL: http://dx.doi.org/10.1017/CBO9781316588284.
  12. Gonzalo Navarro and Yakov Nekrich. Top-k document retrieval in optimal time and linear space. In Yuval Rabani, editor, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 1066-1077. SIAM, 2012. URL: http://dx.doi.org/10.1137/1.9781611973099.84.
  13. Gonzalo Navarro, Yakov Nekrich, and Luís M. S. Russo. Space-efficient data-analysis queries on grids. Theor. Comput. Sci., 482:60-72, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2012.11.031.
  14. Gonzalo Navarro, Rajeev Raman, and Srinivasa Rao Satti. Asymptotically optimal encodings for range selection. In Venkatesh Raman and S. P. Suresh, editors, Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014), volume 29 of LIPIcs, pages 291-301. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2014.291.
  15. Gonzalo Navarro and Kunihiko Sadakane. Fully functional static and dynamic succinct trees. ACM Trans. Algorithms, 10(3):16:1-16:39, 2014. URL: http://dx.doi.org/10.1145/2601073.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact