%0 Report %1 potamias2008indexing %A Potamias, Michalis %A Bonchi, Francesco %A Castillo, Carlos %A Gionis, Aristides %D 2008 %K graph, search, social %T Fast shortest path distance estimation in large networks %X We study the problem of preprocessing a large graph so that single-pair shortest-path queries can be answered quickly at runtime. Computing shortest paths is a well studied problem, but exact algorithms do not scale well to real-world huge graphs in applications that require very short response time.We focus on approximate methods for distance estimation, in particular in landmarks-based distance indexing. This approach involves choosing some nodes as landmarks and computing (off-line), for each node in the graph its embedding, i.e., the vector of its distances from all the landmarks. At runtime, when the distance between a pair of nodes is needed, we quickly estimate it by combining the embeddings of the two nodes. Given a budget of memory for the index, which translates directly into a budget of landmarks, different landmark selection strategies can yield dramatically different results in terms of accuracy. We develop and experimentally compare a large number of simple heuristics that scale well to large graphs. For a given target accuracy, our techniques require far less space than random landmark selection. We demonstrate the robustness of our techniques experimentally using five different real world graphs having tens of millions of edges.We study an application of our method in two problems arising naturally in large-scale graphs, social search and community detection.

@techreport{potamias2008indexing, abstract = {We study the problem of preprocessing a large graph so that single-pair shortest-path queries can be answered quickly at runtime. Computing shortest paths is a well studied problem, but exact algorithms do not scale well to real-world huge graphs in applications that require very short response time.We focus on approximate methods for distance estimation, in particular in landmarks-based distance indexing. This approach involves choosing some nodes as landmarks and computing (off-line), for each node in the graph its embedding, i.e., the vector of its distances from all the landmarks. At runtime, when the distance between a pair of nodes is needed, we quickly estimate it by combining the embeddings of the two nodes. Given a budget of memory for the index, which translates directly into a budget of landmarks, different landmark selection strategies can yield dramatically different results in terms of accuracy. We develop and experimentally compare a large number of simple heuristics that scale well to large graphs. For a given target accuracy, our techniques require far less space than random landmark selection. We demonstrate the robustness of our techniques experimentally using five different real world graphs having tens of millions of edges.We study an application of our method in two problems arising naturally in large-scale graphs, social search and community detection.}, added-at = {2009-08-06T15:16:38.000+0200}, author = {Potamias, Michalis and Bonchi, Francesco and Castillo, Carlos and Gionis, Aristides}, biburl = {https://www.bibsonomy.org/bibtex/2d0d0b1d7164a6bd2149fbcaeba8e099f/chato}, citeulike-article-id = {3111114}, interhash = {86717c041dde4c13146c2f5f7e656051}, intrahash = {d0d0b1d7164a6bd2149fbcaeba8e099f}, keywords = {graph, search, social}, month = {August}, posted-at = {2008-08-12 09:21:04}, priority = {0}, timestamp = {2009-08-06T15:16:44.000+0200}, title = {Fast shortest path distance estimation in large networks}, year = 2008 }