Please use this identifier to cite or link to this item: https://doi.org/10.1145/3448016.3457290
Title: PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration
Authors: Sun, S 
Chen, Y 
He, B 
Hooi, B 
Keywords: s-t path enumeration
hop-constrained
light-weight index
Issue Date: 1-Jan-2021
Publisher: ACM
Citation: Sun, S, Chen, Y, He, B, Hooi, B (2021-01-01). PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration. Proceedings of the ACM SIGMOD International Conference on Management of Data abs/2103.11137 : 1758-1770. ScholarBank@NUS Repository. https://doi.org/10.1145/3448016.3457290
Rights: Attribution-NonCommercial 4.0 International
Abstract: We study the hop-constrained s-t path enumeration (HcPE ) problem, which takes a graph G, two distinct vertices s,t and a hop constraint k as input, and outputs all paths from s to t whose length is at most k. 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.
Source Title: Proceedings of the ACM SIGMOD International Conference on Management of Data
URI: https://scholarbank.nus.edu.sg/handle/10635/215368
ISSN: 0730-8078
DOI: 10.1145/3448016.3457290
Rights: Attribution-NonCommercial 4.0 International
Appears in Collections:Elements
Staff Publications

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
2103.11137v2.pdf1.39 MBAdobe PDF

OPEN

Post-printView/Download

Google ScholarTM

Check

Altmetric


This item is licensed under a Creative Commons License Creative Commons