×

zbMATH — the first resource for mathematics

A framework for succinct labeled ordinal trees over large alphabets. (English) Zbl 1314.68111
Summary: We consider succinct representations of labeled ordinal trees that support a rich set of operations. Our new representations support a much broader collection of operations than previous work. In our approach, labels of nodes are stored in a preorder label sequence, which can be compressed using any succinct representation of strings that supports access, rank and select operations. Thus, we present a framework for succinct representations of labeled ordinal trees that is able to handle large alphabets. This answers an open problem presented by Geary et al., which asks for representations of labeled ordinal trees that remain space-efficient for large alphabets. We further extend our work and present the first succinct representations for dynamic labeled ordinal trees that support several label-based operations including finding the level ancestor with a given label.

MSC:
68P05 Data structures
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barbay, J; Golynski, A; Munro, JI; Rao, SS, Adaptive searching in succinctly encoded binary relations and tree-structured documents, Theor. Comput. Sci., 387, 284-297, (2007) · Zbl 1144.68014
[2] Barbay, J., Rao, S.S.: Succinct encoding for XPath location steps. Technical Report CS-2006-10, University of Waterloo (2006)
[3] Belazzougui, D., Navarro, G.: Optimal lower and upper bounds for representing sequences. ACM Trans. Algorithms (to appear) · Zbl 1365.68260
[4] Benoit, D; Demaine, ED; Munro, JI; Raman, R; Raman, V; Rao, SS, Representing trees of higher degree, Algorithmica, 43, 275-292, (2005) · Zbl 1086.68034
[5] Bille, P, A survey on tree edit distance and related problems, Theor. Comput. Sci., 337, 217-239, (2005) · Zbl 1078.68152
[6] Clark, D.R., Munro, J.I.: Efficient suffix trees on secondary storage (extended abstract). In: Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 383-391. Society for Industrial and Applied Mathematics (1996) · Zbl 0847.68030
[7] Farzan, A; Munro, JI, A uniform paradigm to succinctly encode various families of trees, Algorithmica, 68, 16-40, (2014) · Zbl 1286.68117
[8] Farzan, A., Raman, R., Rao, S.S.: Universal succinct representations of trees? In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 5555, pp. 451-462. Springer, Berlin (2009) · Zbl 1248.68168
[9] Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Compressing and indexing labeled trees, with applications. J. ACM 57(1), 4 (2009) · Zbl 1326.68132
[10] Ferragina, P; Venturini, R, A simple storage scheme for strings achieving entropy bounds, Theor. Comput. Sci., 372, 115-121, (2007) · Zbl 1110.68029
[11] Geary, RF; Raman, R; Raman, V, Succinct ordinal trees with level-ancestor queries, ACM Trans. Algorithms, 2, 510-534, (2006) · Zbl 1321.68223
[12] He, M., Munro, J.I.: Succinct representations of dynamic strings. In: Proceedings of String Processing and Information Retrieval—17th International Symposium. Lecture Notes in Computer Science, vol. 6393, pp. 334-346. Springer, Berlin (2010) · Zbl 1295.68102
[13] He, M; Munro, JI; Rao, SS, Succinct ordinal trees based on tree covering, ACM Trans. Algorithms, 8, 42, (2012) · Zbl 1295.68102
[14] He, M., Munro, J.I., Zhou, G.: Path queries in weighted trees. In: Proceedings of the 22nd International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 7074, pp. 140-149. Springer, Berlin (2011) · Zbl 1350.68073
[15] He, M., Munro, J.I., Zhou, G.: A framework for succinct labeled ordinal trees over large alphabets. In: Proceedings of the 23rd International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 7676, pp. 537-547. Springer, Berlin (2012) · Zbl 1260.68125
[16] He, M., Munro, J.I., Zhou, G.: Succinct data structures for path queries. In: Proceedings of the 20th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 7501, pp. 575-586. Springer, Berlin (2012) · Zbl 1365.68181
[17] Manzini, G, An analysis of the Burrows-Wheeler transform, J. ACM, 48, 407-430, (2001) · Zbl 1323.68262
[18] Navarro, G., Nekrich, Y.: Optimal dynamic sequence representations. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 865-876. Society for Industrial and Applied Mathematics (2013)
[19] Navarro, G., Nekrich, Y.: Optimal dynamic sequence representations. CoRR abs/1206.6982 (2013) · Zbl 1320.68060
[20] Navarro, G., Sadakane, K.: Fully-functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), 16 (2014) · Zbl 1333.68084
[21] Tsur, D.: Succinct representation of labeled trees. CoRR abs/1312.6039 (2013) · Zbl 1303.68043
[22] Zhou, G.: Path Queries in Weighted Trees. Master’s thesis, Waterloo, ON, Canada (2012) · Zbl 1078.68152
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.