Performing mobile k nearest neighbor （MkNN） queries whilst also being mobile is a challenging problem. All the mobile objects issuing queries and/or being queried are mobile. The performance of this kind of query re...Performing mobile k nearest neighbor （MkNN） queries whilst also being mobile is a challenging problem. All the mobile objects issuing queries and/or being queried are mobile. The performance of this kind of query relies heav- ily on the maintenance of the current locations of the objects. The index used for mobile objects must support efficient up- date operations and efficient query handling. This study aims to improve the performance of the MkNN queries while re- ducing update costs. Our approach is based on an observa- tion that the frequency of one region changing between being occupied or not by mobile objects is much lower than the frequency of the position changes reported by the mobile ob- jects. We first propose an virtual grid quadtree with Voronoi diagram （VGQ-Vor）, which is a two-layer index structure that indexes regions occupied by mobile objects in a quadtree and builds a Voronoi diagram of the regions. Then we propose a moving k nearest neighbor （kNN） query algorithm on the VGQ-Vor and prove the correctness of the algorithm. The ex- perimental results show that the VGQ-Vor outperforms the existing techniques （Bx-tree, Bdual-tree） by one to three or- ders of magnitude in most cases.展开更多
文摘Performing mobile k nearest neighbor （MkNN） queries whilst also being mobile is a challenging problem. All the mobile objects issuing queries and/or being queried are mobile. The performance of this kind of query relies heav- ily on the maintenance of the current locations of the objects. The index used for mobile objects must support efficient up- date operations and efficient query handling. This study aims to improve the performance of the MkNN queries while re- ducing update costs. Our approach is based on an observa- tion that the frequency of one region changing between being occupied or not by mobile objects is much lower than the frequency of the position changes reported by the mobile ob- jects. We first propose an virtual grid quadtree with Voronoi diagram （VGQ-Vor）, which is a two-layer index structure that indexes regions occupied by mobile objects in a quadtree and builds a Voronoi diagram of the regions. Then we propose a moving k nearest neighbor （kNN） query algorithm on the VGQ-Vor and prove the correctness of the algorithm. The ex- perimental results show that the VGQ-Vor outperforms the existing techniques （Bx-tree, Bdual-tree） by one to three or- ders of magnitude in most cases.
