Exact Rooted Subtree Matching in Sublinear Time

The problem of exact subtree matching is the one of deciding if a pattern tree P of m vertices is a subtree of a text tree T of n vertices, and, in the affirmative case, finding all the occurrences of P in T, and it is shown how the problem can be solved in Theta(m + log n) time once a proper data structure is built for T in a preprocessing phase which requires TheTA(n) time and space.

Abstract

The problem of exact subtree matching is the one of deciding if a
\npattern tree P of m vertices is a subtree of a text tree T of n vertices, 
\nm<= n, and, in the affirmative case, finding all the occurrences of P 
\nin T. We consider ordered and non-ordered rooted trees with labeled 
\nvertices (the case of unlabeled vertices is a special case of this), 
\nand show how the problem can be solved in Theta(m + log n) time 
\nonce a proper data structure is built for T in a preprocessing phase 
\nwhich requires Theta(n) time and space. 
\nRegarding T as an immutable text on which several queries are made, P as 
\nthe contents of one such query, and assuming m=o(n), we can speak of 
\nsearch time sublinear in the size m+n of the overall structure. The 
\nnumber of occurrences of P in T does not appear in the search time 
\nbecause all such occurrences can be directly reconstructed from a 
\nconstant output information.