ExTCKNN: Expanding Tree-Based Continuous K Nearest Neighbor Query in Road Networks With Traffic Rules

Abstract

The existing continuous nearest neighbor query algorithms of moving objects in road networks do not consider any traffic rule and assume that the speed of moving objects is constant and the topology of road networks never change. However, in real road networks, the object’s speed and the road network’s structure change frequently Hence, these would make the existing methods ineffective when applying to the real-world road network environment To overcome the aforementioned disadvantages, we propose a Data Modeling approach of Road Networks with traffic rules (called DMRNR) and design a novel Expanding Tree-based Continuous k Nearest Neighbors algorithm (abbreviate for ExTCKNN) that can be well adopted to the actual road network environment. The algorithm consists of three steps: 1) it obtains the query results to store using DMRNR in the initial phase; 2) it maintains the data model of road networks by monitoring the real-time change information; and 3) the results are generated according to the submitted query with the updated data model and the latest state of moving objects The merit of the proposed algorithm lies in that it queries the nearest neighbors by taking the movements of the moving object and the variety of the road networks into consideration Extensive experiments are conducted and the experimental results demonstrate a significant improvement of the proposed method when compared with conventional solutions.

Keywords

• Road networks
• k nearest neighbor
• continuous query
• expanding tree data model of road network