tag:blogger.com,1999:blog-264226589944705290.post4848374183305677105..comments2023-11-05T03:45:25.001-08:00Comments on God Plays Dice: Computing distance in the Facebook graphMichael Lugohttp://www.blogger.com/profile/15671307315028242949noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-264226589944705290.post-4388655784977569982011-02-06T12:34:51.913-08:002011-02-06T12:34:51.913-08:00Thanks, Suresh! If I remember correctly I've h...Thanks, Suresh! If I remember correctly I've heard that a similar method is used in generating road directions. Here the landmarks are intersections of major roads, so it's usually semi-obvious what the closest landmark is.Michael Lugohttps://www.blogger.com/profile/01950197848369071260noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-39878508865442318032011-02-05T16:06:23.526-08:002011-02-05T16:06:23.526-08:00Actually a generalization of bidirectional search ...Actually a generalization of bidirectional search is quite common when dealing with large graphs. Fix a collection of "landmark" nodes, and determine for each node which its closest landmark is (by BFS say). Then compute the exact distance between pairs of landmarks (there are presumably only a few of them). To now compute the distance between two nodes takes three lookups: from each node to its closest landmark, and the landmark-landmark distance. <br /><br />this tends to work fairly well in practice, especially with graphs that contain many tree-like tendrils and a highly connected core.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.com