R2Mine: A Reduced Redundancy Computation Graph Pattern Matching System
Dongyang Zhang, Jianhuan Zhuo, Yile Li, Yinliang Yue, Weiping Wang · 2024
Graph pattern matching is a fundamental task in various fields, enabling the exploration of complex graph structures. Existing graph pattern matching systems focus on generating better schedule plan to filter out invalid matching paths through pattern analysis. However, these systems ignore the numerous identical computations among different filtered matching paths.To overcome this challenge, we propose Reduced Redundancy Computation (R2Mine), aims to effectively recognize and reuse identical computations among different filtered matching paths. Specifically, by analyzing pattern, R2Mine extracts overlap nodes among all valid matching instances, named Reusable Basic Pattern (RBP). Then R2Mine employs RBP to generate redundant discriminant conditions to recognize identical computations involved overlap nodes. Utilizing these conditions allows the system to reuse redundant computations among different matching paths. To evaluate our approach, we conduct extensive experiments on 6 real-world graph datasets. The results demonstrate that R2Mine outperforms state-of-the-art graph pattern matching systems, Peregrine and GraphPi, respectively achieving a 13.61× and 1.75× on average improvement in performance.