Planting Trees for scalable and efficient Canonical Hub Labeling

Summary: PLaNT constructs minimal canonical hub labels via embarrassingly parallel, dependency-free labeling, avoiding PLL’s sequential root order. Collaborative partitioning enables in-memory distributed labeling/querying on massive weighted graphs, with substantially smaller labels and up to 9.5× cluster speedup. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12439
Venue: VLDB
Year: 2020
Pagerank: 5.3345443e-05
Overall Rank: 9,003 | 38.24%
DOI: 10.14778/3372716.3372722

Incoming Non-self Citations Over Time

Authors

1. Kartik Lakhotia (University of Southern California)
2. Rajgopal Kannan (U.S. Army Research Laboratory)
3. Qing Dong (University of Southern California)
4. Viktor Prasanna (University of Southern California)

BibTeX Citation

@article{lakhotia_vldb20,
        title = {{Planting Trees for scalable and efficient Canonical Hub Labeling}},
        author = {Lakhotia, Kartik and Kannan, Rajgopal and Dong, Qing and Prasanna, Viktor},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {4},
        pages = {492--505},
        doi = {10.14778/3372716.3372722},
        url = {https://doi.org/10.14778/3372716.3372722},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,844	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.7566172e-05
7,624	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	5.5805027e-05
11,097	A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
109	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.000331207
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
370	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019937972
1,309	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00011210911
1,511	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010538011
1,553	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.0001037809
1,622	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010201102
2,152	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	9.0778596e-05
2,200	Efficient Network-Aware Search in Collaborative Tagging Sites	2008	VLDB	8.9664473e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,111	Scaling Queries over Big RDF Graphs with Semantic Hash Partitioning	2013	VLDB
2	1,036	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD
3	6,603	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB
4	1,553	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB
5	4,403	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD
6	11,248	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB
7	11,097	A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks	2025	VLDB
8	5,571	Hub Labeling for Shortest Path Counting	2020	SIGMOD
9	1,309	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB
10	2,152	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD