zbMATH — the first resource for mathematics

Succinct data structures for path queries. (English) Zbl 1365.68181
Epstein, Leah (ed.) et al., Algorithms – ESA 2012. 20th annual European symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceeding. Berlin: Springer (ISBN 978-3-642-33089-6/pbk). Lecture Notes in Computer Science 7501, 575-586 (2012).
Summary: Consider a tree \(T\) on \(n\) nodes, each having a weight drawn from \([1..\sigma ]\). In this paper, we design succinct data structures to encode \(T\) using \(n H(W_T) + o(n\lg \sigma)\) bits of space, such that we can support path counting queries in \(O(\frac{\lg \sigma}{\lg\lg n} + 1)\) time, path reporting queries in \(O((\mathrm{occ}+1)(\frac{\lg \sigma}{\lg\lg n} + 1))\) time, and path median and path selection queries in \(O(\frac{\lg \sigma}{\lg\lg \sigma})\) time, where \(H(W _{T })\) is the entropy of the multiset of the weights of the nodes in \(T\). Our results not only improve the best known linear space data structures [the authors, Lect. Notes Comput. Sci. 7074, 140–149 (2011; Zbl 1350.68073)], but also match the lower bounds for these path queries [M. Pǎtraşcu, in: Proceedings of the 39th annual ACM symposium on theory of computing, STOC’07. New York, NY: Association for Computing Machinery (ACM). 40–46 (2007; Zbl 1232.68068); SIAM J. Comput. 40, No. 3, 827–847 (2011; Zbl 1226.68033); A. G. Jørgensen and K. G. Larsen, in: Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA’11. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 805–813 (2011; doi:10.1137/1.9781611973082.63)] when \(\sigma = \Omega(n / \text{polylog}(n))\).
For the entire collection see [Zbl 1246.68031].

68P05 Data structures
Full Text: DOI