A NEW ALGORITHM FOR TWIG PATTERN MATCHING

Tree pattern matching is one of the most fundamental tasks for XML query processing. Prior work has typically decomposed the twig pattern into binary structural (parent-child and ancestor-descendent) relationships or paths, and then stitch together these basic matches by join operations. In this paper, we propose a new algorithm that explores both the document tree and the twig pattern in a bottom-up way and show that the join operation can be completely avoided. The new algorithm runs in O(|T||Q|) time and O(|Q|leafT) space, where T and Q are the document tree and the twig pattern query, respectively; and leafT represents the number of leaf nodes in T. Our experiments show that our method is effective, scalable and efficient in evaluating twig pattern queries.