路网中移动对象快照K近邻查询处理  

Snapshot K neighbor query processing on moving objects in road networks

作　　者：卢秉亮[1] 刘娜[1] 

机构地区：[1]沈阳航空航天大学计算机学院,沈阳110136

出　　处：《计算机应用》2011年第11期3078-3083,共6页journal of Computer Applications

摘　　要：扩展了一种支持路网中移动对象的位置相关查询框架的功能,利用存在磁盘上的R树来存储网络连通性和一种基于内存的网格结构来维持移动对象的位置更新,提出了基于范围查询(MNDR)的快照K近邻查询算法(SKNN),对空间中的任意一条边,分析可能受影响的最大数量和最小数量的网格单元格,说明用于快照范围查询处理的搜索空间的最大范围,预估包含查询结果的子空间,使用这个子空间作为范围调用MNDR来有效地计算路网中查询点的KNN POI,降低I/O成本,缩短查询时间。通过实验对比,当规模扩展到数十万的移动对象时,SKNN比种有效查询处理空间网络数据的预计算方法 S-GRID有更好大的系统吞吐量。The functionality of a framework that supported location-based services on moving objects in road networks was extended and Snapshot K Nearest Neighbor（SKNN） queries based on Mobile Network Distance Range（MNDR） queries was proposed using an on-disk R-tree to store the network connectivity and an in-memory grid structure to maintain the moving object position updates.The minimum and maximum number of grid cells of a given arbitrary edge in the space that were possibly affected were analyzed.The maximum bound that could be used in snapshot range query processing to prune the search space was shown.SKNN estimated the subspace containing the query results and used the subspace as range to efficiently compute the KNN POI from the query points to reduce I/O cost and time of query.Analysis shows that the maximum bound can be used in snapshot range query processing to prune the search space.The contrast experiments show that SKNN has better system throughput than S-GRID while scaling to hundreds of thousands of moving objects.

关 键 词：空间数据库 范围查询 位置相关 K近邻 

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