近邻检索问题是机器学习与数据挖掘领域中的一个较为基础的研究问题,其相关的实际应用问题数不胜数,例如相似图像检索、基于近邻检索的图像分类问题等。过去的几年中,近邻检索方面的研究层出不穷,近邻检索问题的相关算法大致可以分为五类:线性扫描算法、树形索引算法、近邻图算法、哈希算法以及反向索引算法。线性扫描算法是解决近邻检索问题最基本的方法,即通过遍历每个数据进而找到查询数据的近邻。树形索引算法利用了树形数据结构划分空间,并建立索引结构来进行近邻检索。近邻图算法对数据库中的数据建立近邻图结构用于辅助近邻检索过程。哈希算法通过将数据由原始数据空间映射到Hamming空间,进而将近邻检索问题转化为Hamming编码相关的问题。反向索引算法通过聚类等方法建立反向索引结构用于提高近邻检索的效率。相关的近似近邻检索算法被提出[1],该方法提出了“桥向量”的概念,其概念和乘积量化[2]中聚类中心的概念比较类似。该算法基于桥向量和增强近邻图,提出了“需求驱动的实时提取”策略,在线检索阶段采用优先级搜索的方式进行近邻检索。近些年来,基于二进制编码和二进制视觉特征的大规模图像检索方面的研究在计算机视觉领域引起了广泛的关注。尽管二进制编码以及二进制特征可以提高计算效率,但针对大规模数据库通过线性扫描来检索近邻的方法依然计算开销巨大。在这篇文章中,我们将[1]中的近邻检索算法进行泛化,将其适用性扩展到Hamming空间。该扩展算法利用了Hamming空间中的K-平均聚类算法。我们提出的方法和现有的Hamming空间中的近邻检索算法(如多索引哈希算法[3]和FLANN算法[4])相比有较好的结果,在检索准确性、被访问数据数量以及平均检索时间三个方面均超越了现有的方法。