Abstract: KNN (K-nearest neighbor) query is an important part of spatial data query research. When dealing with large scale location data, the current KNN query methods have the problem of updating and finding unbalance, which leads to low efficiency. Therefore, this paper proposes a KNN query method for mobile spatial data, which is based on Voronoi partition. Firstly, a two-level spatial index structure, VRI (VHash and VR index) is created, which contains two parts, VHash (Voronoi Hash) and VR (Voronoi and R) tree. The first level index structure VHash is the representation of direct neighbors in the Voronoi graph. The second layer index structure VR tree generates the corresponding R tree from the bottom up according to the areas of the minimum? rectangular region of each Voronoi cell. Secondly, based on the VRI structure, the KNN query algorithm and dynamic maintenance algorithm for the location data are proposed. In the KNN query method, the VR tree is used to locate and VHash is used to find the K nearest neighbor, which can effectively locate the query point and search fast. Thirdly, for the data updating situation, the index structure is updated timely. During that time, for the KNN query with dynamic location data, a maintaining method is proposed, which utilizes the record table. Finally, the experiments show that the proposed Voronoi partition spatial index structure and its corresponding KNN query algorithm have better performance and adaptability.

Key words: K-nearest neighbor (KNN) query, big data, Voronoi, R tree

摘要： 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树