关键词: k-最近邻, 降维, Hilbert曲线, 近似算法

Abstract: R-Tree can achieve better performance in low-dimensional space, but its performance suffers greatly in high-dimensional space. So the reduction of the dimensionality is the key to the problem. Hilbert curve can fill d dimensional space linearly, divide it into equal-size grids and map points lying in grids into linear space. Using the quality of reducing dimensions of Hilbert curve, the paper presents an approximate k-nearest neighbors query algorithm, and analyzes the quality of the approximate k-nearest neighbors. According to the test, its running time is shorter than brute-force method and the algorithm based on R-tree, and the quality of approximate k-nearest neighbors is better.

Key words: k-nearest neighbors, reduction of dimensionality, Hilbert curve, approximate algorithm