Researches On Continuous Nearest Neighbors Query In Road Networks

The problem of Continuous K Nearest Neighbor(KNN) Query in a road network has been studied by many researchers,and is frequently used in Geographical Information System.CKNN is defined as the KNN of any point on a given path.The result of this type of query is a set of intervals,or split points,and their associated KNN.The split points specify where on the path the KNN of a moving object changes, and the intervals(bounded by the split points) specify the locations that the KNN of a moving object remains the same.We can pre-compute CKNN of any path in a road network and store it.This brings system a quicker response to user's KNN query of any query point.In road networks,the distance between two points is the length of the shortest path connecting them.There are mainly two methodologies to solve CKNN query. One is adapting divide-and-conquer method,and the other one is using linear functions to represent the distance between two points in the road network.An approach on conquer-and-divide basis to CKNN query is introduced in this thesis,whose name is Split.Split method divides the query path into some subpaths, and focuses on computing CKNN for every subpath.Finally,Split method merges the results of all subpaths to get the CKNN for the query path.Experiments demonstrate that Split outperforms IE method in a real-world road network data set,and it works more efficiently in the high-density object point circumstance than UNICONS.