INTRODUCTION
Google Maps is a web mapping product developed at Google by Lars Rasmussen and Jens Rasmussen. It offers satellite imagery, aerial photography, street maps, 360° interactive panoramic views of streets, real-time traffic conditions, and route planning for traveling by foot, car, air, and public transportation.
ALGORITHMS
It took a long time for 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.
1. Dijkstra’s Algorithm
Google Map is based on this algorithm, Dijkstra’s Algorithm which was invented by Edsger W. Dijkstra, he was a Dutch systems scientist, programmer, software engineer, science essayist, and pioneer in computing science.
The algorithm finds the “minimum path” that connects the two points, that is the sequence of arcs that minimizes the sum of the weights and therefore, in the case of Maps, minimizes the estimated travel time.
Google Maps does this for us now and we don’t even really think about what a complex task it could be. Shortest path problems, a key feature of graph theory with a whole lot of pretty obvious real-world applications, get insanely deep very fast. The result is known (informally) as a combinatorial explosion, which is where the number of different combinations that must be explored in a given problem grows exponentially.
The result of such an explosion is that problems, like shortest path problems, grow so quickly as to become practically incomputable, taking a practically infinite amount of time to solve. It only takes a handful of nodes in a given map or graph for the number of possible combinations to push into the billions, requiring vast and unreasonable amounts of time.
The easiest way to explain Dijkstra’s algorithm is probably with an example. Take the graph below, where the numbers are given are the weights of each connection. (A weight could be a simple distance or really any relative cost associated with traversing a particular connection that we’re seeking to minimize.) To start, we assign s, our starting position, the value 0. It takes 0 miles (or whatever) to get here because it’s the beginning position. Next, we look at the neighboring nodes of s, which we can imagine as a sort of frontier to be explored.
Dijkstra is a greedy algorithm. What is a greedy algorithm?
Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to the global solutions are best fit for Greedy. A greedy algorithm is a simple, intuitive algorithm that is used in optimization problems. The algorithm makes the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem. Greedy algorithms are quite successful in some problems, such as Huffman encoding which is used to compress data, or Dijkstra’s algorithm, which is used to find the shortest path through a graph.
However, in many problems, a greedy strategy does not produce an optimal solution. For example, in the animation above, the greedy algorithm seeks to find the path with the largest sum. It does this by selecting the largest available number at each step. The greedy algorithm fails to find the largest sum, however, because it makes decisions based only on the information it has at any one step, without regard to the overall problem.
With a goal of reaching the largest sum, at each step, the greedy algorithm will choose what appears to be the optimal immediate choice, so it will choose 12 instead of 3 at the second step and will not reach the best solution, which contains 99.
How it works
Google Maps relies on a technology that we can generically describe 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.
- Pseudo Code
- Algorithm:
Steps:
- Choose an initial node in the weighted graph which serves as a source node.
- The distance of the other nodes is initialized as infinity concerning the source node.
- An empty set N contains the nodes to which the shortest path has been found.
- The distance of the source node concerning itself is zero. It is added to N and thus termed as ‘active node’.
- Consider the neighboring nodes of the active node which are connected to it by a weighted edge. Sum up the distance with the weight of the edge.
- If the neighboring nodes already have some distance assigned, then update the distance if the newly obtained distance in step 5 is less than the current value.
- Now, choose the node which has the minimum distance assigned to it and insert it into N. The newly inserted node is now the ’active node’.
- Repeat steps 5 to 7 until the destination node is included in the set N or if there are no more labeled nodes in N.
2. A* Algorithm
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.
A* (A-star) Algorithm A* algorithm is a flexible, more efficient, and cutting-edge algorithm that Google Maps currently utilized to find the shortest path between a given source and destination. It has a wider range of contexts hence, it can deal with larger graphs which is preferable to Dijkstra’s algorithm. A* is like Greedy Best-First-Search. A* algorithm is widely used since its mechanism involves combining the pieces of information that Dijkstra algorithm uses (It favors the vertices close to the source) and information that Greedy Best-First-Search uses (choosing nodes close to the goal).
One of the differences between A* and Dijkstra’s algorithm is that the A* algorithm, being a heuristic algorithm, has two cost functions :
g(x) :- The actual cost to reach a vertex (same applies to Dijkstra) h(x) :- Approximate cost to reach goal node from node n. ( This is the heuristic part of the cost function) f(x) :- Total estimated cost of each node
The cost calculated by the A* algorithm shouldn’t be overestimated, since it is a heuristic algorithm. Hence, the actual cost to reach the destination node, from any given node n should be either greater than or equal to h(x). This is called the Admissible Heuristic. Hence, one can represent the estimated total cost of each node by :
f (x) = g (x) + h (x).
A node is expanded by A* search, only if it is considered to be promising. This algorithm focuses solely on reaching the goal node from the node which is currently under consideration. It does not try to reach other nodes.
Thus, if the heuristic function taken into consideration approximates the future cost accurately, then one needs to explore considerably fewer nodes as compared to Dijkstra’s algorithm.
A* algorithm terminates when the destination node has been reached ensuring that the total cost of reaching the destination node is the minimum compared to all the other paths. It can also terminate if the destination node has not been reached despite all the nodes being explored. Unlike, Dijkstra’s algorithm, it does not explore all nodes possible, thus A* proves to be more proficient.
Owing to the high accuracy, flexibility, ability to deal with mammoth graphs, and its stark advantages over Dijkstra’s algorithm, Google Maps has shifted to deploying A* algorithm for obtaining the shortest path between the source and destination.
* Pseudo-code
- Algorithm:
1) Initialise two lists -
a) Open_list
b)Closed_list
2) Insert the source node into the open_list
3) Keep the total cost of the source node as zero
4) While open_list is not NULL:
a) Check the node with minimum total cost (least f(x)) present in the open_list
b) Rename the above node as X
c) Pop X out of the open_list
d) Generate the successors to X
e) Set X as the parent node of all these successors
5) for each successor:
a) if successor is same as the destination:stop
b) else:
successor.g(x) = X.g(x) + distance between successor and X
successor.h(x) = distance from destination [goal] to successor (using heuristics)
successor.f(X) = successor.g(x) + suucessor.h(x)
c) if a node with same position as successor is present in open_list, but having a lower cost [f(x)] than successor, then skip the successor
d) if a node with the same position as the successor is present in the closed_list , but having a lower cost [f(x)], then skip this successor, else insert the node into the open_list
end for loop
6) Add X into the closed list
7) End the while loop
8) The route is obtained by the closed_list
9) Stop.
DATA STRUCTURES
1. 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.
Priority Queue is similar to a queue where we insert an element from the back and remove an element from the front, but with a difference that the logical order of elements in the priority queue depends on the priority of the elements. The element with the highest priority will be moved to the front of the queue and the one with the lowest priority will move to the back of the queue. Thus it is possible that when you en queues an element at the back in the queue, it can move to the front because of its highest priority.
Priority Queues have a priority value and data, for every entry.
Thus, when adding a new element to the queue, it bubbles up to the surface if it has a higher priority value than elements already in the collection.
When one calls pop, we get the data for the element with the highest priority.
Forwarding a flow in a network includes receiving the flow at a switch, determining an optimized priority queue level of the flow at the switch, and forwarding the flow via the switch using an optimized priority queue level of the flow at the switch. The flow passes through a plurality of switches, including the switch, in the network, and the optimized priority queue level of the flow at the switch is different from a priority queue level of the flow at a second switch of the plurality of switches. The second switch routes the flow at the second switch using the different priority queue levels for the flow.
Many applications require that we process items having keys in order, but not necessarily in full sorted order and not necessarily all at once. Often, we collect a set of items, then process the one with the largest key, then perhaps collect more items, then process the one with the current largest key, and so forth. An appropriate data type in such an environment supports two operations: remove the maximum and insert. Such a data type is called a priority queue.
API. Priority queues are characterized by the remove the maximum and insert operations. By convention, we will compare keys only with a less() method, as we have been doing for sorting. Thus, if records can have duplicate keys, maximum means any record with the largest key value. To complete the API, we also need to add constructors and a test if empty operation. For flexibility, we use a generic implementation with a generic type Key that implements Comparable.
2. Bidirectional Search Trees:
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.
The query module combines the forward search spaces and the backward search space To determine the shortest paths from each point at which the initial graph search stopped to the destination node. Combining forward and reverse search spaces to determine optimal routes is a well-known aspect of bidirectional graph searches (e.g.: bidirectional Dijkstra), and will not be described in detail here. In some embodiment, the query module may combine the forward search spaces to form a combined forward search space, and then determine meeting spots between the combined forward search space and the backward search space, thereby determine the shortest paths.
The module takes into account forward search spaces from each node at which the initial graph search stopped, and also the backward search space from the destination node. Thus, the search carried out by the query module is a many-to-one search. It will be appreciated that it is not necessary to finish the initial graph search before starting the many-to-one search since the latter can be started from a node once the initial search has stopped at that node.
CONCLUSION :
Therefore, the algorithms, techniques, procedures, and technology used by Google Maps to render accurate and real-time information and data on their app, is understood. Obsolete algorithms like Dijkstra’s algorithm may not work since the time complexity would increase drastically and hence a more efficient, accurate, and faster algorithm like A* has helped replace it. Features like street view need a splendid level of image processing, editing, and stitching. Mathematical concepts like Trilateration, Triangulation, and Geocoding are required to locate any position with the help of imaginary geographical coordinates. Aerial imagery also helps design the front end of the app.
The pictures captured by aerial imagery are processed and thereafter used to give the map layout which is seen when one opens the application.
Thus, Google Maps constantly keeps updating the old features and introduces new ones for the benefit and convenience of its users. Hence, Google Maps is one of the most helpful and reliable applications.
