×

zbMATH — the first resource for mathematics

Succinct representations of weighted trees supporting path queries. (English) Zbl 1268.68069
Summary: We consider the problem of succinctly representing a given vertex-weighted tree of n vertices, whose vertices are labeled by integer weights from \(\{1,2,\ldots ,\sigma\}\) and supporting the following path queries efficiently: (1) path median query: given two vertices \(i\), \(j\), return the median weight on the path from \(i\) to \(j\), (2) path selection query: given two vertices \(i\), \(j\) and a positive integer \(k\), return the \(k\)th smallest weight on the path from \(i\) to \(j\), (3) path counting/reporting query: given two vertices \(i\), \(j\) and a range \([a,b]\), count/report the vertices on the path from \(i\) to \(j\) whose weights are in this range.
The previous best data structure supporting these queries takes \(O(n\log n)\) bits space and can perform path median/selection/counting in \(O(\log\sigma )\) time and path reporting in \(O(\log \sigma +occ\log \sigma )\) time, where \(occ\) represents the number of outputs [M. He et al., Lect. Notes Comput. Sci. 7074, 140–149 (2011; Zbl 1350.68073)].
We present a succinct data structure taking \(n\log \sigma +6n+o(n\log \sigma )\) bits space that can perform the above mentioned queries in \(O(\log \sigma \log n)\) and \(O(\log \sigma \log n+occ\log \sigma )\) time respectively.

MSC:
68P05 Data structures
68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] N. Alon, B. Schieber, Optimal preprocessing for answering on-line product queries, Tech. Rep., Tel Aviv University, 1987.
[2] Benoit, D.; Demaine, E.D.; Munro, J.I.; Raman, R.; Raman, V.; Rao, S.S., Representing trees of higher degree, Algorithmica, 43, 4, 275-292, (2005) · Zbl 1086.68034
[3] Chazelle, B., Computing on a free tree via complexity-preserving mappings, Algorithmica, 2, 337-361, (1987) · Zbl 0636.68092
[4] D.R. Clark, J.I. Munro, Efficient suffix trees on secondary storage (extended abstract), in: ACM-SIAM Symposium on Discrete Algorithms, 1996, pp. 383-391. · Zbl 0847.68030
[5] Cole, R.; Farach-Colton, M.; Hariharan, R.; Przytycka, T.M.; Thorup, M., An \(O(n \log n)\) algorithm for the maximum agreement subtree problem for binary trees, SIAM J. comput., 30, 5, 1385-1404, (2000) · Zbl 0976.68081
[6] T. Gagie, S.J. Puglisi, A. Turpin, Range quantile queries: another virtue of wavelet trees, in: International Conference on String Processing and Information Retrieval, 2009, pp. 1-6.
[7] R. Grossi, A. Gupta, J.S. Vitter, High-order entropy-compressed text indexes, in: ACM-SIAM Symposium on Discrete Algorithms, 2003, pp. 841-850. · Zbl 1092.68584
[8] Hagerup, T., Parallel preprocessing for path queries without concurrent Reading, Inform. and comput., 158, 1, 18-28, (2000) · Zbl 1046.68979
[9] Harel, D.; Tarjan, R.E., Fast algorithms for finding nearest common ancestors, SIAM J. comput., 13, 2, 338-355, (1984) · Zbl 0535.68022
[10] M. He, J.I. Munro, G. Zhou, Path queries in weighted trees, in: International Symposium on Algorithms and Computation, 2011, pp. 140-149. · Zbl 1350.68073
[11] M. He, J.I. Munro, G. Zhou, Succinct data structures for path queries, in: European Symposium on Algorithms, 2012.
[12] W.-K. Hon, R. Shah, J.S. Vitter, Ordered pattern matching: towards full-text retrieval, Purdue University Tech. Rept. CSD TR 06-008, 2006.
[13] G. Jacobson, Space-efficient static trees and graphs, in: IEEE Symposium on Foundations of Computer Science, 1984, pp. 549-554.
[14] J. Jansson, K. Sadakane, W.-K. Sung, Ultra-succinct representation of ordered trees, in: ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 575-584. · Zbl 1302.68100
[15] Krizanc, D.; Morin, P.; Smid, M.H.M., Range mode and range Median queries on lists and trees, Nordic J. comput., 12, 1, 1-17, (2005) · Zbl 1083.68028
[16] Lu, H.-I.; Yeh, C.-C., Balanced parentheses strike back, ACM trans. algorithms, 4, 3, (2008), Article No. 28
[17] V. Mäkinen, G. Navarro, Position-restricted substring searching, in: Latin American Symposium on Theoretical Informatics, 2006, pp. 703-714. · Zbl 1145.68392
[18] Munro, J.I.; Raman, V., Succinct representation of balanced parentheses and static trees, SIAM J. comput., 31, 3, 762-776, (2001) · Zbl 1017.68037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.