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  where  is the number of equivalence classes in the coarsest simulation relation Rg⊎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 , where  is the number of equivalence classes in the coarsest simulation relation Rg on g, taking k=|Vg|2 in the general case and if g is acyclic.