Design techniques based on classical algorithms have often proved useful. They are especially useful for recent innovations on large-scale problems like travel itineraries and routing challenges. For instance, Dijkstra’s algorithm is used to find the shortest path between nodes in a graph, such as road networks. However, the process of partitioning a road network can speed up algorithms by shrinking the part of the graph that is searched during computation.
Recently, Ali Kemal Sinop — Senior Research Scientist at Google Research, and Mahmuda Ahmed — Senior Software Engineer at Google Maps, revealed on Google AI blog the engineering behind its graph partitioning algorithm for road networks, using ideas from classic algorithms, using random walks.
Sign up for your weekly dose of what's up in emerging technology.
Modeling Road Networks using Graphs
There is a useful relation between road networks and graphs where the interactions become nodes and roads become the edges.
To explain how routing might benefit from partitioning, the authors use the example of the Dijkstra algorithm. The Dijkstra algorithm works in a breadth-first search manner. Dijkstra performs an exhaustive search which begins with the source until it reaches the destination. As the distance between the starting point and destination increases, the computation can become slower. For routes with intra-metros, the exhaustive volume of space explored by the Dijkstra algorithm results in an impractical latency during computation on the order of seconds. Having said that, identifying regions that have more connections inside themselves but lesser connections to the outside makes it possible to split the computation into smaller chunks.
To validate, the researchers showcase the following example:
Source: Google AI
Suppose, in order to drive from point one to point B, when one finalises where to enter from (say, Outerbridge or Goethals) and where to exit from (Verrazzano), the challenge can be broken down into three smaller chunks — first to the entrance, then to the exit, and then to the destination using the best possible route. Meaning, a routing algorithm needs to consider three points or beacons to navigate between points A and B to find the most accurate path.
However, beacons are useful only as long as there aren’t too many of them. This is because, with fewer beacons, fewer shortcuts need to be added, the smaller the search space and, thus, the faster the computation. Therefore, efficient partitioning should have fewer beacons for the road network.
Google ensures that there aren’t too many beacons by dividing the road network to minimise the number of connections between components. To do this, it divides the network into two balanced components while minimising the number of roads that connect these two components, resulting in a small ratio of beacons to roads in each component. The algorithm then keeps dividing the network into two components at a time until the desired size of the components is reached (in terms of the number of roads inside), yielding a multi-component partition.
There is a trick here — if the number of beacons is high, then there would be too many beacons. However, if the size is too large, then it would only be useful for longer routes. The size is thus left as an input parameter and can be entered through experimentation when the algorithm is being finalised.
Partitioning for Road Networks
In order to divide a road network represented in a graph into two balanced components, one has to make the graph smaller by grouping the closely connected nodes together, allowing speeding up the following two-way partitioning phase.
This is where a stochastic or random walk comes into play. Random walks come with theoretical properties that tend to get trapped in regions that are well-connected on the inside but poorly connected on the outside.
Post finding the small components (connected nodes grouped together), the algorithm contracts each group into a new single node.
The size of the original graph (on the left) is reduced by finding groups of nodes (middle) and coalescing each of the groups into one super node (on the right) | Source: Google AI
Finally, the algorithm is partitioned into two smaller graphs and then refined the partitioning on the small graph to one on the original graph of the road network. Google researchers then use the inertial flow algorithm to find the cut on the smaller graph that minimises the ratio of the beacons to nodes.
Source: Google AI
Once the cut on the small graph is found, the algorithm then performs a refinement step to project the cut back to the original graph of the road network.
Source: Google AI
Classical algorithms offer useful tools for solving problems at a large scale. Additionally, graph partitioning can be used to break down a large scale graph problem into smaller subproblems to be solved independently. This can be particularly relevant in Google maps, where the partitioning algorithm efficiently computes routes.