Document Open Access Logo

Path Query Data Structures in Practice

Authors Meng He, Serikzhan Kazi

PDF
Thumbnail PDF

File

LIPIcs.SEA.2020.27.pdf
  • Filesize: 0.78 MB
  • 16 pages

Document Identifiers

Author Details

Meng He
  • Faculty of Computer Science, Dalhousie University, Halifax, Canada
Serikzhan Kazi
  • Faculty of Computer Science, Dalhousie University, Halifax, Canada

Funding

This work was supported by NSERC of Canada.

Cite As Get BibTex

Meng He and Serikzhan Kazi. Path Query Data Structures in Practice. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SEA.2020.27

Abstract

We perform experimental studies on data structures that answer path median, path counting, and path reporting queries in weighted trees. These query problems generalize the well-known range median query problem in arrays, as well as the 2d orthogonal range counting and reporting problems in planar point sets, to tree structured data. We propose practical realizations of the latest theoretical results on path queries. Our data structures, which use tree extraction, heavy-path decomposition and wavelet trees, are implemented in both succinct and pointer-based form. Our succinct data structures are further specialized to be plain or entropy-compressed. Through experiments on large sets, we show that succinct data structures for path queries may present a viable alternative to standard pointer-based realizations, in practical scenarios. Compared to naïve approaches that compute the answer by explicit traversal of the query path, our succinct data structures are several times faster in path median queries and perform comparably in path counting and path reporting queries, while being several times more space-efficient. Plain pointer-based realizations of our data structures, requiring a few times more space than the naïve ones, yield up to 100-times speed-up over them.

Subject Classification

ACM Subject Classification
  • Information systems → Data structures
Keywords
  • path query
  • path median
  • path counting
  • path reporting
  • weighted tree

Metrics

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

Related Versions

Supplementary Materials

