Please use this identifier to cite or link to this item:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/16204
Title: | Υλοποίηση Map-reduce Σε Χωρικά Δεδομένα Με Τον Αλγόριθμο Dijkstra |
Authors: | Δημήτρης Θεοδωράκης Σελλής Τιμολέων |
Keywords: | map-reduce javascript dijkstra graph-partitioning database |
Issue Date: | 8-Dec-2011 |
Abstract: | Η παρούσα διπλωματική εργασία επικεντρώνεται στην υλοποίηση αλγορίθμου εύρεσης συντομότερων μονοπατιών σε τμηματοποιημένους γράφους με τη χρήση παραλληλοποίησης και map-reduce σε web browsers με Javascript. Ως αλγόριθμος συντομότερου μονοπατιού χρησιμοποιείται ο Dijkstra ενώ τα πειραματικά δεδομένα μας προκύπτουν από το γράφο του οδικού δικτύου της Δυτικής Ευρώπης, που διατίθενται για επιστημονική χρήση από το Ινστιτούτο Karlsruher. Η διαδικασία χωρίζεται σε τρία βασικά στάδια. Στο στάδιο της προ-επεξεργασίας δεδομένων τμηματοποιείται ο γράφος σε κελιά με τη βοήθεια του εργαλείου METIS. Στο δεύτερο στάδιο δημιουργείται ένα γράφος επικάλυψης, με τη βοήθεια της map-reduce διαδικασίας που εκτελείται από τα προγράμματα περιήγησης των χρηστών (Javascript), ενώ το τρίτο και τελευταίο στάδιο περιλαμβάνει την εύρεση του συντομότερου μονοπατιού με τη χρήση του γράφου επικάλυψης που κατασκευάστηκε στο δεύτερο στάδιο. Να σημειωθεί ότι η παρούσα εργασία ασχολείται μονάχα με τα δύο πρώτα στάδια ενώ το τελευταίο αναφέρεται για λόγους συνέπειας. |
URI: | http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/16204 |
Appears in Collections: | Διπλωματικές Εργασίες - Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
DT2011-0309.pdf | 1.97 MB | Adobe PDF | View/Open |
Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.