On the study of tree pattern matching algorithms and applications

Solving Tree Pattern Query problem is the central part of XML database query. This thesis presents several new algorithms to solve Tree Pattern Query problem and its variations. All of them have better time complexity than any existing algorithms. This thesis also describes the design, implementation, and application of two new algorithms to detect cloned code. The algorithms operate on the abstract syntax trees formed by many compilers as an intermediate representation. They extend prior work by identifying clones even when arbitrary subtrees have been changed. On a 440,000-line code corpus, 20-50% of the clones found eluded previous methods.