bq. Find the shortest path between two nodes nodes in a large graph which you can’t keep in memory, for example the Facebook friendship graph.

!<blog/meet-in-the-middle?12fig26.gif 60%! The usual approach is to use a bread first search algorithm. If the distance between two nodes is $k$ and the average degree in the network is $p$ then we explore $O(p^k^)$ nodes.

!<blog/meet-in-the-middle?12fig26.gif 70%! The usual approach is to use a bread first search algorithm. If the distance between two nodes is $k$ and the average degree in the network is $p$ then we explore $O(p^k^)$ nodes.

A better solution starts from both nodes and sees when the two search spaces meet.  The improvement is that you only explore $O(p^k/2^)$ nodes.