Study On K Nearest Neighbor Queries Of Moving Objects Based On Road Networks

In moving objects database, k nearest neighbor queries attracts much attention. Many k nearest neighbor queries methods existed were based on the Euclidean space, these methods considered relative positions of two objects in space. However, In the road network condition, the result of the k nearest neighbor quires is rest with the connectivities of road network, not the objects' relative positions.In this field, Christian et proposed a Island method in 2005, it is a k nearest neighbor query method of moving objects based on road network,but this method has three flaws which are k nearest neighbor query in constrained road network,traffic-jam exploration and optimize of Island's radius. This article has studied k nearest neighbor query of moving objects based on road network in view of above three aspects ,and proposed the Island+ method, which has made the improvement to the memory structure and trajectory preservation of neighbor objects.First, on the basis of integrated analysis and research of k nearest neighbor query of moving objects based on road network method, road network modeling is improved. it Simulates the street intersection changing restriction and road section available condition with transition matrix and a flag bit , which simulated the simply limitd road network .Secondly, on the basis of the work above, a new traffic-jam exploration mechanism is proposed which realizes the road section traffic jam survey. The data can be temporarily stored, which has provided limiting condition for the pre-computation part .so our method can even more draw close to the transportation conditionin in real-life .In succession, This article has given the region radius optimization method,which has enhanced update and querying efficiency through adjusting the radius of small density region and big density region. Finally, its good performance is proved by experiment results.