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