Abstract: K nearest neighbor query algorithm is one of the commonly used algorithms in massive spatial data query. First, it construct an index of largescale spatial data by Kd-Tree, and hierarchical division of the search space. Then, it used the k nearest neighbor query to ensure the efficiency of the search. However, the traditional Kd-Tree construction has two drawbacks: the use of test data points are required for each k nearest neighbor query back to the root, thus affecting the efficiency of the query; Kd-Tree uses the splitlevel domain for the space division of space into cubes (twodimensional data are rectangular), extra space appears in polygonal space at the intersection of judgment, making the comparison of data unnecessary,   thus affecting the efficiency of the query. Regarding these two shortcomings, it proposed the corresponding improved algorithmRB algorithm. Experimental results show that the algorithm has a higher query efficiency than the traditional KD algorithm.There are two main contribution from this paper: (1) This paper construct a quickly create Kd-Tree indexes to support queries KNN akgorithm to classify largescale data. (2) RB algorithm is proposed to improve the traditional Kd-Tree index construction method,and improving query efficiency for KNN algorithm.

Key words: k nearest neighbor query, Kd-Tree, spatial data, polygon space, hierarchical division