Hop-constrained s-t simple path (HC-s-t path) enumeration is a core problem in graph analysis, commonly applied to unlabelled graphs without considering label constraints. However, in many practical scenarios, graphs are edge-labelled, requiring queries to satisfy specific label constraints on the paths between vertices. This introduces new computational challenges that traditional HC-s-t path algorithms are not equipped to handle, especially in distributed environments dealing with large-scale graphs. To address these challenges, we propose a distributed algorithm for labelled hop-constrained s-t path (LHC-s-t path) enumeration. Our approach introduces an online label-based index to prune unnecessary computations, reducing both redundant processing and communication overhead. This enables efficient LHC-s-t path enumeration across distributed systems. Extensive experiments on large real-world graphs demonstrate that our algorithm significantly outperforms existing methods, achieving over an order of magnitude improvement in performance and scalability.

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

Distributed Hop-Constrained s-t Simple Path Enumeration in Labelled Graphs

  • Xia Li,
  • Zhengyi Yang,
  • Kongzhang Hao,
  • Xin Shu,
  • Xin Cao,
  • Wenjie Zhang

摘要

Hop-constrained s-t simple path (HC-s-t path) enumeration is a core problem in graph analysis, commonly applied to unlabelled graphs without considering label constraints. However, in many practical scenarios, graphs are edge-labelled, requiring queries to satisfy specific label constraints on the paths between vertices. This introduces new computational challenges that traditional HC-s-t path algorithms are not equipped to handle, especially in distributed environments dealing with large-scale graphs. To address these challenges, we propose a distributed algorithm for labelled hop-constrained s-t path (LHC-s-t path) enumeration. Our approach introduces an online label-based index to prune unnecessary computations, reducing both redundant processing and communication overhead. This enables efficient LHC-s-t path enumeration across distributed systems. Extensive experiments on large real-world graphs demonstrate that our algorithm significantly outperforms existing methods, achieving over an order of magnitude improvement in performance and scalability.