Bottom-up Subtree Isomorphism for Unordered Labeled Trees

A bottom-up subtree P of a labeled unordered tree T is such that, for each internal vertex u of P, all the children of u in T are also vertices of P, and the labels in corresponding positions also match. We aim at finding all the occurrences of a pattern tree P of m vertices as a bottom-up subtree of a text tree T of n vertices, m ≤ n. If the labels are single characters of a constant or of an n-integer alphabet the problem is solved in O(m + log n) time and (m) additional space, after a preprocessing of T is done in (n) time and (n) additional space. Note that the number of occurrences of P in T does not appear in the search time. For more complex labels the running times increase, becoming a function of the total length of all the labels in T and P if such labels are sequences of characters. Regarding T as a static text and P as the contents of a query on T, and assuming m = o(n), the response time for each P is sublinear in the size of the overall structure.