运动对象组最近邻连续查询的有效期延迟策略

Extending the valid time of continuous group nearest neighbor query with moving objects

针对基于概念划分的运动对象组最近邻连续查询算法中结果列表因定长而有效期较短的问题,采取了变长结果列表和定长距离阈值的更新策略,通过提高局部更新的有效性以减少初始化计算的次数,并利用栅格索引特性提出了基于扩展外包容影响区域的查询初始化方法,从而在不增加单次局部更新和初始化计算开销的前提下降低了连续性查询的总计算开销.实验证明:在对象的分布情况稳定时,优化策略的计算开销约为基于概念划分的定长列表方法的70%,而在对象分布发生变化时优势更为明显.

The continuous group nearest neighbor query algorithm basing on the conceptual partitio ning method used a result object list of fixed length, which is easy to be invalidated. To prolong the period of the result list＇s validity, an updating strategy with varied-length result list and fixed distance threshold was adopted, so as to reduce the times of initializing the query. Moreover, an initializing strategy using the extended bounding influence region depending on the grid index is proposed. With the two strategies, the CPU cost of continuous query is reduced without increasing the cost of either initialization or updates of result object list in one cycle. The experiment result shows that the CPU cost with the optimizing strategies can be about 70 ~ of the conceptual partitioning method when the distribution of objects is stable, and the optimizing is more obvious when the distribution changes during the continuous query.