Parallel and Improvement of Pre-computation Technique for Approximation Shortest Distance Query

With the development of mobile Internet, more and more applications are associated with location. There are many applications just care about shortest distance of two points and do not care about the paths, such as take-away applications. The problem of shortest distance query of objects has caught many researchers´ attention in recent years. One of solutions is pre-computation. We can select representative node for each node in graph, and approximation shortest distance of two nodes can be obtained by computing the distance between their representative nodes. The distance between any two representative nodes is pre-computed. In this paper, we propose a more effective algorithm to select representative such that the number of representatives is less than random algorithm, and we use parallel approach to compute the shortest distance between representatives and optimize the data struct to reduce the memory cost of distance result. We evaluate our approach on a real data set. The evaluation result shows the size of representative nodes are less than random algorithm, and the computing time and memory cost reduce effectively.