关键词: 动态图, 图模式匹配, 增量算法, 结构分解, 大图数据

Abstract: In the age of big data, the scale of data graphs expands rapidly. The incremental graph pattern matching technique becomes a research focus, since it avoids re-computing matches in the whole data graph, as a result reducing the matching time and improving the overall execution performance when the data graph changes. However, the efficiency of existing incremental matching algorithms will reduce when dealing with large scale patterns. To tackle this problem, this paper proposes a novel incremental graph pattern matching algorithm based on structural decomposition named Inc_CFLS. The Inc_CFLS algorithm constructs an efficient index based on intermediate matched results, and the index is utilized to speed up subsequent pattern matching calculations. The Inc_CFLS algorithm further makes use of the index information to classify the edge insertion events over the data graph into different event classes, and designs query pruning optimization strategies for each of these event classes, which effectively improves the matching efficiency. The experimental results over physical-world datasets show that the proposed Inc_CFLS algorithm runs 1—2 times faster than the state-of-the-art incremental graph matching algorithm. Especially, the Inc_CFLS algorithm can effectively handle graph pattern matching analysis over large dynamic graphs.

Key words: dynamic graphs, graph pattern matching, incremental algorithm, structure decomposition, big graph data