摘要：

提出一种基于自调节网格索引的反向最近邻查询(RNNQ)算法，将空间划分为大小相等的网格单元，每个单元作为一个桶存储移动对象，采用基于桶内对象数目和网格几何特征的剪枝策略减少反向最近邻查询所需访问的节点。查询点周围单元桶内对象过多时进行二次网格划分，减小节点访问代价。实验结果表明，该算法具有良好的查询性能，优于基于TPR树索引的RNNQ算法。

关键词: 移动对象, 反向最近邻查询, 自调节网格索引

Abstract:

This paper presents a Reverse Nearest Neighbor Queries(RNNQ) algorithm based on Auto-Selection Grid Index(ASGI). ASGI divides the space into an equal size network, and each cell stores moving objects as a bucket. RNNQ algorithm uses the strategy of the bucket’s object number and the grid geometry characteristic to reduce the access node the RNNQ must visit. ASGI will repeat the previous action to decrease the cost again if objects around the query point are too many. Experimental results show that RNNQ algorithm based on ASGI has good query performance and outperforms RNNQ algorithm based on TPR tree.

Key words: moving object, Reverse Nearest Neighbor Queries(RNNQ), Auto-Selection Grid Index(ASGI)

中图分类号: 

• TP311