Given two rooted, labeled trees
the tree path subsequence problem is to determine which paths in
are subsequences of which paths in
. 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.