Implementation of Map-Reduce on Spatial Data using the Dijkstra Algorithm on Web Clients Full text

Dimitris Theodorakis
School of Electrical and Computer Engineering, NTUA
Diploma Thesis
Abstract. This diploma thesis is focused on the implementation of a single source shortest path algorithm for partitioned graphs, using parallel computing and map-reduce on web browsers with Javascript. Dijkstra 's algorithm is used for shortest path calculations whereas the dataset used for the experiments comes from a road graph of Western Europe that the Institute of Karlsruher offers for research. The process is divided in three basic steps. In the first step we partition graph using the METIS tool. In the second step we construct an overlay graph by running the map-reduce process via web visitors. In the third step we calculate the actual shortest path by using the overlay graph that was constructed in the previous steps. It should be mentioned that this diploma thesis deals only with the first two steps. The last step is only mentioned for consequence.