Daniel Delling
RESEARCHER
.
Microsoft Research Silicon Valley
1065 La Avenida
Mountain View CA 94043
tel: +1 (650) 693-1918
mail: daniel.delling [at] microsoft [dot] com
I joined Microsoft Research in September 2009. My main research interests include location services, graph algorithms and algorithm engineering.
News
- Our work on exact graph bisection allows us to solve surprisingly big instances to optimality. See our paper for further details.
- We have developed a prototype of location-based service which runs completely in SQL. Besides computing optimal routes in road networks, it allows queries like "find the closest restaurant", "give me the best post office on the way home", or "find a gas station that is ahead of me". See our Technical Report for further details.
- We have developed a new journey planning engine for public transit networks, called RAPTOR. See our paper for further details.
- Bing Maps is now using the Customizable Route Planning technology. See our paper for further details.
- Our work on a new parallel single-source shortest path algorithm (PHAST) won the Best Paper Award (Algorithms Track) at IPDPS 2011.
Activities
- PC co-chair of ATMOS 2012
- PC member of ATMOS 2013, SoCS 2013, SEA 2013, ALENEX 2013, CATS 2013, SOFSEM 2013, ESA 2011, ALENEX 2010
Selected Publications
2012
- Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck, PHAST: Hardware-accelerated shortest path trees, in Journal of Parallel and Distributed Computing, Elsevier, 2012
- Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck, HLDB: Location-Based Services in Databases, in SIGSPATIAL GIS, ACM, November 2012
- Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Hierarchical Hub Labelings for Shortest Paths, in Proceedings of the 20th Annual European Symposium on Algorithms (ESA'12), Springer, 2012
- Daniel Delling and Renato F. Werneck, Better Bounds for Graph Bisection, in Proceedings of the 20th Annual European Symposium on Algorithms (ESA'12), Springer, 2012
- Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck, Exact Combinatorial Branch-and-Bound for Graph Bisection, in Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12), Society for Industrial and Applied Mathematics, 2012
- Daniel Delling, Thomas Pajor, and Renato F. Werneck, Round-Based Public Transit Routing, in Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12), Society for Industrial and Applied Mathematics, 2012
- Daniel Delling, Moritz Kobitzsch, Dennis Luxen, and Renato F. Werneck, Robust Mobile Route Planning with Limited Connectivity, in Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12), Society for Industrial and Applied Mathematics, 2012
2011
- Daniel Delling, Time-Dependent SHARC-Routing, in Algorithmica, vol. 60, no. 1, pp. 60-94, Springer, May 2011
- Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck, Customizable Route Planning, in Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), Springer Verlag, May 2011
- Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks, in Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), Springer Verlag, May 2011
- Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck, Graph Partitioning with Natural Cuts, in 25th International Parallel and Distributed Processing Symposium (IPDPS'11), IEEE, 2011
- Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Faster Batched Shortest Paths in Road Networks, in Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'11), OpenAccess Series in Informatics, 2011
- Mihai Budiu, Daniel Delling, and Renato F. Werneck, DryadOpt: Branch-and-Bound on Distributed Data-Parallel Execution Engines, in 25th International Parallel and Distributed Processing Symposium (IPDPS'11), IEEE, 2011
- Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck, PHAST: Hardware-Accelerated Shortest Path Trees, in 25th International Parallel and Distributed Processing Symposium (IPDPS'11), IEEE, 2011
- Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck, VC-Dimension and Shortest Path Algorithms, in Proc. ICALP 2011, Springer Verlag, 2011
2010
- Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner, Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra's Algorithm, in ACM Journal of Experimental Algorithmics, vol. 15, pp. 2.3, February 2010
- Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Alternative Routes in Road Networks, in Proc. 9th International Symposium on Experimental Algorithms (SEA), Springer Verlag, 2010
- Daniel Delling, Bastian Katz, and Thomas Pajor, Parallel Computation of Best Connections in Public Transportation Networks, in Proceedings of the 24th International Parallel and Distributed Processing Symposium (IPDPS'10), IEEE Computer Society, 2010
2009
- Reinhard Bauer and Daniel Delling, SHARC: Fast and Robust Unidirectional Routing, in ACM Journal of Experimental Algorithmics, vol. 14, pp. 2.4–2.29, Society for Industrial and Applied Mathematics, May 2009
- Daniel Delling, Peter Sanders, Dominik Schultes, and Dorothea Wagner, Engineering Route Planning Algorithms, in Algorithmics of Large and Complex Networks, vol. 5515, pp. 117–139, Springer, 2009
2008
- Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Görke, Martin Höfer, Zoran Nikoloski, and Dorothea Wagner, On Modularity Clustering, in IEEE Transactions on Knowledge and Data Engineering, vol. 20, no. 2, pp. 172–188, IEEE, February 2008
For a complete list of my publications, please browse to my old site.
