Monitoring continuous all k-nearest neighbor query in mobile network environments

This paper investigates the continuous all k-nearest neighbor (CAkNN) problem in a pervasive and mobile computing environment, which is a spatial query that continuously monitors kNN results for all mobile users in the network for a specified period of time. This problem is characterized by the fact that a single movement of a node may result in that several users have to re-compute their kNN results. The affected nodes are the moving node itself and its Reverse-kNN (RkNN) nodes at both the previous and the new locations. This paper proposes the use of a bucket point-region quadtree to index mobile users. This structure is unique in that it can be readily reorganized for maintenance purpose when nodes move. In addition, it helps to quickly determine an appropriate search radius for each of these nodes. In this paper, we have proposed two novel RkNN techniques that are tailored for the structure with only small maintenance overhead. These techniques enable us to integrate kNN and RkNN searching operations together so as to facilitate continuous monitoring of the query result. Based on the notion of maximum prune distance, we present two algorithms to offer true continuity for a CAkNN query. Simulation results show that our algorithms outperform existing solutions by a significant margin.