基于Hilbert曲线的近似k-最近邻查询算法  

Approximate k-nearest Neighbors Query Algorithm Based on Hilbert Curve

作　　者：徐红波[1] 郝忠孝[1] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080

出　　处：《计算机工程》2008年第12期47-49,共3页Computer Engineering

基　　金：黑龙江省自然科学基金资助项目(F200601)

摘　　要：在低维空间中R树的查询效率较高,而在高维空间中其性能急剧恶化,降维成为解决问题的关键。利用Hilbert曲线的降维特性,该文提出基于Hilbert曲线近似k-最近邻查询算法AKNN,分析近似k-最近邻的误差。实验结果表明算法在执行时间上优于线性扫描和基于R树最短优先查询算法,近似解的质量较好。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 filld 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.

关 键 词：K-最近邻 降维 HILBERT曲线 近似算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]