软件学报

作者：韩士元，何清，于自强，童向荣，郑渤龙

单位：韩士元，济南大学 信息科学与工程学院, 山东 济南 25002211,何清，济南大学 信息科学与工程学院, 山东 济南 25002202,于自强，烟台大学 计算机与控制工程学院, 山东 烟台 26400503,童向荣，烟台大学 计算机与控制工程学院, 山东 烟台 26400504,郑渤龙，华中科技大学 计算机科学与技术学院, 湖北 武汉 43007405

关键词：移动对象;连续k近邻查询 (CKNN);增量查询算法

基金：国家自然科学基金（62172351，62072392，61903156，61873324）；山东省自然科学基金重点项目（ZR2020KF006）

移动对象连续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位置发生变化时，进一步提出一种高效的增量查询策略，能够最大限度地利用已有查询结果减少当前查询的计算量.最后，在滴滴成都网约车数据集以及两个模拟数据集上进行大量实验，充分验证了算法的性能.

来源：2023年第6期

《软件学报》期刊编辑部

查看软件学报杂志2023年第6期