A Sketch-Based Distance Oracle for Web-Scale Graphs

We study the fundamental problem of computing distances between nodes in large graphs such as the web graph and social networks. Our objective is to be able to answer distance queries between pairs of