摘要: 在低维空间中R树的查询效率较高,而在高维空间中其性能急剧恶化,降维成为解决问题的关键。利用Hilbert曲线的降维特性,该文提出基于Hilbert曲线近似k-最近邻查询算法AKNN,分析近似k-最近邻的误差。实验结果表明算法在执行时间上优于线性扫描和基于R树最短优先查询算法,近似解的质量较好。
关键词:
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
中图分类号:
徐红波;郝忠孝;. 基于Hilbert曲线的近似k-最近邻查询算法[J]. 计算机工程, 2008, 34(12): 47-49.
XU Hong-bo; HAO Zhong-xiao;. Approximate k-nearest Neighbors Query Algorithm Based on Hilbert Curve[J]. Computer Engineering, 2008, 34(12): 47-49.