Bing Makes Driving Directions Twice As Fast

Chris Pendleton announced on the Bing Maps blog that they have pushed out a major update to their driving directions “routing engine.” The new routing engine is twice as fast as the old one and adds more features like adding up to 3 routes in one request.

Previously, Bing Maps used a routing algorithm named Dijkstra’s algorithm. They replaced it with a new one named “Customizable Route Planning” or “CRP” for short. The new Customizable Route Planning algorithm is “twice as fast” as the Dijkstra’s algorithm, according to Chris Pendleton.

Chris also posted an excerpt of how this new routing calculation algorithm works:

Basic Algorithm. Our metric-independent preprocessing stage partitions the graph into connected cells with at most U (an input parameter) vertices each, with as few boundary arcs (arcs with endpoints in di erent cells) as possible. The metric customization stage builds a graph H containing all boundary vertices (those with at least one neighbor in another cell) and boundary arcs of G. It also contains a clique for each cell C: for every pair (v;w) of boundary vertices in C, we create an arc (v;w) whose cost is the same as the shortest path (restricted to C) between v and w (or in nite if w is not reachable from v). We do so by running Dijkstra from each boundary vertex. Note that H is an overlay [24]: the distance between any two vertices in H is the same as in G. Finally, to perform a query between s and t, we run a bidirectional version of Dijkstra’s algorithm on the graph consisting of the union of H, Cs, and Ct. (Here Cv denotes the subgraph of G induced by the vertices in the cell containing v.) As already mentioned, this is the basic strategy of separator-based methods. In particular, HiTi [19] uses edge-based separators and cliques to represent each cell. Unfortunately, HiTi has not been tested on large road networks; experiments were limited to small grids, and the original proof of concept does not appear to have been optimized using modern algorithm engineering techniques. Our rst improvement over HiTi and similar algorithms is to use PUNCH [5] to partition the graph. Recently developed to deal with road networks, it routinely nds solutions with half as many boundary edges (or fewer), compared to the general-purpose partitioners (such as METIS [20]) commonly used by previous algorithms. Better partitions reduce customization time and space, leading to faster queries. For our experiments, we used relatively long runs of PUNCH, taking about an hour. Our results would not change much if we used the basic version of PUNCH, which is only about 5% worse but runs in mere minutes. We use parallelism: queries run forward and reverse searches on two CPU cores, and customization uses all four (each cell is processed independently).

Related Stories:

Related Topics: Channel: Local | Microsoft: Bing Maps & Local

Sponsored


About The Author: is Search Engine Land's News Editor and owns RustyBrick, a NY based web consulting firm. He also runs Search Engine Roundtable, a popular search blog on very advanced SEM topics. Barry's personal blog is named Cartoon Barry and he can be followed on Twitter here. For more background information on Barry, see his full bio over here.

Connect with the author via: Email | Twitter | Google+ | LinkedIn



SearchCap:

Get all the top search stories emailed daily!  

Share

Other ways to share:
 

Read before commenting! We welcome constructive comments and allow any that meet our common sense criteria. This means being respectful and polite to others. It means providing helpful information that contributes to a story or discussion. It means leaving links only that substantially add further to a discussion. Comments using foul language, being disrespectful to others or otherwise violating what we believe are common sense standards of discussion will be deleted. Comments may also be removed if they are posted from anonymous accounts. You can read more about our comments policy here.
  • Winooski

    Tell the truth: You guys just thought it would be cool to have a page on SEL start ranking for [boundary vertices] and [Dijkstra’s algorithm], didn’t you? [;-)]

Get Our News, Everywhere!

Daily Email:

Follow Search Engine Land on Twitter @sengineland Like Search Engine Land on Facebook Follow Search Engine Land on Google+ Get the Search Engine Land Feed Connect with Search Engine Land on LinkedIn Check out our Tumblr! See us on Pinterest

 
 

Click to watch SMX conference video

Join us at one of our SMX or MarTech events:

United States

Europe

Australia & China

Learn more about: SMX | MarTech


Free Daily Search News Recap!

SearchCap is a once-per-day newsletter update - sign up below and get the news delivered to you!

 


 

Search Engine Land Periodic Table of SEO Success Factors

Get Your Copy
Read The Full SEO Guide