Two Birds One Stone: Dual-Role Path Based Subgraph Matching Using Partial Evaluation
摘要
In recent years, considerable attention has been drawn to the development of algorithms for subgraph matching in distributed scenarios. Many distributed engines inherently support join-based methods, which can lead to numerous redundant intermediate results and redundant processing. In contrast, exploration-based algorithms, though effective at limiting such extraneous results, necessitate arbitrary access to data. This paper introduces an efficient subgraph matching algorithm that leverages dual-role paths, which is implemented within the framework of partial evaluation and unifies the strengths of binary join and preprocessing enumeration approaches. During the partial evaluation phase, we decompose queries into dual-role paths to enhance the parallel capabilities of the system. For assembly, dual-role paths are treated as vertices for preprocessing enumeration, which reduces invalid intermediate results and avoids a large communication cost. The proposed algorithm has been implemented in a state-of-the-art distributed graph database system, and the comprehensive testing indicates that our proposed algorithm has increased efficiency by up to three times based on the partial evaluation framework.