speedy Google Maps driving directions like implementation

[Lukáš Vlček <lu...@gmail.com>]

Hi,
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 but I don't think it is really
close to the truth. How it is possible to implement such real-time function
in plain MapReduce fashion (from the Hadoop point of view)? The only
possibility I can think of right now it that they either execute the
MapReduce computation only in the memory (intermediate results as well as
Reduce to next Map results are kept only in some-kind of distributed memory)
or they use other architecture for this.

In simple words I know there are some tutorials about how to nail down SSSP
problem with MapReduce but I can not believe it can produce results in such
a quick response I can experience with Google Maps.

Any comments, ideas?

Thanks,
Lukas

Re: speedy Google Maps driving directions like implementation

[Owen O'Malley <om...@apache.org>]

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

Re: speedy Google Maps driving directions like implementation

[Joerg Rieger <jo...@mni.fh-giessen.de>]

Hello,

On 10.06.2009, at 11:43, Lukáš Vlček wrote:

> Hi,
> 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 but I don't think it is  
> really
> close to the truth. How it is possible to implement such real-time  
> function
> in plain MapReduce fashion (from the Hadoop point of view)? The only
> possibility I can think of right now it that they either execute the
> MapReduce computation only in the memory (intermediate results as  
> well as
> Reduce to next Map results are kept only in some-kind of distributed  
> memory)
> or they use other architecture for this.
>
> In simple words I know there are some tutorials about how to nail  
> down SSSP
> problem with MapReduce but I can not believe it can produce results  
> in such
> a quick response I can experience with Google Maps.
>
> Any comments, ideas?


I don't think they use MapReduce for the user-facing part of Google  
Maps.

If I had to implement something similar, I would use MapReduce jobs to
preform as much as "offline"-processing as possible.

Therefore my guess is, that MapReduce-Jobs are used to create the  
static map
tiles from the huge satellite imagery.

I also think that MapReduce jobs create an index or a graph  
representation of
roads and their intersections with other roads, including  
intersections with
towns and other points of interest.

The resulting graph is probably stored in a Memcache type memory  
system for
very fast retrieval.

But then again, I'm not a GIS expert (not even close). ;-)


J

--