Abstract: To solve the problem of continuous range queries for moving objects in road networks, the network distance is adopted as the metric. First, a data storage model is designed for the road networks, the moving objects and the queries in main memory. Next, based on the data model two algorithms are proposed for continuous range queries. The incremental range query algorithm (IRQA) minimizes the re-computation for each query by using the expansion tree and the influence list data structure; however the group range query algorithm (GRQA) achieves the goal through grouping the queries on the same route, making the observation that these queries may share the same execution. Finally, the experimental results show that GRQA has better performance when the queries are centra- lized-distributed, while IRQA is better when queries are uniformly distributed. Meanwhile, they are both more ef-fective than the original brute force algorithm which re-computes each query periodically.

Key words: continuous range query, incremental range query algorithm (IRQA), expansion tree, group range query algorithm (GRQA), route

摘要： 研究了采用网络距离的道路网上移动对象连续多范围查询处理技术。设计了道路网、移动对象和查询数据在内存中存储的数据模型。基于该数据模型提出了两种道路网上的移动对象连续多范围查询处理算法。其中, 增量式范围查询算法(incremental range query algorithm, IRQA)通过使用扩张树和影响列表结构减少查询的重新计算; 组范围查询算法(group range query algorithm, GRQA)利用同一路径上多查询的结果具有相关性这一特点减少查询的重新计算。实验结果表明GRQA算法在查询分布比较集中时性能较优, IRQA算法在查询均匀分布时性能较优, 此外, 两种算法均优于重新计算所有查询结果的原始算法。

关键词: 连续范围查询, 增量式范围查询算法, 扩张树, 组范围查询算法, 路径