References

  1. KIT roadgraphs. https://i11www.iti.kit.edu/information/roadgraphs. Accessed: 07/12/2018. URL: https://i11www.iti.kit.edu/information/roadgraphs.
  2. ltree module for PostreSQL RDBMS. https://www.postgresql.org/docs/current/ltree.html. Accessed: 10/01/2020. URL: https://www.postgresql.org/docs/current/ltree.html.
  3. MOLA Mars Orbiter Laser Altimeter data from NASA Mars Global Surveyor. https://planetarymaps.usgs.gov/mosaic/Mars_MGS_MOLA_DEM_mosaic_global_463m.tif. Accessed: 10/01/2019. URL: https://planetarymaps.usgs.gov/mosaic/Mars_MGS_MOLA_DEM_mosaic_global_463m.tif.
  4. SRTM Shuttle Radar Topography Mission. http://srtm.csi.cgiar.org/srtmdata/. Accessed: 10/01/2019. URL: http://srtm.csi.cgiar.org/srtmdata/.
  5. Andrés Abeliuk, Rodrigo Cánovas, and Gonzalo Navarro. Practical compressed suffix trees. Algorithms, 6(2):319-351, 2013. URL: https://doi.org/10.3390/a6020319.
  6. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network flows - theory, algorithms and applications. Prentice Hall, 1993. Google Scholar
  7. Noga Alon and Baruch Schieber. Optimal preprocessing for answering on-line product queries. Technical report, Tel-Aviv University, 1987. Google Scholar
  8. Diego Arroyuelo, Rodrigo Cánovas, Gonzalo Navarro, and Kunihiko Sadakane. Succinct trees in practice. In Proceedings of the Twelfth Workshop on Algorithm Engineering and Experiments, ALENEX 2010, Austin, Texas, USA, January 16, 2010, pages 84-97, 2010. URL: https://doi.org/10.1137/1.9781611972900.9.
  9. Diego Arroyuelo, Francisco Claude, Reza Dorrigiv, Stephane Durocher, Meng He, Alejandro López-Ortiz, J. Ian Munro, Patrick K. Nicholson, Alejandro Salinger, and Matthew Skala. Untangled monotonic chains and adaptive range search. Theor. Comput. Sci., 412(32):4200-4211, 2011. URL: https://doi.org/10.1016/j.tcs.2011.01.037.
  10. Michael A. Bender, Martin Farach-Colton, Giridhar Pemmasani, Steven Skiena, and Pavel Sumazin. Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms, 57(2):75-94, 2005. URL: https://doi.org/10.1016/j.jalgor.2005.08.001.
  11. David Benoit, Erik D. Demaine, J. Ian Munro, Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Representing trees of higher degree. Algorithmica, 43(4):275-292, 2005. URL: https://doi.org/10.1007/s00453-004-1146-6.
  12. Nieves R. Brisaboa, Guillermo de Bernardo, Roberto Konow, Gonzalo Navarro, and Diego Seco. Aggregated 2d range queries on clustered points. Inf. Syst., 60:34-49, 2016. URL: https://doi.org/10.1016/j.is.2016.03.004.
  13. Timothy M. Chan, Meng He, J. Ian Munro, and Gelin Zhou. Succinct indices for path minimum, with applications. Algorithmica, 78(2):453-491, 2017. URL: https://doi.org/10.1007/s00453-016-0170-7.
  14. Timothy M. Chan, Kasper Green Larsen, and Mihai Patrascu. Orthogonal range searching on the ram, revisited. In Computational Geometry, 27th ACM Symposium, SoCG 2011, Paris, France, June 13-15, 2011. Proceedings, pages 1-10, 2011. URL: https://doi.org/10.1145/1998196.1998198.
  15. Bernard Chazelle. Computing on a free tree via complexity-preserving mappings. Algorithmica, 2(1):337-361, November 1987. URL: https://doi.org/10.1007/BF01840366.
  16. Francisco Claude, J. Ian Munro, and Patrick K. Nicholson. Range queries over untangled chains. In String Processing and Information Retrieval - 17th International Symposium, SPIRE 2010, Los Cabos, Mexico, October 11-13, 2010. Proceedings, pages 82-93, 2010. URL: https://doi.org/10.1007/978-3-642-16321-0_8.
  17. O'Neil Delpratt, Naila Rahman, and Rajeev Raman. Engineering the LOUDS succinct tree representation. In Experimental Algorithms, 5th International Workshop, WEA 2006, Cala Galdana, Menorca, Spain, May 24-27, 2006, Proceedings, pages 134-145, 2006. URL: https://doi.org/10.1007/11764298_12.
  18. Arash Farzan and J. Ian Munro. A uniform paradigm to succinctly encode various families of trees. Algorithmica, 68(1):16-40, 2014. URL: https://doi.org/10.1007/s00453-012-9664-0.
  19. Travis Gagie, Simon J. Puglisi, and Andrew Turpin. Range quantile queries: Another virtue of wavelet trees. In String Processing and Information Retrieval, 16th International Symposium, SPIRE 2009, Saariselkä, Finland, August 25-27, 2009, Proceedings, pages 1-6, 2009. URL: https://doi.org/10.1007/978-3-642-03784-9_1.
  20. Richard F. Geary, Naila Rahman, Rajeev Raman, and Venkatesh Raman. A simple optimal representation for balanced parentheses. Theor. Comput. Sci., 368(3):231-246, 2006. URL: https://doi.org/10.1016/j.tcs.2006.09.014.
  21. Richard F. Geary, Rajeev Raman, and Venkatesh Raman. Succinct ordinal trees with level-ancestor queries. ACM Trans. Algorithms, 2(4):510-534, 2006. URL: https://doi.org/10.1145/1198513.1198516.
  22. Simon Gog, Timo Beller, Alistair Moffat, and Matthias Petri. From theory to practice: Plug and play with succinct data structures. In Experimental Algorithms - 13th International Symposium, SEA 2014, Copenhagen, Denmark, June 29 - July 1, 2014. Proceedings, pages 326-337, 2014. URL: https://doi.org/10.1007/978-3-319-07959-2_28.
  23. Torben Hagerup. Parallel preprocessing for path queries without concurrent reading. Inf. Comput., 158(1):18-28, 2000. URL: https://doi.org/10.1006/inco.1999.2814.
  24. Meng He and Serikzhan Kazi. Path and ancestor queries over trees with multidimensional weight vectors. In 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China, pages 45:1-45:17, 2019. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2019.45.
  25. Meng He, J. Ian Munro, and Srinivasa Rao Satti. Succinct ordinal trees based on tree covering. ACM Trans. Algorithms, 8(4):42:1-42:32, 2012. URL: https://doi.org/10.1145/2344422.2344432.
  26. Meng He, J. Ian Munro, and Gelin Zhou. Path queries in weighted trees. In Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings, pages 140-149, 2011. URL: https://doi.org/10.1007/978-3-642-25591-5_16.
  27. Meng He, J. Ian Munro, and Gelin Zhou. A framework for succinct labeled ordinal trees over large alphabets. Algorithmica, 70(4):696-717, 2014. URL: https://doi.org/10.1007/s00453-014-9894-4.
  28. Meng He, J. Ian Munro, and Gelin Zhou. Data structures for path queries. ACM Trans. Algorithms, 12(4):53:1-53:32, 2016. URL: https://doi.org/10.1145/2905368.
  29. Kazuki Ishiyama and Kunihiko Sadakane. A succinct data structure for multidimensional orthogonal range searching. In 2017 Data Compression Conference, DCC 2017, Snowbird, UT, USA, April 4-7, 2017, pages 270-279, 2017. URL: https://doi.org/10.1109/DCC.2017.47.
  30. Guy Jacobson. Space-efficient static trees and graphs. In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 549-554, 1989. URL: https://doi.org/10.1109/SFCS.1989.63533.
  31. Jesper Jansson, Kunihiko Sadakane, and Wing-Kin Sung. Ultra-succinct representation of ordered trees with applications. J. Comput. Syst. Sci., 78(2):619-631, 2012. URL: https://doi.org/10.1016/j.jcss.2011.09.002.
  32. Danny Krizanc, Pat Morin, and Michiel H. M. Smid. Range mode and range median queries on lists and trees. Nord. J. Comput., 12(1):1-17, 2005. Google Scholar
  33. Hsueh-I Lu and Chia-Chi Yeh. Balanced parentheses strike back. ACM Trans. Algorithms, 4(3):28:1-28:13, 2008. URL: https://doi.org/10.1145/1367064.1367068.
  34. J. Ian Munro, Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Succinct representations of permutations and functions. Theor. Comput. Sci., 438:74-88, 2012. URL: https://doi.org/10.1016/j.tcs.2012.03.005.
  35. J. Ian Munro and Venkatesh Raman. Succinct representation of balanced parentheses and static trees. SIAM J. Comput., 31(3):762-776, 2001. URL: https://doi.org/10.1137/S0097539799364092.
  36. David R. Musser. Introspective sorting and selection algorithms. Softw., Pract. Exper., 27(8):983-993, 1997. URL: https://doi.org/10.1002/(SICI)1097-024X(199708)27:8%3C983::AID-SPE117%3E3.0.CO;2-%23.
  37. Gonzalo Navarro. Compact Data Structures - A Practical Approach. Cambridge University Press, 2016. URL: http://www.cambridge.org/de/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/compact-data-structures-practical-approach?format=HB.
  38. Gonzalo Navarro and Alberto Ordó~nez Pereira. Faster compressed suffix trees for repetitive collections. ACM Journal of Experimental Algorithmics, 21(1):1.8:1-1.8:38, 2016. URL: https://doi.org/10.1145/2851495.
  39. OpenStreetMap contributors. Planet dump retrieved from https://planet.osm.org . https://www.openstreetmap.org , 2017. URL: https://www.openstreetmap.org.
  40. Manish Patil, Rahul Shah, and Sharma V. Thankachan. Succinct representations of weighted trees supporting path queries. J. Discrete Algorithms, 17:103-108, 2012. URL: https://doi.org/10.1016/j.jda.2012.08.003.
  41. Rajeev Raman, Venkatesh Raman, and Srinivasa Rao Satti. Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms, 3(4):43, 2007. URL: https://doi.org/10.1145/1290672.1290680.
  42. A. Rényi and G. Szekeres. On the height of trees. Journal of the Australian Mathematical Society, 7(4):497-507, 1967. Google Scholar
  43. Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362-391, June 1983. URL: https://doi.org/10.1016/0022-0000(83)90006-5.
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