Λεπτομέρειες

ΕίδοςΔιπλωματική
ΚωδικόςDIPL-2011-10
ΤίτλοςΥλοποίηση Map-Reduce σε χωρικά δεδομένα με τον αλγόριθμο Dijkstra
ΣυγγραφέαςΔημήτρης Θεοδωράκης
Έτος2011
Λέξεις κλειδιάmap-reduce, javascript, dijkstra, graph-partitioning, database
ΠερίληψηΗ παρούσα διπλωματική εργασία επικεντρώνεται στην υλοποίηση αλγορίθμου εύρεσης συντομότερων μονοπατιών σε τμηματοποιημένους γράφους με τη χρήση παραλληλοποίησης και map-reduce σε web browsers με Javascript. Ως αλγόριθμος συντομότερου μονοπατιού χρησιμοποιείται ο Dijkstra ενώ τα πειραματικά δεδομένα μας προκύπτουν από το γράφο του οδικού δικτύου της ∆υτικής Ευρώπης, που διατίθενται για επιστημονική χρήση από το Ινστιτούτο Karlsruher. Η διαδικασία χωρίζεται σε τρία βασικά στάδια. Στο στάδιο της προ-επεξεργασίας δεδομένων τμηματοποιείται ο γράφος σε κελιά με τη βοήθεια του εργαλείου METIS. Στο δεύτερο στάδιο δημιουργείται ένα γράφος επικάλυψης, με τη βοήθεια της map-reduce διαδικασίας που εκτελείται από τα προγράμματα περιήγησης των χρηστών (Javascript), ενώ το τρίτο και τελευταίο στάδιο περιλαμβάνει την εύρεση του συντομότερου μονοπατιού με τη χρήση του γράφου επικάλυψης που κατασκευάστηκε στο δεύτερο στάδιο. Να σημειωθεί ότι η παρούσα εργασία ασχολείται μονάχα με τα δύο πρώτα στάδια ενώ το τελευταίο αναφέρεται για λόγους συνέπειας.
ΚατηγορίαGeographic Information Systems
Αρχείο Επισκόπηση


Επιστροφή στην αρχική σελίδα