Simulation relations for pattern matching in directed graphs

We consider the problem of finding the occurrences of a pattern tree t in a directed graph g, and propose two algorithms, one for preprocessing and one for searching for t in g. It is assumed that the object graph itself is large and static, and that the pattern tree is small and frequently updated. To model varying abstraction levels in the data, we work with partially ordered alphabets and compute simulation relations rather than equivalence relations. In particular, vertices and edges are labelled with elements from a pair of preorders instead of unstructured alphabets. Under the above assumptions, we obtain a search algorithm that runs in time O(height (t) . vertical bar t vertical bar . vertical bar(V-g(+/-)t/R-g(+/-)t vertical bar(2)) where vertical bar (V-g(+/-)t/R-g(+/-)t)vertical bar is the number of equivalence classes in the coarsest simulation relation R-g(+/-)t on the graph g((+/-))t, the disjoint union of g and t. This means that the size of the object graph only affects the running time of the search algorithm indirectly, because of the groundwork done by the preprocessing routine in time O(k . vertical bar g vertical bar . vertical bar(V-g/R-g)vertical bar(2)), where vertical bar(V-g/R-g) is the number of equivalence classes in the coarsest simulation relation R-g on g, taking k = vertical bar V-g vertical bar(2) in the general case and k = height (g) if g is acyclic. (C) 2013 Elsevier B.V. All rights reserved.