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

摘要

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