Incremental Processing of Continuous K Nearest Neighbor Queries over Moving objects

For a given set of moving objects and a k nearest neighbor query q, the processing of Continuous K Nearest Neighbor (CKNN) query refers to search the k nearest objects for q and continuously monitor its result in real-time with the objects and the query point moving. Most existing works about processing CKNN queries usually exist some flaws about the index maintenance, real-time updates of results, and the query cost, which makes them hardly can perfectly settle this issue. To address this challenge, we propose an incremental search algorithm to handle CKNN queries over a tremendous volume of moving objects with a Random Estimate method. In particularly, our approach adopts the grid index to maintain the moving objects in real-time. For a given query q, IS-CKNN first employs YPK-CNN algorithm to compute the initial result of q. Next, it designs the Random Estimation (RE) method, to rapidly estimate an appropriate search region that guarantees covering k nearest neighbors of q based on its previous search scope. This strategy can immediately compute the appropriate search space for the moving query without iteratively enlarging the search region, which can greatly enhance the search efficiency. Finally, we conduct extensive experiments to fully evaluate the performance of our proposal.