%0 Journal Article
%T 基于多线程的不确定移动对象连续k近邻查询
%A 齐建鹏
%A 于彦伟
%A 王创存
%A 曹磊
%A 宋鹏
%J 浙江大学学报(工学版)
%D 2018
%R 10.3785/j.issn.1008-973X.2018.01.019
%X 针对不确定数据下的大规模连续k近邻查询请求，基于不确定移动对象连续k近邻查询的Rate方法，提出高效的基于多核多线程的并行查询处理框架.根据查询对象的运动速度与相对位置确定查询请求间是否采用查询复用，确定查询复用时的距离边界.提出密度网格扩展的多线程数据分发方法，解决了负载均衡问题，将空间位置相邻的查询请求划分到同一线程，提高查询复用率.通过多线程间的内存共享机制，对计算过的移动对象的预测区域实现计算复用.在大规模交通数据集上验证了所提算法的有效性与查询性能，相比传统的Rate方法，所提并行算法的加速比可达37.</br>Abstract: An efficient multi-core and multi-threading based framework was proposed for searching k-NNs of large-scale queries with uncertain locations based on the continuous k-NN query method called Rate for uncertain moving objects. The velocities and locations of different query objects were used to judge whether employing query reuse and give the bound of reuse distance. The density grid based multi-threaded data partition method was proposed to resolve the problem of load balance, and neighboring queries were grouped into the same thread to improve the reusability. The obtained predicted areas of moving objects can be reused by building shared memory over multi-core and multi-threading. The experiments conducted on large scale datasets demonstrated the effectiveness and efficiency of the proposed methods, and the proposed optimized parallel method reached about 37 speed-up compared with Rate.
%U http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2018.01.019