计算机科学与探索

作者：宋宝燕，孟彦伟，丁琳琳

单位：辽宁大学 信息学院，沈阳 110036

关键词：K最近邻（KNN）查询,海量数据,Voronoi,R树

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

来源：2019年第12期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2019年第12期