IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying

Summary: IS-LABEL, a novel independent-set based labeling scheme for point-to-point distance querying. Its labeling leverages graph independent sets to support fast distance queries, achieving order-of-magnitude scalability beyond prior indexes (beyond ~1M vertices) for large real-world graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: he1171abbe0cfcaf0
Venue: VLDB
Year: 2013
Pagerank: 9.9828268e-05
Overall Rank: 1,647 | 88.94%
DOI: 10.14778/2536336.2536340

Incoming Non-self Citations Over Time

Authors

1. Ada Wai-Chee Fu (Chinese University of Hong Kong)
2. Huanhuan Wu (Chinese University of Hong Kong)
3. James Cheng (Chinese University of Hong Kong)
4. Raymond Chi-Wing Wong (Hong Kong University of Science and Technology)

BibTeX Citation

@article{fu_vldb13,
        title = {{IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying}},
        author = {Fu, Ada Wai-Chee and Wu, Huanhuan and Cheng, James and Wong, Raymond Chi-Wing},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {6},
        pages = {457--468},
        doi = {10.14778/2536336.2536340},
        url = {https://doi.org/10.14778/2536336.2536340},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,106	Path Problems in Temporal Graphs	2014	VLDB	0.0001199079
1,340	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.0001096845
1,563	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010219537
1,585	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010158887
2,190	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.8832666e-05
2,944	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD	7.8277412e-05
3,348	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	7.3891319e-05
3,689	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	7.0921741e-05
5,705	Hub Labeling for Shortest Path Counting	2020	SIGMOD	6.0274828e-05
5,804	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	5.9865208e-05
5,897	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	5.952769e-05
6,962	Towards Maximum Independent Sets on Massive Graphs	2015	VLDB	5.630587e-05
6,991	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.6247902e-05
7,053	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	5.6103309e-05
7,305	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD	5.5576178e-05
7,640	Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling	2017	SIGMOD	5.4766381e-05
9,175	Planting Trees for scalable and efficient Canonical Hub Labeling	2020	VLDB	5.2123828e-05
10,575	Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach	2026	SIGMOD	4.9769913e-05
10,696	Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC	2026	SIGMOD	4.9769913e-05
11,586	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	4.9769913e-05
11,758	TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks	2023	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
382	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019477423
447	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018151383
991	Path Oracles for Spatial Networks	2009	VLDB	0.00012642908
1,253	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011331798
1,426	On k-skip Shortest Paths	2011	SIGMOD	0.00010705427
2,606	K-Reach: Who is in Your Small World	2012	VLDB	8.2264537e-05
3,936	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD	6.9140006e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,050	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB
2	9,812	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB
3	6,770	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB
4	2,535	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD
5	776	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
6	4,491	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD
7	2,190	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD
8	1,253	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD
9	11,586	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB
10	1,585	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB