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

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