Document Open Access Logo

Fast and Stable Repartitioning of Road Networks

Authors Valentin Buchhold, Daniel Delling, Dennis Schieferdecker, Michael Wegner

PDF
Thumbnail PDF

File

LIPIcs.SEA.2020.26.pdf
  • Filesize: 0.87 MB
  • 15 pages

Document Identifiers

Author Details

Valentin Buchhold
  • Karlsruhe Institute of Technology, Germany
Daniel Delling
  • Apple Inc, Cupertino, CA, USA
Dennis Schieferdecker
  • Apple Inc, Cupertino, CA, USA
Michael Wegner
  • Apple Inc, Cupertino, CA, USA

Funding

This work was done while the first author was interning at Apple Inc.

Cite AsGet BibTex

Valentin Buchhold, Daniel Delling, Dennis Schieferdecker, and Michael Wegner. Fast and Stable Repartitioning of Road Networks. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SEA.2020.26

Abstract

We study the problem of graph partitioning for evolving road networks. While the road network of the world is mostly stable, small updates happen on a relatively frequent basis, as can been observed with the OpenStreetMap project (http://www.openstreetmap.org). For various reasons, professional applications demand the graph partition to stay roughly the same over time, and that changes are limited to areas where graph updates occur. In this work, we define the problem, present algorithms to satisfy the stability needs, and evaluate our techniques on continental-sized road networks. Besides the stability gains, we show that, when the changes are low and local, running our novel techniques is an order of magnitude faster than running graph partitioning from scratch.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Graph repartitioning
  • stable partitions
  • road networks
  • algorithm engineering

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Alternative routes in road networks. ACM Journal of Experimental Algorithmics, 18(1):1.3:1-1.3:17, 2013. URL: https://doi.org/10.1145/2444016.2444019.
  2. Reinhard Bauer and Daniel Delling. SHARC: Fast and robust unidirectional routing. ACM Journal of Experimental Algorithmics, 14:2.4:1-2.4:29, 2009. URL: https://doi.org/10.1145/1498698.1537599.
  3. 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. ACM Journal of Experimental Algorithmics, 15:2.3:1-2.3:31, 2010. URL: https://doi.org/10.1145/1671970.1671976.
  4. Valentin Buchhold, Peter Sanders, and Dorothea Wagner. Real-time traffic assignment using engineered customizable contraction hierarchies. ACM Journal of Experimental Algorithmics, 24(2):2.4:1-2.4:28, 2019. URL: https://doi.org/10.1145/3362693.
  5. Aydin Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. Recent advances in graph partitioning. In Lasse Kliemann and Peter Sanders, editors, Algorithm Engineering: Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 117-158. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-49487-6_4.
  6. Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck. PHAST: Hardware-accelerated shortest path trees. Journal of Parallel and Distributed Computing, 73(7):940-952, 2013. URL: https://doi.org/10.1016/j.jpdc.2012.02.007.
  7. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Customizable route planning in road networks. Transportation Science, 51(2):566-591, 2017. URL: https://doi.org/10.1287/trsc.2014.0579.
  8. Daniel Delling, Andrew V. Goldberg, Ilya P. Razenshteyn, and Renato F. Werneck. Graph partitioning with natural cuts. In 25th IEEE International Symposium on Parallel and Distributed Processing (IPDPS'11), pages 1135-1146. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/IPDPS.2011.108.
  9. Daniel Delling, Dennis Schieferdecker, and Christian Sommer. Traffic-aware routing in road networks. In 34th IEEE International Conference on Data Engineering (ICDE'18), pages 1543-1548. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/ICDE.2018.00172.
  10. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Customizable contraction hierarchies. ACM Journal of Experimental Algorithmics, 21(1):1.5:1-1.5:49, 2016. URL: https://doi.org/10.1145/2886843.
  11. Lars Gottesbüren, Michael Hamann, Tim Niklas Uhl, and Dorothea Wagner. Faster and better nested dissection orders for customizable contraction hierarchies. Algorithms, 12(9):1-20, 2019. URL: https://doi.org/10.3390/a12090196.
  12. Michael Hamann and Ben Strasser. Graph bisection with pareto optimization. ACM Journal of Experimental Algorithmics, 23(1):1.2:1-1.2:34, 2018. URL: https://doi.org/10.1145/3173045.
  13. Bruce Hendrickson, Robert W. Leland, and Rafael Van Driessche. Enhancing data locality by using terminal propagation. In Proceedings of the 29th Annual Hawaii International Conference on System Sciences (HICSS'96), pages 565-574. IEEE Computer Society, 1996. URL: https://doi.org/10.1109/HICSS.1996.495507.
  14. Moritz Hilger, Ekkehard Köhler, Rolf H. Möhring, and Heiko Schilling. Fast point-to-point shortest path computations with arc-flags. In Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson, editors, The Shortest Path Problem: Ninth DIMACS Implementation Challenge, volume 74 of DIMACS Book, pages 41-72. American Mathematical Society, 2009. Google Scholar
  15. Martin Holzer, Frank Schulz, and Dorothea Wagner. Engineering multilevel overlay graphs for shortest-path queries. ACM Journal of Experimental Algorithmics, 13:2.5:1-2.5:26, 2008. URL: https://doi.org/10.1145/1412228.1412239.
  16. George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20(1):359-392, 1998. URL: https://doi.org/10.1137/S1064827595287997.
  17. Ulrich Lauther. An experimental evaluation of point-to-point shortest path calculation on road networks with precalculated edge-flags. In Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson, editors, The Shortest Path Problem: Ninth DIMACS Implementation Challenge, volume 74 of DIMACS Book, pages 19-39. American Mathematical Society, 2009. Google Scholar
  18. Burkhard Monien and Stefan Schamberger. Graph partitioning with the party library: Helpful-sets in practice. In Proceedings of the 16th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD'04), pages 198-205. IEEE Computer Society, 2004. URL: https://doi.org/10.1109/SBAC-PAD.2004.18.
  19. Leonid Oliker and Rupak Biswas. PLUM: Parallel load balancing for adaptive unstructured meshes. Journal of Parallel and Distributed Computing, 52(2):150-177, 1998. URL: https://doi.org/10.1006/jpdc.1998.1469.
  20. François Pellegrini and Jean Roman. Scotch: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs. In Heather M. Liddell, Adrian Colbrook, Louis O. Hertzberger, and Peter M. A. Sloot, editors, Proceedings of the 4th International Conference and Exhibition on High-Performance Computing and Networking (HPCN'96), volume 1067 of Lecture Notes in Computer Science, pages 493-498. Springer, 1996. URL: https://doi.org/10.1007/3-540-61142-8_588.
  21. Eddy Pramono, Horst D. Simon, and Andrew Sohn. Dynamic load balancing for finite element calculations on parallel computers. In David H. Bailey, Petter E. Bjørstad, John R. Gilbert, Michael Mascagni, Robert S. Schreiber, Horst D. Simon, Virginia Torczon, and Layne T. Watson, editors, Proceedings of the 7th SIAM Conference on Parallel Processing for Scientific Computing, pages 599-604. SIAM, 1995. Google Scholar
  22. Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76(3), 2007. URL: https://doi.org/10.1103/PhysRevE.76.036106.
  23. Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, and Roman Dementiev. Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-25209-0.
  24. Peter Sanders and Christian Schulz. Distributed evolutionary graph partitioning. In David A. Bader and Petra Mutzel, editors, Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12), pages 16-29. SIAM, 2012. URL: https://doi.org/10.1137/1.9781611972924.2.
  25. Peter Sanders and Christian Schulz. Think locally, act globally: Highly balanced graph partitioning. In Vincenzo Bonifaci, Camil Demetrescu, and Alberto Marchetti-Spaccamela, editors, Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science, pages 164-175. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-38527-8_16.
  26. Aaron Schild and Christian Sommer. On balanced separators in road networks. In Evripidis Bampis, editor, Proceedings of the 14th International Symposium on Experimental Algorithms (SEA'15), volume 9125 of Lecture Notes in Computer Science, pages 286-297. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-20086-6_22.
  27. Kirk Schloegel, George Karypis, and Vipin Kumar. Multilevel diffusion schemes for repartitioning of adaptive meshes. Journal of Parallel and Distributed Computing, 47(2):109-124, 1997. URL: https://doi.org/10.1006/jpdc.1997.1410.
  28. Kirk Schloegel, George Karypis, and Vipin Kumar. A unified algorithm for load-balancing adaptive scientific simulations. In Louis H. Turcotte, editor, Proceedings of the 13th ACM/IEEE Supercomputing Conference (SC'00), pages 1-11. IEEE Computer Society, 2000. URL: https://doi.org/10.1109/SC.2000.10035.
  29. Kirk Schloegel, George Karypis, and Vipin Kumar. Wavefront diffusion and LMSR: Algorithms for dynamic repartitioning of adaptive meshes. IEEE Transactions on Parallel and Distributed Systems, 12(5):451-466, 2001. URL: https://doi.org/10.1109/71.926167.
  30. Frank Schulz, Dorothea Wagner, and Karsten Weihe. Dijkstra’s algorithm on-line: An empirical case study from public railroad transport. ACM Journal of Experimental Algorithmics, 5:1-23, 2000. URL: https://doi.org/10.1145/351827.384254.
  31. Frank Schulz, Dorothea Wagner, and Christos D. Zaroliagis. Using multi-level graphs for timetable information in railway systems. In David M. Mount and Clifford Stein, editors, Proceedings of the 4th Workshop on Algorithm Engineering and Experiments (ALENEX'02), volume 2409 of Lecture Notes in Computer Science, pages 43-59. Springer, 2002. URL: https://doi.org/10.1007/3-540-45643-0_4.
  32. Andrew Sohn and Horst D. Simon. JOVE: A dynamic load balancing framework for adaptive computations on an SP-2 distributed-memory multiprocessor. Technical Report 94-60, New Jersey Institute of Technology, Department of Computer and Information Science, 1994. Google Scholar
  33. Chris Walshaw. Variable partition inertia: Graph repartitioning and load balancing for adaptive meshes. In Manish Parashar and Xiaolin Li, editors, Advanced Computational Infrastructures for Parallel and Distributed Adaptive Applications, pages 357-380. John Wiley & Sons, 2009. URL: https://doi.org/10.1002/9780470558027.ch17.
  34. Chris Walshaw and Martin Berzins. Dynamic load-balancing for PDE solvers on adaptive unstructured meshes. Concurrency: Practice and Experience, 7(1):17-28, 1995. URL: https://doi.org/10.1002/cpe.4330070103.
  35. Chris Walshaw, Mark Cross, and Martin G. Everett. Parallel dynamic graph partitioning for adaptive unstructured meshes. Journal of Parallel and Distributed Computing, 47(2):102-108, 1997. URL: https://doi.org/10.1006/jpdc.1997.1407.
  36. Pei-bai Zhou. Numerical Analysis of Electromagnetic Fields. Electric Energy Systems and Engineering Series. Springer, 1993. URL: https://doi.org/10.1007/978-3-642-50319-1.
  37. Olgierd C. Zienkiewicz, Robert L. Taylor, and David D. Fox. The Finite Element Method for Solid and Structural Mechanics. Butterworth-Heinemann, 2014. URL: https://doi.org/10.1016/C2009-0-26332-X.
  38. Olgierd C. Zienkiewicz, Robert L. Taylor, and Perumal Nithiarasu. The Finite Element Method for Fluid Dynamics. Butterworth-Heinemann, 2014. URL: https://doi.org/10.1016/C2009-0-26328-8.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact