CAJ | 학술논문

k近邻查询算法是查询大规模空间数据的常用算法之一，使用Kd-Tree先构建大规模空间数据的索引，然后对搜索空间进行层次划分，再进行k近邻查询，能保证搜索的效率。但是，传统的Kd-Tree构建有两个缺点：使用测试数据点进行k近邻查询每次都需要回溯到根节点，影响了查询的效率；Kd-Tree使用split域对空间进行层次划分，空间划分为立方体（二维数据表现为矩形），多边形空间在相交判断时会出现没必要进行数据距离比较的多余空间，这样会影响查询的效率。针对这两个缺点，本文提出了相应的改进算法---RB算法。实验结果证明，该算法比传统的KD算法拥有更高的查询效率。本文的主要贡献有两点：（1）构建一种快速创建Kd-Tree索引来支持KNN算法进行大规模数据的分类查询操作。（2）改进传统的Kd-Tree索引构建方法，提出新的改进算法RB算法，提高KNN算法查询的效率。
k근린사순산법시사순대규모공간수거적상용산법지일，사용Kd-Tree선구건대규모공간수거적색인，연후대수색공간진행층차화분，재진행k근린사순，능보증수색적효솔。단시，전통적Kd-Tree구건유량개결점：사용측시수거점진행k근린사순매차도수요회소도근절점，영향료사순적효솔；Kd-Tree사용split역대공간진행층차화분，공간화분위립방체（이유수거표현위구형），다변형공간재상교판단시회출현몰필요진행수거거리비교적다여공간，저양회영향사순적효솔。침대저량개결점，본문제출료상응적개진산법---RB산법。실험결과증명，해산법비전통적KD산법옹유경고적사순효솔。본문적주요공헌유량점：（1）구건일충쾌속창건Kd-Tree색인래지지KNN산법진행대규모수거적분류사순조작。（2）개진전통적Kd-Tree색인구건방법，제출신적개진산법RB산법，제고KNN산법사순적효솔。
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 u-ses the split-level domain for the space division of space into cubes ( two-dimensional data are rectangu-lar) , 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 pro-posed 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 con-struction method ,and improving query efficiency for KNN algorithm .