Study On K Nearest Neighbor Query Based On Road Networks In Mobile Database

In moving objects database, K nearest neighbor query has become one of the most attractive research fields. Many existing K nearest neighbor query methods are based on the Euclidean space, which consider relative positions of two objects in space. However, in the road network condition, the results of K nearest neighbor query depends on the connectivity of road network. More recent works research K nearest neighbor query on static object based on road network. K nearest neighbor query on moving objects based on road networks mainly has two challenges, manage efficiently moving objects position update and offer fast network distance calculations. Therefore, moving object index strategy and K nearest neighbor query strategy need to be studied. It is a challenging research topic that how to adopt a fast and efficient methods to deal with moving object K nearest neighbor query.Based on the detailed analyzing existing K nearest neighbor query methods, snapshot k nearest neighbor queries (SKNN) method based on mobile network range queries(MNDR)is presented using an on-disk R-tree to store the network connectivity and an in-memory grid structure to maintain moving object position updates. Given an arbitrary edge in the space,by analyzing the maximum and minimum number of grid cells that are possibly affected,the maximum bound can be used in range query processing to prune the search space is ensured.SKNN estimates the subspace containing the query results and uses the subspace as range to efficiently compute the KNN Points of Interest (POIs) from the query points to reduce I/O cost and time of query. The contrast experiments show that SKNN has better system throughput than S-GRID while scaling to a large number of moving objects.