面向移动对象连续k近邻查询的双层索引结构

移动对象连续k近邻（CKNN）查询是指给定一个连续移动的对象集合，对于任意一个k近邻查询q，实时计算查询q的k近邻并在查询有效时间内对查询结果进行实时更新.现实生活中，交通出行、社交网络、电子商务等领域许多基于位置的应用服务都涉及移动对象连续k近邻查询这一基础问题.已有研究工作解决连续k近邻查询问题时，大多需要通过多次迭代确定一个包含k近邻的查询范围，而每次迭代需要根据移动对象的位置计算当前查询范围内移动对象的数量，整个迭代过程的计算代价占查询代价的很大部分.为此，提出了一种基于网络索引和混合高斯函数移动对象分布密度的双重索引结构（grid GMM index，GGI），并设计了移动对象连续k近邻增量查询算法（incremental search for continuous k nearest neighbors，IS-CKNN）.GGI索引结构的底层采用网格索引对海量移动对象进行维护，上层构建混合高斯模型模拟移动对象在二维空间中的分布.对于给定的k近邻查询q，IS-CKNN算法能够基于混合高斯模型直接确定一个包含q的k近邻的查询区域，减少了已有算法求解该区域的多次迭代过程；当移动对象和查询q位置发生变化时，进一步提出一种高效的增量查询策略，能够最大限度地利用已有查询结果减少当前查询的计算量.最后，在滴滴成都网约车数据集以及两个模拟数据集上进行大量实验，充分验证了算法的性能.

Double Layer Index for Continuous k-nearest Neighbor Queries on Moving Objects

For a given set of moving objects, continuous k-nearest neighbor (CKNN) query q over moving objects is to quickly identify and monitor the k-nearest objects as objects and the query point evolve. In real life, many location-based applications in transportation, social network, e-commerce, and other fields involve the basic problem of processing CKNN queries over moving objects. Most of existing work processing CKNN queries usually needs to determine a query range containing k-nearest neighbors through multiple iterations, while each iteration has to identify the number of objects in the current query range, and which dominates the query cost. In order to address this issue, this study proposes a dual index called GGI that consists of a grid index and a Gaussian mixture function to simulate the varying distribution of objects. The bottom layer of GGI employs a grid index to maintain moving objects, and the upper layer constructs Gaussian mixture model to simulate the distribution of moving objects in two-dimensional space. Based on GGI, an incremental search algorithm called IS-CKNN to process CKNN queries. This algorithm directly determines a query region that at least contains k neighbors of q based on Gaussian mixture model, which greatly reduces the number of iterations. When the objects and query point evolve, an efficient incremental query strategy is further proposed, which can maximize the use of existing query results and reduce the calculation of the current query. Finally, extensive experiments are carried out on one real dataset and two synthetic datasets to confirm the superiority of the proposed proposal.