Abstract
Given two rooted, labeled trees P and T the tree path subsequence problem is to determine which paths in P are subsequences of which paths in T. Here a path begins at the root and ends at a leaf. In this paper we propose this problem as a useful query primitive for XML data, and provide new algorithms improving the previously best known time and space bounds.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Arlazarov, V.L., Dinic, E.A., Kronrod, M.A., Faradzev, I.A.: On economic construction of the transitive closure of a directed graph (in russian). English translation in soviet math. dokl. 11, 1209–1210 (1975); Dokl. Acad. Nauk. 194, 487–488 (1970)
Baeza-Yates, R.A.: Searching subsequences. Theor. Comput. Sci. 78(2), 363–376 (1991)
Chen, W.: Multi-subsequence searching. Inf. Process. Lett. 74(5-6), 229–233 (2000)
Clark, J., DeRose, S.: XML path language (XPath) (1999), avialiable as: http://www.w3.org/TR/xpath
Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. In: Proc. of ACM Symp. on Theory of Computing, pp. 246–251 (1983)
Hagerup, T., Miltersen, P.B., Pagh, R.: Deterministic dictionaries. J. Algorithms 41(1), 69–85 (2001)
Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM Journal of Computing 13(2), 338–355 (1984)
Kilpeläinen, P., Mannila, H.: Ordered and unordered tree inclusion. SIAM Journal of Computing 24, 340–356 (1995)
Schlieder, T., Meuss, H.: Querying and ranking XML documents. J. Am. Soc. Inf. Sci. Technol. 53(6), 489–503 (2002)
Schlieder, T., Naumann, F.: Approximate tree embedding for querying XML data. In: ACM SIGIR Workshop On XML and Information Retrieval (2000)
Termier, A., Rousset, M., Sebag, M.: Treefinder: a first step towards XML data mining. In: IEEE International Conference on Data Mining, ICDM (2002)
Yang, H., Lee, L., Hsu, W.: Finding hot query patterns over an xquery stream. The VLDB Journal 13(4), 318–332 (2004)
Yang, L.H., Lee, M.L., Hsu, W.: Efficient mining of XML query patterns for caching. In: Proceedings of the 29th VLDB Conference, pp. 69–80 (2003)
Zezula, P., Amato, G., Debole, F., Rabitti, F.: Tree signatures for XML querying and navigation. In: Bellahsène, Z., Chaudhri, A.B., Rahm, E., Rys, M., Unland, R. (eds.) XSym 2003. LNCS, vol. 2824, pp. 149–163. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bille, P., Gørtz, I.L. (2006). Matching Subsequences in Trees. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds) Algorithms and Complexity. CIAC 2006. Lecture Notes in Computer Science, vol 3998. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11758471_25
Download citation
DOI: https://doi.org/10.1007/11758471_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34375-2
Online ISBN: 978-3-540-34378-3
eBook Packages: Computer ScienceComputer Science (R0)