Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/16204
Τίτλος: | Υλοποίηση Map-reduce Σε Χωρικά Δεδομένα Με Τον Αλγόριθμο Dijkstra |
Συγγραφείς: | Δημήτρης Θεοδωράκης Σελλής Τιμολέων |
Λέξεις κλειδιά: | map-reduce javascript dijkstra graph-partitioning database |
Ημερομηνία έκδοσης: | 8-Δεκ-2011 |
Περίληψη: | Η παρούσα διπλωματική εργασία επικεντρώνεται στην υλοποίηση αλγορίθμου εύρεσης συντομότερων μονοπατιών σε τμηματοποιημένους γράφους με τη χρήση παραλληλοποίησης και map-reduce σε web browsers με Javascript. Ως αλγόριθμος συντομότερου μονοπατιού χρησιμοποιείται ο Dijkstra ενώ τα πειραματικά δεδομένα μας προκύπτουν από το γράφο του οδικού δικτύου της Δυτικής Ευρώπης, που διατίθενται για επιστημονική χρήση από το Ινστιτούτο Karlsruher. Η διαδικασία χωρίζεται σε τρία βασικά στάδια. Στο στάδιο της προ-επεξεργασίας δεδομένων τμηματοποιείται ο γράφος σε κελιά με τη βοήθεια του εργαλείου METIS. Στο δεύτερο στάδιο δημιουργείται ένα γράφος επικάλυψης, με τη βοήθεια της map-reduce διαδικασίας που εκτελείται από τα προγράμματα περιήγησης των χρηστών (Javascript), ενώ το τρίτο και τελευταίο στάδιο περιλαμβάνει την εύρεση του συντομότερου μονοπατιού με τη χρήση του γράφου επικάλυψης που κατασκευάστηκε στο δεύτερο στάδιο. Να σημειωθεί ότι η παρούσα εργασία ασχολείται μονάχα με τα δύο πρώτα στάδια ενώ το τελευταίο αναφέρεται για λόγους συνέπειας. |
URI: | http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/16204 |
Εμφανίζεται στις συλλογές: | Διπλωματικές Εργασίες - Theses |
Αρχεία σε αυτό το τεκμήριο:
Αρχείο | Μέγεθος | Μορφότυπος | |
---|---|---|---|
DT2011-0309.pdf | 1.97 MB | Adobe PDF | Εμφάνιση/Άνοιγμα |
Όλα τα τεκμήρια του δικτυακού τόπου προστατεύονται από πνευματικά δικαιώματα.