Hey—we've moved. Visit
The Keyword
for all the latest news and stories from Google
Official Blog
Insights from Googlers into our products, technology, and the Google culture
The road to better path-finding
November 6, 2007
Posted by Barry Brumitt, Software Engineer
Way back at the end of 2005, Google Maps' driving directions were on par with other sites, providing basic driving directions in a few seconds. But the nature of the existing system made it nigh impossible to make it faster, add new features, or improve the quality of the routes. And better directions can yield tangible real-world benefits by saving people time and fuel, alleviating frustration, and making travel more pleasant. For all these reasons, it made sense to take a fresh look at the problem and to try to reinvent things such that we could provide a service markedly superior to the status quo.
It's important to us to solve big problems.
Automatically finding routes
quickly is a hard problem -- especially at a global scale (there are
several hundred million
road segments worldwide). Even if a routing program is needed to only look at 10% of the map and only examine each segment for a microsecond, it would take tens of seconds to compute a path. Route-finding has to be done automatically because it would be impossibly time-consuming to compute the best routes between all pairs of locations by hand.
Fortunately, we have the tools, technologies, and expertise that make it easier to tackle such hard problems and to build systems for searching large data sets quickly. A small group of engineers (of which I was a part) created the Google Maps route-finding project in
Kirkland, WA
with the hope of building a world-class system for route-finding. This is the first project I've worked on at Google, and it has given me the opportunity to learn all about the infrastructure we have to build and launch products and features.
We started with the geographic data sets already in use by other groups at Google. Then we designed, built, tested, and deployed a complete route-finding solution in under 12 months. Commutes across the
520 Bridge from Seattle
became a favorite test query. As someone with a background in path planning and robotics, it's been great to work on a problem with such substantial theoretical and practical aspects. It took 10 months of hard work, thousands of
MapReduce
passes, and an uncountable number of lattes to complete.
And 'complete' doesn't really capture it. Our new route-finding system is hundreds of times faster: it can find and describe a
cross-continental shortest path
in well under a second. Shorter paths can be found proportionately faster.
As evidenced by our '
draggable directions
' launch earlier this year, this kind of performance fundamentally changes your Maps experience. It's now possible for you to change your route by simply dragging it or its endpoints. (
Here's an example
of the above route adjusted to use I-90 instead of WA-520.) No other planning service provides this feature, and it would have been impossible to ship without the massive speedup provided by the system we created.
In the last few months, we've also added other features, like '
avoid highways
' and '
estimated time-in-traffic
.' Plus, we now cover about 50 countries worldwide. We've raised the bar for what a route-finding system can and should provide. We're pleased with what we've built, and you can expect further improvements in the coming months.
Just recently, the Google Maps route-finding team moved to our new
Fremont
Engineering office. I'm happy to report we don't have to
commute
across Lake Washington at all anymore. In fact, nearly half the team cycles in every day! And
we're always looking
for great people, so if any of this sounds like the kind of challenge you'd be up for, we'd love to hear from you.
Labels
accessibility
41
acquisition
26
ads
131
Africa
19
Android
58
apps
419
April 1
4
Asia
39
books + book search
48
commerce
12
computing history
7
crisis response
33
culture
12
developers
120
diversity
35
doodles
68
education and research
144
entrepreneurs at Google
14
Europe
46
faster web
16
free expression
61
google.org
73
googleplus
50
googlers and culture
202
green
102
Latin America
18
maps and earth
194
mobile
124
online safety
19
open source
19
photos
39
policy and issues
139
politics
71
privacy
66
recruiting and hiring
32
scholarships
31
search
505
search quality
24
search trends
118
security
36
small business
31
user experience and usability
41
youtube and video
140
Archive
2016
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2015
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2014
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2013
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2012
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2011
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2010
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2009
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2008
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2007
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2006
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2005
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2004
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Feed
Google
on
Follow @google
Follow
Give us feedback in our
Product Forums
.
Follow
