Incremental Graph Pattern Matching: Data Structures and Initial Experiments

Abstract

Despite the large variety of existing graph transformation tools, the implementation of their pattern matching engine typically follows the same principle. First a matching occurrence of the left-hand side of the graph transformation rule is searched by some graph pattern matching algorithm. Then potential negative application conditions are checked that might eliminate the previous occurrence. However, when a new transformation step is started, all the information on previous matchings is lost, and the complex graph pattern matching phase is restarted from scratch each time. In the paper, we present the foundational data structures and initial experiments for an incremental graph pattern matching engine which keeps track of existing matchings in an incremental way to reduce the execution time of graph pattern matching.