Quickly Find Businesses Along a Route

About a year ago Bing introduced the all-new Bing Maps and launched new features. One of those features is the ability to search for businesses along a driving route. What Bing didn't highlight was the technology used to actually make it work.
 
Here's an example of planning a drive from work in Bellevue, WA to a favorite restaurant in Marblemount, WA. Bing Maps gives directions, and provides the ability to search for interesting things along the route:




 
Another planning scenario is when the gas tank gets to half full. It's easy to find a gas stations along a trip with minimal deviation from the route and low price options. Tap the gas stations icon and, thanks to Bing's real-time gas prices, there are several options:
 

 
The job of minimizing deviation has already been done – see all gas stations in order of their appearance on the route. The difference in trip time is shown right next to the gas price. Hover over each gas station in the panel and it is highlighted on the map.

It's also easy to choose the gas station that looks best, click the “Directions” dropdown, and add it to the planned route.


 
Once tapping “Add to route…”, the gas station is automatically added in the right order place as a destination along the route and marked on the map. At this point, add some coffee stops, attractions, and more.
 
Problem Space
 
The most basic geospacial searches will take a starting point (like current location) and calculate the geometric distance from that point to several other points. In order to quickly understand the nearness of points, the data must be spatially indexed.
 
Once indexed, points can be found in multiple ways, like bounding box queries or point-radius queries. This will offer computationally fast results for points in the search area, using basic geometry.
 
Neither of these sorts of queries has any concept of roads or travel. In reality, when points are businesses and a passenger is in a car, the crow-flies distance doesn’t present the entire picture. The actual duration and distance to get from one search point to any destination point should be calculated using the road network.
 
Solution
 
Bing has a road network represented as a graph, and uses several graph optimizations and algorithms. To power the ability to search along the route, Bing utilize a hub-based algorithm developed by Microsoft Research.
As described in more detail in the paper, the basic approach is to find “hot” spots on the map – parts of the routing graph which tend to have many driving routes pass through them. In order to calculate these hubs, every possible direction permutation is calculated in Bing's automobile routing graph. If the entire road network in the US has 50 million vertices, the optimal driving distance in a 50M  x 50M matrix is calculated, and every one of those paths is stored (in the case with 50 million vertices, that’s 2.5 quadrillion paths).

Once all paths are assessed, they are analyzed and vertices common across multiple paths are counted. The vertices with the most paths passing through them become the hubs.
 

Traversing hubs away from Seattle
 
After the hub set is created, Bing walks the graph using only hubs, without passing through every individual vertex. In the case below, potential paths are explored (using only hubs) from the route to potential businesses along the path. This doesn't create the instructions for a drive, but it does give a good approximation of the travel deviation to get to a business.  


Traversing hubs away from one of the Bing offices in Bellevue, WA
 
When calculating to find the best business along a route, Bing Maps first locates the hubs that are along the route, then finds the hubs near businesses that may be nearby. After the nearest hubs are found, the driving time deviation is a simple lookup, since every hub-to-hub time has been pre-calculated. This way, thousands of businesses along a route is cycled through incredibly quickly.  
 
After this has all been done, various options for gas stations along the route are presented. At this point, thanks to a hub-based approach, BingMaps hasn't spent any processing time to get the precise route (and instructions) to leave the highway and get to a gas station. Once the ideal gas station is selected, it's inserted into the directions and instructions are re-computed.


 
While this all makes for a very performant way to find things along an existing path in the routing graph, it also eats up a huge amount of storage. There are tens of millions of vertices, which are stored alongside all of the hub data that is pre-computed. Luckily, Microsoft Research has already taken care of this problem. While we won’t dive into the details in this blog post, Microsoft Research has established a solution using sequential memory on the machine doing the calculation
 
-The Bing Team