×

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

Citations:

Zbl 1350.68073
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Alon, B. Schieber, Optimal preprocessing for answering on-line product queries, Tech. Rep., Tel Aviv University, 1987.; 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.; 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.; 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.; 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.; 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.; 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.; 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.; 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.; 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 · Zbl 1445.68072
[17] V. Mäkinen, G. Navarro, Position-restricted substring searching, in: Latin American Symposium on Theoretical Informatics, 2006, pp. 703-714.; 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.