The distributed subgraph matching algorithm based on the partial evaluation framework significantly improves subgraph matching efficiency by partitioning graph data across multiple computing nodes and executing query tasks in parallel. However, despite its parallel advantages in handling large-scale graph data, data partitioning also poses challenges. Specifically, since graph data is divided into multiple partitions, for highly selective queries, some partitions struggle to utilize specific vertex information to narrow the search space, resulting in a large number of invalid intermediate results. Therefore, this paper proposes an optimization method for distributed subgraph matching based on vertex hotness caching. This method leverages the principle of query locality, identifies frequently accessed vertices through analyzing query logs, and designates them as high-hotness vertices. It then caches these high-hotness vertices and their multi-hop neighborhood information on the master node. This allows highly selective queries that can be covered by the cache to be directly computed on the master node, avoiding the difficulty that the partial evaluation framework has in utilizing high-selectivity vertices to narrow the search space.

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

Enhancing Partial Evaluation Subgraph Matching Through Vertex Hotness Caching

  • Hui Wang,
  • Xin Wang,
  • Jinshuo Zhao,
  • Yang Liu

摘要

The distributed subgraph matching algorithm based on the partial evaluation framework significantly improves subgraph matching efficiency by partitioning graph data across multiple computing nodes and executing query tasks in parallel. However, despite its parallel advantages in handling large-scale graph data, data partitioning also poses challenges. Specifically, since graph data is divided into multiple partitions, for highly selective queries, some partitions struggle to utilize specific vertex information to narrow the search space, resulting in a large number of invalid intermediate results. Therefore, this paper proposes an optimization method for distributed subgraph matching based on vertex hotness caching. This method leverages the principle of query locality, identifies frequently accessed vertices through analyzing query logs, and designates them as high-hotness vertices. It then caches these high-hotness vertices and their multi-hop neighborhood information on the master node. This allows highly selective queries that can be covered by the cache to be directly computed on the master node, avoiding the difficulty that the partial evaluation framework has in utilizing high-selectivity vertices to narrow the search space.