Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond

Summary: Novel label-constrained 2-hop indexes use pruning and vertex-ordering strategies to avoid exponential label-set enumeration and bound query time by index-entry size. Delivers microsecond LCR queries on billion-edge graphs, with up to 10^5× speedups. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12464
Venue: VLDB
Year: 2020
Pagerank: 5.824568e-05
Overall Rank: 6,603 | 54.70%
DOI: 10.14778/3380750.3380753

Incoming Non-self Citations Over Time

Authors

1. You Peng (University of New South Wales)
2. Ying Zhang (University of Technology Sydney)
3. Xuemin Lin (University of New South Wales)
4. Lu Qin (University of Technology Sydney)
5. Wenjie Zhang (University of New South Wales)

BibTeX Citation

@article{peng_vldb20,
        title = {{Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond}},
        author = {Peng, You and Zhang, Ying and Lin, Xuemin and Qin, Lu and Zhang, Wenjie},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {6},
        pages = {812--825},
        doi = {10.14778/3380750.3380753},
        url = {https://doi.org/10.14778/3380750.3380753},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,579	Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions	2021	SIGMOD	6.6203846e-05
5,044	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.3883109e-05
7,226	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	5.6667372e-05
7,322	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB	5.644647e-05
8,650	Towards Generating Hop-constrained s-t Simple Path Graphs	2023	SIGMOD	5.3916003e-05
9,625	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	5.2434488e-05
10,789	Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks	2025	SIGMOD	5.093636e-05
10,845	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	5.093636e-05
11,198	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD	5.093636e-05
11,225	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	5.093636e-05
11,248	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	5.093636e-05
11,583	Answering Regular Path Queries through Exemplars	2022	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 23 of 23 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
269	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022786599
679	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00015055389
706	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014789612
747	Querying Graph Databases	2013	PODS	0.00014400452
1,211	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011648789
1,301	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00011255351
1,309	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00011210911
1,378	Effective Community Search over Large Spatial Graphs	2017	VLDB	0.00010971508
1,533	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010467148
1,647	Effective and Efficient Community Search over Large Heterogeneous Information Networks	2020	VLDB	0.00010125633
2,024	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	9.2907829e-05
2,490	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	8.5090456e-05
2,700	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	8.2411888e-05
3,021	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	7.8401031e-05
3,278	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	7.5712342e-05
3,473	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	7.3864987e-05
3,821	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	7.0933895e-05
3,979	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.9754185e-05
4,289	Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs	2016	SIGMOD	6.779194e-05
4,498	Constrained Shortest Path Query in a Large Time-Dependent Graph	2019	VLDB	6.6613027e-05
6,935	C-Explorer: Browsing Communities in Large Graphs	2017	VLDB	5.7350034e-05
7,976	Correlation Constraint Shortest Path over Large Multi-Relation Graphs	2019	VLDB	5.5152959e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,553	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB
2	1,796	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD
3	4,403	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD
4	5,044	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB
5	3,979	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB
6	746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
7	2,700	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD
8	2,490	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD
9	7,322	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB
10	9,625	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB