TY - RPRT
T1 - The Tree Inclusion Problem
T2 - In Optimal Space and Faster
AU - Bille, Philip
AU - Gørtz, Inge Li
PY - 2005/1
Y1 - 2005/1
N2 - Given two rooted, ordered, and labeled trees P and T the tree inclusion problem is to determine if P can be obtained from T by deleting nodes in T. This problem has recently been recognized as an important query primitive in XML databases.Kilpeläinen and Mannila (SIAM J. of Comp. 1995) presented the first polynomial time algorithm using quadratic time and space. Since then several improved results have been obtained for special cases when P and T have a small number of leaves or small depth. However, in the worst case these algorithms still use quadratic time and space. In this paper we present a new approach to the problem which leads to a new algorithm which use optimal linear space and has subquadratic running time. Our algorithm improves all previous time and space bounds.Most importantly, the space is improved by a linear factor. This will make it possible to query larger XML databases and speed up the query time since more of the computation can be kept in main memory.
AB - Given two rooted, ordered, and labeled trees P and T the tree inclusion problem is to determine if P can be obtained from T by deleting nodes in T. This problem has recently been recognized as an important query primitive in XML databases.Kilpeläinen and Mannila (SIAM J. of Comp. 1995) presented the first polynomial time algorithm using quadratic time and space. Since then several improved results have been obtained for special cases when P and T have a small number of leaves or small depth. However, in the worst case these algorithms still use quadratic time and space. In this paper we present a new approach to the problem which leads to a new algorithm which use optimal linear space and has subquadratic running time. Our algorithm improves all previous time and space bounds.Most importantly, the space is improved by a linear factor. This will make it possible to query larger XML databases and speed up the query time since more of the computation can be kept in main memory.
M3 - Report
T3 - IT University Technical Report Series
BT - The Tree Inclusion Problem
PB - IT-Universitetet i København
CY - Copenhagen
ER -