AnchorMine: An Efficient Graph Pattern Matching System for Specific Vertex Matching
Dongyang Zhang, Jianhuan Zhuo, Mingzhe Xing, Yinliang Yue, Peng Fu, Weiping Wang · 2024
As data scales continue to expand, graph structures are widely applied across multiple domains due to their effective organization of complex data. Graph Pattern Matching (GPM) is a fundamental task in graph analysis to identify all user-interesting subgraphs in a graph. Current GPM systems achieve this goal by generating efficient traversal path strategies. However, when matching patterns that include a specific vertex (S-GPM), current GPM systems often traverse paths without the specific vertex or duplicate traverse some paths. These redundant traversals lead to decreased execution efficiency. In this paper, we introduce AnchorMine, a GPM system designed for S-GPM tasks, aiming to significantly reduce redundant path traversal by identifying and reusing paths that include specific vertex. Specifically, AnchorMine first analyzes the pattern to identify vertices in different positions within the pattern, named Anchors (ACs). Then AnchorMine extracts features of reusable paths based on each Anchor (AC). These features enable the system to identify paths that can be reused during matching. Using these features, it further generates the parameters required for matching based on path reuse, achieving efficient matching for S-GPM tasks. In experiments on 8 real-world graph datasets, AnchorMine significantly outperformed GraphPi, SandSlash, and Peregrine on 6 datasets used for performance testing, with matching performance improvements of 3249.22 ×, 2018.73 × and 7573.27 ×, respectively. On the remaining 2 datasets used for scalability testing, AnchorMine scales well.