Study On Continuous K Nearest Neighbor Queries Over Moving Objects

Location based service(LBS) provides users with information services related to their positions which can be obtained through mobile devices and wireless networks infrastructure, such as navigation services, traffic scheduling, logistics management, emergency call, location advertising, etc. Location based services generally related to queries over a large number of moving objects, k nearest neighbor(kNN) query is one of the most important query.The capabilities of k nearest neighbor query in addressing the needs of the practical application become more and more obvious, attracted wide attention in relevant research areas. At present, k nearest neighbor query technologies over static objects in euclidean space has been good developed, but few continuous k nearest neighbor(CkNN) query technologies considered moving objects and road networks, when face to a large number of concurrent queries, the existing query technologis made poor performance.This paper is a study on continuous k nearest neighbor queries over moving objects based on road networks, aims to improve the query processing efficiency of the server-side as much as possible. The work of this paper is mainly reflected in the following aspects:(1) Deeply analyzed the existing classical query algorithms which considered moving objects based on road networks or euclidean space, summarized its general technical ideas, discussed the advantages and disadvantages of these methods, compared the query processing based on road networks with that in euclidean space, and summed the difficulty of processing k nearest neighbor queries which based on road networks.(2) By analyzed the characteristic of k nearest neighbor queries which based on road networks, this paper proposed a shared computation method named initial result computing algorithm, the algorithm sufficiently reused other queries’computation result in the query processing, thus avoided redundant search of road networks.(3) This paper presented an expansion tree based continuous k nearest neighbor query algorithm for the highly dynamic road networks(TL-CkNN), which maintain the reuslt periodically for all the queries registerd in the system, use data updates to prune the expansion tree, then based on the pruned expansion tree continue to result recompuation, thereby reduced the duplication of road network expansion. Experiment results show this algorithm has better performance than other algorithms in the highly dynamic road networks.