Abstract: Computing driving directions interactively on continental road networks requires preprocessing. This step can be costly, limiting our ability to incorporate new optimization functions, including traffic information or personal preferences. In this talk, I will show how the performance of the state-of-the-art customizable route planning (CRP) framework is boosted by GPUs, even though it has highly irregular structure.  Extensive experiments reveal that we can incorporate a new optimization function on a continental sized road network (with tens of millions of road segments) in about 60 milliseconds. This is an order of magnitude faster than a highly-optimized parallel CPU implementation, enabling interactive personalized driving directions on continental scale. The CRP framework is currently used by Bing Maps.

Joint work with Andrew Goldberg, Moritz Kobitzsch, Thomas Pajor, and Renato Werneck.

Bio: Daniel Delling is a researcher at Microsoft Research Silicon Valley since 2009.  Prior to that, he earned a PhD in Computer Science from the Karlsruhe Institute of Technology, Germany.  Daniel's research focus is the design of efficient algorithms exploiting modern hardware architecture.