移动对象反向最近邻查询技术研究  

Research on Reverse Nearest Neighbor Queries Technique for Moving Objects

作　　者：王晓辉[1] 曹泽文[1] 谭川豫[1] 

机构地区：[1]国防科技大学信息系统与管理学院,长沙410073

出　　处：《计算机工程》2010年第20期66-67,70,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(70771110)

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]