PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration

Summary: PathEnum delivers real-time hop-constrained s-t path enumeration (HcPE) via a light-weight index that prunes edges, plus two enumeration modes: DFS-based and join-based. A join-based cost model optimizes search order; experiments on 15 real-world graphs show orders-of-magnitude improvements in time, throughput, and latency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6243
Venue: SIGMOD
Year: 2021
Pagerank: 6.0343238e-05
Overall Rank: 5,938 | 59.27%
DOI: 10.1145/3448016.3457290

Incoming Non-self Citations Over Time

Authors

1. Shixuan Sun (National University of Singapore)
2. Yuhang Chen (National University of Singapore)
3. Bingsheng He (National University of Singapore)
4. Bryan Hooi (National University of Singapore)

BibTeX Citation

@inproceedings{sun_sigmod21,
        title = {{PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration}},
        author = {Sun, Shixuan and Chen, Yuhang and He, Bingsheng and Hooi, Bryan},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3457290},
        url = {https://dl.acm.org/doi/10.1145/3448016.3457290},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,275	RapidFlow: An Efficient Approach to Continuous Subgraph Matching	2022	VLDB	6.2873652e-05
8,650	Towards Generating Hop-constrained s-t Simple Path Graphs	2023	SIGMOD	5.3916003e-05
9,118	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	5.3201316e-05
10,354	Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings	2026	SIGMOD	5.093636e-05
10,748	Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs	2025	SIGMOD	5.093636e-05
10,963	RICH: Real-time Identification of negative Cycles for High-efficiency Arbitrage	2025	VLDB	5.093636e-05
11,225	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
211	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024797217
593	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00016027871
809	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00013874588
927	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.00013161079
1,237	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00011545768
2,035	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	9.2787188e-05
2,182	TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data	2018	SIGMOD	9.010121e-05
2,940	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	7.9381573e-05
3,821	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	7.0933895e-05
3,955	2SCENT: An Efficient Algorithm for Enumerating All Simple Temporal Cycles	2018	VLDB	6.9950293e-05
4,551	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.6355948e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,044	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB
2	7,664	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB
3	352	On Graph Query Optimization in Large Networks	2010	VLDB
4	269	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD
5	4,289	Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs	2016	SIGMOD
6	8,650	Towards Generating Hop-constrained s-t Simple Path Graphs	2023	SIGMOD
7	10,748	Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs	2025	SIGMOD
8	7,418	Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale	2022	VLDB
9	4,551	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB
10	9,118	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD