Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale

Summary: Proposes a hybrid search paradigm and divide-and-conquer distributed algorithm for HC-s-t path enumeration on billion-scale graphs, with pruning and bounded memory to enable high parallelism. Adds idle-machine load balancing and bidirectional search to boost efficiency; experiments demonstrate scalable performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12672
Venue: VLDB
Year: 2022
Pagerank: 4.6817479e-05
Overall Rank: 7,675 | 46.61%
DOI: 10.14778/3489496.3489499

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,089	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	4.39898e-05
10,163	Enumerating Graph Pattern Matches with ML Oracles	2026	SIGMOD	4.1945683e-05
10,467	Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs	2025	SIGMOD	4.1945683e-05
11,038	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,394	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.0001221552
1,665	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.00010967716
1,953	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9665955e-05
2,494	Streaming Graph Partitioning: An Experimental Study	2018	VLDB	8.6508229e-05
2,547	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.5683079e-05
2,801	Scalable Distributed Subgraph Enumeration	2017	VLDB	8.0992955e-05
3,215	Fractal: A General-Purpose Graph Pattern Mining System	2019	SIGMOD	7.3645742e-05
3,839	Experimental Analysis of Streaming Algorithms for Graph Partitioning	2019	SIGMOD	6.7120651e-05
4,020	TopoX: Topology Refactorization for Efficient Graph Partitioning and Processing	2019	VLDB	6.5237459e-05
4,534	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.1049756e-05
4,556	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.0883757e-05
5,751	Effective and Efficient Dynamic Graph Coloring	2018	VLDB	5.3409543e-05
5,811	Fast and Robust Distributed Subgraph Enumeration	2019	VLDB	5.317401e-05
8,885	Bonding Vertex Sets Over Distributed Graph: A Betweenness Aware Approach	2015	VLDB	4.4282232e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,788	Towards Distributed Bitruss Decomposition on Bipartite Graphs	2022	VLDB	4.651009e-05
5,811	Fast and Robust Distributed Subgraph Enumeration	2019	VLDB	5.317401e-05
2,801	Scalable Distributed Subgraph Enumeration	2017	VLDB	8.0992955e-05
10,209	Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC	2026	SIGMOD	4.1945683e-05
11,038	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	4.1945683e-05
891	Maximum Biclique Search at Billion Scale	2020	VLDB	0.00015564292
10,467	Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs	2025	SIGMOD	4.1945683e-05
4,534	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.1049756e-05
6,208	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD	5.1568586e-05
9,089	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	4.39898e-05