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
--
