Abstract:Graph simulation is widely adopted to approximately solve complex graph pattern matching problems. To enhance the query efficiency for matching temporal graph patterns, this study proposes a simulation algorithm, SimAssign, which is based on a union graph model, along with a dynamic programming based query optimization framework. The proposed approach consists of two main components: (1) a sequence of temporal graph snapshots is merged into a union graph, on which initial query results are computed using a static graph simulation algorithm; these results are then partitioned according to temporal intervals to generate matching results for each snapshot; (2) a unified cost model is developed to support various graph simulation strategies, and a dynamic programming framework is introduced to identify optimal execution plans based on this model. Extensive experiments on both real and synthetic datasets demonstrate that the cost model accurately estimates the execution costs of static graph simulation, incremental graph simulation, and SimAssign. Moreover, the proposed optimization framework consistently selects optimal strategies. In most cases, SimAssign substantially outperforms both static and incremental simulation methods, with performance improvements reaching up to four times that of the incremental approach on certain datasets.