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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Two Birds One Stone: Dual-Role Path Based Subgraph Matching Using Partial Evaluation

  • Chengguo Li,
  • Xin Wang,
  • Yongqi Yin,
  • Hui Wang

摘要

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.