2010 · 120 citations · 18 references
ComputingComputer ScienceAlgorithmsComputational GeometryWeb AnalyticsGraph AlgorithmsGraph AnalyticsGraph TheoryNearest Neighbor SearchOnline AlgorithmsShortest Path AlgorithmsGraph QueryingGraph SketchesNetwork GraphsOnline Graph AlgorithmsPath ComputationReal-time ProcessingScalable Graph AlgorithmsSketch-based Querying
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 nodes in real time. Since the standard shortest path algorithms are expensive, our approach moves the time-consuming shortest-path computation offline, and at query time only looks up precomputed values and performs simple and fast computations on these precomputed values. More specifically, during the offline phase we compute and store a small “sketch ” for each node in the graph, and at query-time we look up the sketches of the source and destination nodes and perform a simple computation using these two sketches to estimate the distance. Categories and Subject Descriptors G.2.2 [Graph Theory]: Graph algorithms, path and circuit problems
18
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
Syntactic clustering of the Web
Andrei Broder, S. Glassman, Mark S. Manasse et al. · Computer Networks and ISDN Systems · 1997 · 1.4K citations
Mikkel Thorup, Uri Zwick · Journal of the ACM · 2005 · 618 citations