Document Tree Reconstruction and Fast Twig Pattern Matching

摘要

In this article, we discuss an efficient algorithm for tree mapping problem in XML databases. Given a target tree T and a pattern tree Q, the algorithm can find all the embeddings of Q in T in O(|D||Q|) time, where D is a largest data stream associated with a node of Q. Furthermore, the algorithm can be easily adapted to an indexing environment with XB-trees being used.