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
10710
Venue
VLDB
Year
2013
Pagerank
0.00010349881
Overall Rank
1,838 | 87.22%
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,024 Path Problems in Temporal Graphs 2014 VLDB 0.00014609643
1,654 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.000109978
1,823 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010413508
1,880 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010226347
2,639 Scaling Distance Labeling on Small-World Networks 2019 SIGMOD 8.3975113e-05
3,342 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.197276e-05
3,671 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 6.8560247e-05
4,193 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 6.37019e-05
5,932 Hub Labeling for Shortest Path Counting 2020 SIGMOD 5.2670741e-05
6,138 Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks 2021 SIGMOD 5.1915368e-05
6,494 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.0417258e-05
6,873 Towards Maximum Independent Sets on Massive Graphs 2015 VLDB 4.8989748e-05
7,277 Exact Top-k Nearest Keyword Search in Large Networks 2015 SIGMOD 4.7794907e-05
7,441 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 4.7302202e-05
7,673 Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling 2017 SIGMOD 4.6826056e-05
8,256 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 4.5490743e-05
8,967 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 4.4190656e-05
10,075 Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach 2026 SIGMOD 4.1945683e-05
10,209 Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC 2026 SIGMOD 4.1945683e-05
11,038 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.1945683e-05
11,239 TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks 2023 VLDB 4.1945683e-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
376 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00025097452
433 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00023310419
945 Path Oracles for Spatial Networks 2009 VLDB 0.00015137526
1,054 On k-skip Shortest Paths 2011 SIGMOD 0.00014422699
1,378 A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012 SIGMOD 0.00012294512
2,756 K-Reach: Who is in Your Small World 2012 VLDB 8.1682536e-05
4,067 Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach 2012 SIGMOD 6.4795399e-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.1506256e-05
9,483 I/O Efficient Label-Constrained Reachability Queries in Large Graphs 2024 VLDB 4.3341665e-05
7,428 DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs 2022 VLDB 4.7320892e-05
2,957 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD 7.8198686e-05
788 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00016650034
5,035 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 5.7470184e-05
2,639 Scaling Distance Labeling on Small-World Networks 2019 SIGMOD 8.3975113e-05
1,378 A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012 SIGMOD 0.00012294512
11,038 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.1945683e-05
1,823 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010413508