Search Space Reduction using K-means Clustering and Adjacency matrices for GIS Usage Information Retrieval

Abstract

Nowadays, people widespread use of smartphones and ubiquitous devices for map based services. As the transport network is complicated and massive, people may be confused to reach the desired location after finding a location. Many searching techniques are used for finding the shortest path, might still not be fast enough in certain realtime applications because of complexing transport network. Search time can be reduced if we pruned unnecessary clusters in a complex large graph. Memory utilization is safe for the processing time if we reduce search space in complex network. For removing unnecessary clusters, adjacency matrices, distance based methods and K-means clustering can be used. ArcGIS software and popular shortest path algorithms are applied to find the shortest path from one location to another on the Android mobile platform. In addition, the performance of finding the shortest path using popular A* and Dijkstra algorithms with bidirectional search can be compared before and after removing unnecessary clusters.