面向移动对象的高效组最近邻居查询方法

An Efficient Technique for Group Nearest Neighbor Queries of Moving Objects

组最近邻居查询是移动对象数据库重要的查询类型之一。本文提出了一种基于网格索引结构的剪枝搜索策略,将空间区域划分为网格,通过对象点的网格单元标识减少组最近邻居查询所需要的节点访问代价。用步长迭代法得到查询对象集的质心,提出了一种移动对象组最近邻居查询MOGNN算法,采用更精确的裁剪搜索空间准则,减少了查询所需要访问的节点数目。实验结果与分析表明,基于网格索引的MOGNN查询算法具有良好的查询性能。

Group nearest neighbor（GNN） query is an important researching area in the moving object databases.In this paper a search space pruning method which is based on grid access method and then devises the space into grids is presented.The moving objects are indexed by their grid identifier,and by this the disk accesses of GNN queries are reduced.Using gradient descent method an approximate centroid can be quickly obtained.Also developed is an efficient group nearest neighbor query algorithm which uses a more precise branch and bound searching strategy,reducing the disk I/O greatly.Experimental results and analysis show that the MGNN algorithm for grid indexing method has a good query performance.