基于Voronoi划分的位置数据KNN查询处理方法

摘要：

K最近邻(KNN)查询是空间数据查询研究的重要内容.目前的KNN查询方法在处理大规模的位置数据时,存在着更新和查找失衡的问题,导致查询效率较低.因此,提出基于Voronoi划分的位置数据KNN查询处理方法.首先,创建了一个二级空间索引结构——VRI,包含VHash和VR树两部分.一级索引结构VHash表示Voronoi图的直邻;二级索引结构VR树,按照各Voronoi单元所在的最小矩形区域的重叠面积,自下而上地生成对应的R树.其次,基于VRI索引结构提出了位置数据的KNN查询算法及动态维护算法,在KNN查询方法中,采用VR树进行定位,VHash查找K近邻,能够有效地对查询点定位,查找速度快.再次,针对数据更新的情况,索引结构也能够及时更新,在更新的时间段内,对于位置数据随时间变化的KNN查询,提出了利用记录表进行有效查询的方法.最后,实验表明,提出的基于Voronoi划分的空间索引结构和其对应的KNN查询算法均具有较好的性能和适应性.

关键词：K最近邻(KNN)查询、海量数据、Voronoi、R树

所属期刊栏目：13

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

资助基金：The National Key Research and Development Program of China under Grant No.2016YFC0801406;the National Natural Science Foundation of China under Grant Nos.61472169,61502215, 61702381, 51704138;the Young and Middle Age Science and Technology Innovation Talents Support Program of Shenyang under Grant No.RC180244;the Young Research Foundation of Liaoning University under Grant No.LDQN201438;the Natural Science Foundation of Hubei Province under Grant No.2017CFB196;the Scientific Research Foundation of Wuhan University of Science and Technology under Grant No.2017xz015;the Science Research Normal Fund of Liaoning Provincial Education Department under Grant No.LJC201913

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

页数：共14页

页码：2015-2028