时间依赖路网中反向k近邻查询

摘要：

在现存的反向k近邻查询方案中,比较高效的研究大多集中在欧氏空间或者静态路网,对时间依赖路网中的反向k近邻查询的研究相对较少.已有算法在兴趣点密度稀疏或者k值较大时,查询效率较低.对此,提出了基于子网划分的反向k近邻查询算法mTD-SubG.首先,将整个路网划分为大小相同的子网,通过子网的边界节点向其他子网进行扩展,加快对路网中兴趣点的查找速度;其次,利用剪枝技术缩小路网的扩展范围;最后,利用已有时间依赖路网下的近邻查询算法,判定查找到的兴趣点是否为反向k近邻结果.实验中将mTD-SubG算法与已有算法mTD-Ea-ger进行对比,结果表明mTD-SubG算法的响应时间比mTD-Eager算法减少了85.05％,遍历节点个数比mTD-Eager算法减少了51.40％.

关键词：时间依赖、路网、反向、k近邻(RkNN)、mTD-SubG算法

所属期刊栏目：46

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金61502317;辽宁省自然科学基金201602559,201602568

在线出版日期：2019-03-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：232-237