Amorphous parallel algorithms for shortest paths

• Κύριος συγγραφέας: Παπαδόπουλος, Αναστάσιος
• Άλλοι συγγραφείς: Ζαρολιάγκης, Χρήστος
• Μορφή: Thesis
• Γλώσσα: English
• Έκδοση: 2019
• Θέματα: Amorphous parallelism; Delta-stepping; Time-dependent networks; Oracle; Άμορφοι παραλληλισμοί; Χρονοεξαρτώμενα δίκτυα; 006.31

A new, efficient and highly engineered variant of the well-known Delta-Stepping(DS) algorithm is presented for computing shortest paths in time-dependent networks using amorphous parallelism. This new variant was experimentally evaluated in two scenarios, using real-world data sets (road networks of Berlin, Germany and W. Europe). The experimental study demonstrated that the new DS variant is beneficial for the case of time-dependent road networks and it scales very well with the network size. In particular, the use of the new DS variant for solving the time-dependent many-to-all shortest path problem achieves a speedup of 22.2% compared to the classical time-dependent Dijkstra’s algorithm, while its embedding into state-of-the-art time dependent oracles (that answer in real-time earlier arrival queries for any node pair and departure time) improves the oracle pre-processing phase up to 32% and the oracle query time up to 66%.