2005/12/15 by Philip Bille, Bille, Philip, Inge Li Goertz +1
Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Management and Algorithms #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0512061
Minor correction of typos, etc
arxiv created 2007/12/07 · arxiv updated 2011/11/09
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.