IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point\n Distance Querying on Large Graphs

2012/11/10 by Ada Wai-Chee Fu, Huanhuan Wu, Fu, Ada Wai-Chee +7 · 2 citations
Computer Science · #Advanced Database Systems and Queries #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.1211.2367

openalex publication_date 2012/11/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the problem of computing shortest path or distance between two query\nvertices in a graph, which has numerous important applications. Quite a number\nof indexes have been proposed to answer such distance queries. However, all of\nthese indexes can only process graphs of size barely up to 1 million vertices,\nwhich is rather small in view of many of the fast-growing real-world graphs\ntoday such as social networks and Web graphs. We propose an efficient index,\nwhich is a novel labeling scheme based on the independent set of a graph. We\nshow that our method can handle graphs of size three orders of magnitude larger\nthan those existing indexes.\n

Citations

• Approximate distance oracles

Cited by

• BD-Index: Scalable Biharmonic Distance Queries on Large Graphs via Divide-and-Conquer Indexing
• Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach

Related

• Efficiently Answering Quality Constrained Shortest Distance Queries in Large Graphs
• Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks
• A Highly Scalable Labelling Approach for Exact Distance Queries in Complex Networks
• Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling
• Simpler, faster and shorter labels for distances in graphs