Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/12620
Title: Amorphous parallel algorithms for shortest paths
Other Titles: Άμορφοι παράλληλοι αλγόριθμοι για το πρόβλημα συντομότερων διαδρομών
Authors: Παπαδόπουλος, Αναστάσιος
Keywords: Amorphous parallelism
Delta-stepping
Time-dependent networks
Oracle
Keywords (translated): Άμορφοι παραλληλισμοί
Χρονοεξαρτώμενα δίκτυα
Abstract: 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%.
Abstract (translated): Μια νέα, αποτελεσματική και εξαιρετικά σχεδιασμένη παραλλαγή του γνωστού αλγόριθμου Delta-Stepping (DS) παρουσιάζεται για τον υπολογισμό των συντομότερων διαδρομών σε χρονικά εξαρτώμενα δίκτυα χρησιμοποιώντας άμορφο παραλληλισμό. Αυτή η νέα παραλλαγή αξιολογήθηκε πειραματικά σε δύο σενάρια, χρησιμοποιώντας σύνολα δεδομένων πραγματικού κόσμου (οδικά δίκτυα του Βερολίνου, της Γερμανίας και της Δ. Ευρώπης). Η πειραματική μελέτη κατέδειξε ότι η νέα παραλλαγή DS είναι επωφελής για την περίπτωση των οδικών δικτύων που εξαρτώνται από το χρόνο και κλιμακώνεται πολύ καλά με το μέγεθος του δικτύου. Συγκεκριμένα, η χρήση της νέας παραλλαγής DS για την επίλυση του προβλήματος των χρονοεξαρτώμενων συντομότερων διαδρομών, επιτυγχάνει 22,2% βελτίωση σε σύγκριση με τον κλασικό αλγόριθμο Dijkstra που εξαρτάται από το χρόνο, ενώ η ενσωμάτωσή του σε αλγόριθμους μαντείων τελευταίας τεχνολογίας, (που απαντούν σε ερωτήματα συντομότερων διαδρομών σε πραγματικό χρόνο για οποιοδήποτε ζεύγος κόμβων και ώρα αναχώρησης) βελτιώνει τη φάση προεπεξεργασίας του μαντείου έως 32% και το χρόνο ερωτήματος έως 66%.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΜΔΕ)



This item is licensed under a Creative Commons License Creative Commons