PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration
Shixuan Sun, Yuhang Chen, Bingsheng He, Bryan Hooi
Abstract
We study the hop-constrained s-t path enumeration (HcPE) problem, which takes a graph , two distinct vertices , and a hop constraint as input, and outputs all paths from to whose length is at most . The state-of-the-art algorithms suffer from severe performance issues caused by the costly pruning operations during enumeration for the workloads with the large search space. Consequently, these algorithms hardly meet the real-time constraints of many online applications. In this paper, we propose PathEnum, an efficient index-based algorithm towards real-time HcPE. For an input query, PathEnum first builds a light-weight index aiming to reduce the number of edges involved in the enumeration, and develops efficient index-based approaches for enumeration, one based on depth-first search and the other based on joins. We further develop a query optimizer based on a join-based cost model to optimize the search order. We conduct experiments with 15 real-world graphs. Our experiment results show that PathEnum outperforms the state-of-the-art approaches by orders of magnitude in terms of the query time, throughput and response time.