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

Summary: A distributed hybrid-search, divide-and-conquer algorithm enumerates hop-constrained simple s-t paths at billion-graph scale, pruning fruitless exploration while bounding memory. Idle-triggered load balancing handles skew, and bidirectional search further accelerates enumeration. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12860
Venue: VLDB
Year: 2022
Pagerank: 5.6236086e-05
Overall Rank: 7,418 | 49.11%
DOI: 10.14778/3489496.3489499

Incoming Non-self Citations Over Time

Authors

1. Kongzhang Hao (Nanjing University; University of New South Wales)
2. Long Yuan (Nanjing University; University of New South Wales)
3. Wenjie Zhang (University of New South Wales)

BibTeX Citation

@article{hao_vldb22,
        title = {{Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale}},
        author = {Hao, Kongzhang and Yuan, Long and Zhang, Wenjie},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {2},
        pages = {169--182},
        doi = {10.14778/3489496.3489499},
        url = {https://doi.org/10.14778/3489496.3489499},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,118	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	5.3201316e-05
10,452	Enumerating Graph Pattern Matches with ML Oracles	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
11,248	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	5.093636e-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
927	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.00013161079
1,246	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011504088
1,432	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.0001080346
2,065	Scalable Distributed Subgraph Enumeration	2017	VLDB	9.2352771e-05
2,097	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	9.1725037e-05
2,221	Streaming Graph Partitioning: An Experimental Study	2018	VLDB	8.9260308e-05
2,522	Fractal: A General-Purpose Graph Pattern Mining System	2019	SIGMOD	8.4713567e-05
3,362	Experimental Analysis of Streaming Algorithms for Graph Partitioning	2019	SIGMOD	7.4833791e-05
3,601	TopoX: Topology Refactorization for Efficient Graph Partitioning and Processing	2019	VLDB	7.27018e-05
3,821	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	7.0933895e-05
4,551	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.6355948e-05
5,296	Fast and Robust Distributed Subgraph Enumeration	2019	VLDB	6.2782852e-05
5,797	Effective and Efficient Dynamic Graph Coloring	2018	VLDB	6.0859157e-05
9,032	Bonding Vertex Sets Over Distributed Graph: A Betweenness Aware Approach	2015	VLDB	5.327953e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,144	Towards Distributed Bitruss Decomposition on Bipartite Graphs	2022	VLDB
2	5,296	Fast and Robust Distributed Subgraph Enumeration	2019	VLDB
3	2,065	Scalable Distributed Subgraph Enumeration	2017	VLDB
4	10,498	Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC	2026	SIGMOD
5	780	Maximum Biclique Search at Billion Scale	2020	VLDB
6	11,248	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB
7	10,748	Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs	2025	SIGMOD
8	4,551	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB
9	5,938	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD
10	9,118	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD