Υλοποίηση Map-reduce Σε Χωρικά Δεδομένα Με Τον Αλγόριθμο Dijkstra

Abstract

Η παρούσα διπλωματική εργασία επικεντρώνεται στην υλοποίηση αλγορίθμου εύρεσης συντομότερων μονοπατιών σε τμηματοποιημένους γράφους με τη χρήση παραλληλοποίησης και map-reduce σε web browsers με Javascript. Ως αλγόριθμος συντομότερου μονοπατιού χρησιμοποιείται ο Dijkstra ενώ τα πειραματικά δεδομένα μας προκύπτουν από το γράφο του οδικού δικτύου της Δυτικής Ευρώπης, που διατίθενται για επιστημονική χρήση από το Ινστιτούτο Karlsruher. Η διαδικασία χωρίζεται σε τρία βασικά στάδια. Στο στάδιο της προ-επεξεργασίας δεδομένων τμηματοποιείται ο γράφος σε κελιά με τη βοήθεια του εργαλείου METIS. Στο δεύτερο στάδιο δημιουργείται ένα γράφος επικάλυψης, με τη βοήθεια της map-reduce διαδικασίας που εκτελείται από τα προγράμματα περιήγησης των χρηστών (Javascript), ενώ το τρίτο και τελευταίο στάδιο περιλαμβάνει την εύρεση του συντομότερου μονοπατιού με τη χρήση του γράφου επικάλυψης που κατασκευάστηκε στο δεύτερο στάδιο. Να σημειωθεί ότι η παρούσα εργασία ασχολείται μονάχα με τα δύο πρώτα στάδια ενώ το τελευταίο αναφέρεται για λόγους συνέπειας.