An Efficient Technique for Distance Computation in Road Networks

With recent advances in wireless communication and position technologies, it became possible to collect and record trajectories of moving objects. Thus, many services in road networks such as nearest neighbor querying and the analysis of moving objects trajectories come into sight which present challenges to the database community. The essential part of the queries behind these services is related to the distance computation in road networks. In this paper, we focus on this problem and propose a method for distance computation in road networks including the access of network connectivity information. We present an algorithm called circle which returns all moving objects within a given distance (radius) to a given network position during some time intervals in the past. We choose an existed index structure, the MON-Tree, to record the framework presented in this paper which is to store and query network connectivity information. The circle operator is used to experimentally evaluate our approach. The results show that the performance of the technique presented in this paper outperforms the only existing index structure in the literature capable to support this kind of query.