Matching subsequences in trees |
| |
Authors: | Philip Bille,Inge Li G rtz |
| |
Affiliation: | aThe IT University of Copenhagen, Rued Langgaards Vej 7, DK-2300 Copenhagen S, Denmark;bTechnical University of Denmark, Department of Informatics and Mathematical Modelling, Building 322, DK-2800 Kgs. Lyngby, Denmark |
| |
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. |
| |
Keywords: | Subsequences Tree matching XML queries |
本文献已被 ScienceDirect 等数据库收录! |
|