Abstract—Due to wireless communication technologies, positioning technologies, and mobile computing develop quickly, mobile services are becoming practical and important on big spatiotemporal databases management. Mobile service users move only inside a spatial network, e.g. a road network. They often issue the K Nearest Neighbor (KNN) query to obtain data objects reachable through the road network. The challenge problem of mobile services is how to efficiently answer the data objects which user interest to the corresponding mobile users. Lu et al. have proposed a RNG (Road Network Grid) index for speeding up the KNN query on real-life road networks. Since they divide the road, this makes the number of points of the graph increase. It increases the execution time of constructing the index structure. Therefore, in this paper, we propose a network model that captures the real-life road networks. We map the real-life road networks into graph directly. Then, based on our network model, we propose an EBNA (Edge-Based Nine-Area tree) index structure to make the search time of obtaining the interest edge information quickly. From our simulation result, we show that the performance of constructing the EBNA index is better than constructing the RNG index and the performance of the KNN query processing by using EBNA index is better than the KNN query processing by using RNG index.
Index Terms—Edge-based, index structure, KNN, road network.
Y. I. Chang and M. H. Tsai are with the Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, 80424 Taiwan (e-mail: changyi@cse.nsysu.edu.tw, d023040002@student.nsysu.edu.tw).
[PDF]
Cite: Ye-In Chang, Meng-Hsuan Tsai, and Xu-Lun Wu, "An Edge-Based Algorithm for Spatial Query Processing in Real-Life Road Networks," International Journal of Modeling and Optimization vol. 5, no. 4, pp. 308-312, 2015.
