方向感知的路网移动对象范围查询算法

Direction-aware Moving Object Range Query Algorithm in Road Network

路网移动对象的范围查询作为空间查询处理中经典的查询类型之一,已经在很多领域中得到了广泛应用。但现有的路网移动对象范围查询方法仍然存在一些不足:一方面,大多数的路网移动对象范围查询方法仅考虑了路网距离,而很少关注范围内移动对象在路网中的运动方向;另一方面,为数不多的考虑了移动对象运动方向的查询方法,几乎都基于欧氏空间进行查询处理,不能应用到大规模的路网来判断范围内的移动对象是否朝向查询点运动。针对在大规模复杂路网下如何高效地查找附近范围内所有朝向查询点的移动对象的问题,提出了一种方向感知的路网移动对象范围查询算法。该算法使用R-tree和简单网格作为底层索引支撑,同时利用一种高效的朝向查询点的路网移动对象判定方法,来高效地查找范围内朝向查询点的移动对象。分别从查询范围、移动对象数量以及网格划分数量3个方面进行实验分析,结果表明方向感知的路网移动对象范围查询算法在合理的参数范围内具有较高的实用性和有效性。

The range query on moving objects in road network is one of the classical query methods in spatial query processing,which has been widely used in many fields.However,there are still some shortcomings in the existing moving object range query methods in road networks.On the one hand,most of them only consider the network distance,but pay less attention to the movement direction of moving objects in road networks.On the other hand,a few query me-thods considering the movement direction are based on Euclidean space and can’t not be applied to large-scale road network to determine whether moving objects move toward query point.Aiming at the problem of accurately and efficiently finding moving objects toward the query point in large and complex road network,this paper proposed a direction-aware moving object range query algorithm in road network.In this method,R-tree and simple grid are taking as underlying index support,and an efficient determination method of moving object toward query point in road network is exploited,so as to efficiently query the moving object toward query point.At last,this paper designed experiments in terms of the query range,the number of moving object and the number of grid partition to evaluate the performance of the proposed algorithm.The experimental results show that the algorithm can achieve good query performance even in the case of large-scale complex road network under the condition that the index configuration is reasonable.