Google Maps is arguably one of the most famous Geospatial applications ever. Over the years, Google Maps transformed the way we navigate and made it mainstream to use a digital map to get from point A to point B.
It became much easier now visiting places you never been to before. All I have to do is to pull out Google Maps and find my direction.
Note that almost all of the algorithms involved in the operation of finding a route to get from point A to point B are Graph-based algorithms. So it’s worth learning about the basics of graph data structure and implementation.
How it works
Google Maps relies on a technology that we can generically describe it as a map server. The map server generates a map for the requested location from a large set of pre-generated map tile images covering the entire planet.
The map server may overlay data from other databases on top of this. The combination of a map viewer client and geographical database is traditionally called a Geographical Information System (GIS).
Google Maps couldn’t gather information on all the areas on the planet so they developed a Base Map Partner Program that allows organizations that have authoritative vector data that would improve google maps or google earth to provide it so it can be used.
Besides the Base Map Program Google makes use of round-the-clock, as they name it, vehicles to patrol each and every street, neighborhood and residential complex, providing minutely detailed digital images.
Algorithms used in Google Maps
It took a long time from the Google Maps team to arrive at today’s result from high performance to accuracy in results that we see in Google Maps.
The main mapping algorithm used is Graph Algorithm. But with any algorithm used the problem would still be finding the weights of the routes to take.
The problem of finding the best route raised some questions such as:
- What is the weight of a particular route?
- How to measure this weight if it’s my first time to try it?
- How to assign weights?
- Do we have to give priority to kinds of streets?
Fast Route Planning Algorithms
The above questions led to a customized set of algorithms that are much like Dijkstra’s Algorithm but with some modifications and helper operations before running the algorithm.
The main idea is to do a preprocessing on the graph once, to speed up the following queries so it can be computed very fast in the future.
To learn more details about those sets of algorithms I highly recommend reading the research paper Engineering Fast Route Planning Algorithms*.
Other Algorithms used in Google Maps and Other Map servers
1- Dijkstra’s Algorithm
This is a classical algorithm for route planning, It maintains an array of possible distances for each node.
The algorithm visits the nodes of the road network in the order of their distance to the source node and maintains the invariant that a particular node is visited.
Learn more here.
2- Priority Queues
Dijkstra’s Algorithm can be implemented using O(n) priority queue operations (If you’re not familiar with space-time complexity and big O analysis check out here).
Priority Queue is basically a queue with priority to each of its elements.
However, in practice, the impact of priority queues on the performance of large road networks is rather limited.
3- Bidirectional Search
Executes Dijkstra’s algorithm simultaneously forward from the source and backward from the target.
Once some node has been visited from both directions, the shortest path can be derived from the information already gathered.
4- Geometric Goal-Directed Search (A*)
Consider a square grid having many obstacles and we are given a starting cell and a target cell.
We want to reach the target cell (if possible) from the starting cell as quickly as possible. Here A* search algorithm found its use in Google Maps.
Final Thoughts
Maps and it’s algorithms are one of the most complex pieces of technology because it involves very hard NP-hard Computer Science problems.
Problems that cannot be normally solved by more computing power, it can only be solved by mixing techniques that involves preprocessing.
There is a very good Youtube video about P vs NP to understand one of the biggest unsolved problems of computer science.
References
