Database Paper Browser

Back to papers

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
10711
Venue
VLDB
Year
2013
Pagerank
0.00010340277
Overall Rank
1,843 | 87.20%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank Citing Paper Year Venue Pagerank
1,021 Path Problems in Temporal Graphs 2014 VLDB 0.00014608331
1,653 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.0001098717
1,822 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010404349
1,879 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010227906
2,643 Scaling Distance Labeling on Small-World Networks 2019 SIGMOD 8.3894193e-05
3,346 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.1903469e-05
3,676 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 6.8500097e-05
4,194 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 6.3640644e-05
5,933 Hub Labeling for Shortest Path Counting 2020 SIGMOD 5.2620152e-05
6,144 Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks 2021 SIGMOD 5.1865526e-05
6,491 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.0368875e-05
6,877 Towards Maximum Independent Sets on Massive Graphs 2015 VLDB 4.8945769e-05
7,271 Exact Top-k Nearest Keyword Search in Large Networks 2015 SIGMOD 4.7764555e-05
7,439 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 4.7256836e-05
7,664 Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling 2017 SIGMOD 4.6805647e-05
8,252 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 4.544713e-05
8,973 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 4.4148296e-05
10,075 Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach 2026 SIGMOD 4.1905499e-05
10,209 Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC 2026 SIGMOD 4.1905499e-05
11,041 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.1905499e-05
11,241 TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks 2023 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

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
377 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00025074538
434 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00023277433
946 Path Oracles for Spatial Networks 2009 VLDB 0.00015117675
1,052 On k-skip Shortest Paths 2011 SIGMOD 0.00014403922
1,385 A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012 SIGMOD 0.00012259478
2,762 K-Reach: Who is in Your Small World 2012 VLDB 8.1614818e-05
4,070 Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach 2012 SIGMOD 6.4739921e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
4,478 Reachability Querying: An Independent Permutation Labeling Approach 2014 VLDB 6.1452192e-05
9,485 I/O Efficient Label-Constrained Reachability Queries in Large Graphs 2024 VLDB 4.3300131e-05
7,430 DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs 2022 VLDB 4.7275494e-05
2,958 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD 7.8126329e-05
784 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00016648392
5,035 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 5.7414979e-05
2,643 Scaling Distance Labeling on Small-World Networks 2019 SIGMOD 8.3894193e-05
1,385 A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012 SIGMOD 0.00012259478
11,041 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.1905499e-05
1,822 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010404349