在计算机视觉、机器学习、多媒体数据挖掘等诸多领域,k近邻查询都是一个常见但又非常重要的问题。由于k近邻查询的执行效率往往会在很大程度上影响整个算法的执行效率,因此一个更高效的k近邻查询算法将使许多应用从中大大获益。目前,在低维空间中已经有很多高效的查询算法,但当处理高维数据时,维度灾难通常会导致这些算法的执行效率大大下降。为应对维度灾难带来的困境,很多算法提出了近似的查询方案,虽然这些算法可以满足大部分应用的需求,但仍有一些应用需要算法返回精确的k近邻查询结果。基于上述原因,本文提出了应用于海量高维数据的较高效的精确k近邻查询算法。本文算法主要分为数据预处理和k近邻查询两个阶段。在预处理阶段,算法通过正交变换和维度约减将向量间距离信息集中在少数几个维度之中,这使得在查询阶段算法只需处理少量维度即可完成大部分工作,从而有效地减少了在高维空间中查询带来的时间开销。在查询阶段,本文首先设计了一个近似的近邻查询算法,该算法独立运行时可以快速地得到较高质量的近邻查询结果,对于精确k近邻查询,则利用它返回一个阈值。接下来,算法不断加载数据的部分维度并利用近似的近邻查询算法返回的阈值对不可能成为k近邻的数据进行过滤。最后,算法只需从磁盘中加载少量数据即可完成精确的k近邻查询。实验表明,本文算法只通过小部分的维度就可以对数据实现有效的过滤并最终较高效地返回精确的k近邻查询结果。