On Jun 10, 2009, at 2:43 AM, Lukáš Vlček wrote:
I am wondering how Google implemented the driving directions
function in the
Maps. More specifically how did they do it that it is so fast. I
asked on
Google engineer about this and all he told me is just that there are
bunch
of MapReduce cycles involved in this process
Like search, the key is to use batch map/reduce jobs to generate the
indexes that are used to answer the query in real-time. The right
question is what kind of indexes can be used to answer the routing
question quickly. Generalizing back to a graph, you could use map/
reduce jobs to generate the all-pairs-shortest-distance matrix. Then
it is easy to use the matrix to solve arbitrary shortest path
problems in linear time.
-- Owen
