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

Abstract: 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.

Key words: spatial database, range query, location-dependent, K Nearest Neighbor (KNN)