最近邻查找是计算机视觉和机器学习领域中的一个重要的基础性问题。近年来,基于哈希的算法在处理最近邻查找的问题上,引起了很大的关注。其基本思想是用紧凑的二值码表示高维数据点,并且用二值码之间的相似性近似数据点之间在原空间的相似性。二值码表示具有存储消耗低和计算速度快的优点,故而哈希的方法在大规模数据环境下具有很广的应用前景。尽管哈希方法有存储和计算上的优势,但是依据二值码排序的结果依然存在着一定的误差。这样的误差目前并没有得到很好地解决,故而本论文主要从多个方面提升哈希方法在最近邻查找中的准确性。一般而言,基于哈希的最近邻查找的方法包括两个阶段。第一个是哈希映射,用于将数据点映射为二值码；第二个是针对二值码设计近似距离从而进行排序。为了提升基于哈希的最近邻查找的准确性,本文主要从这两个方面研究如何获得更优质的二值码和更准确的度量距离。本文主要研究内容和创新成果如下：1.提出序列保持哈希算法。该算法通过最大化原空间排序结果和汉明空间排序结果之间的一致性学习哈希映射,从而提升基于汉明距离的哈希映射在最近邻查找的准确性。数据点根据与查询点之间的汉明距离分成不同的类别,从而可以将排序问题建模成分类问题。哈希函数通过最小化在所有训练数据点上面的分类损失而得。该方法直接最大化最近邻查找最关注的排序的一致性,大量的与已有基于汉明距离的哈希方法的对比实验结果表明,序列保持哈希可以在相同的查找时间内取得更高的排序准确率。2.提出优化的笛卡尔K均值算法。该算法用于提升基于空间量化的哈希映射在最近邻查找的准确率。传统的方法中,码本是多个子码本的笛卡尔乘积;而本文提出的方法采用多个这样的码本联合对数据进行编码。每一个数据点用多个码字的和近似,而每一个码字来自不同的码本。码本通过最小化失真误差优化而得。这样简单有效的策略不仅在实验中同时也在理论上保证了更低的失真误差,从而提升了排序的准确性。3.提出二值码距离优化的算法。该算法用于在二值码给定的情况下,通过距离优化的方式提升最近邻查找的准确率。具体而言,由于二值码取值范围的有限性,本文通过一个非参数的查询表存储查询点到每一个二值码之间的距离。为了解决可能带来的存储空间大的问题,本文将二值码分成多个子码,每一个子码生成一个与查询相关的较小的距离查询表,近似距离定义为多个子表对应的表项的和。查询表中的元素值通过最小化近似距离和原真实距离的误差而得。该思想成功应用到对称的二值码之间的距离以及非对称的查询点与数据库二值码之间的距离中。由于理论上保证了更准确的近似距离,大量的实验表明了对距离的优化可以很大幅度提升基于哈希的最近邻查找的准确率。综上,本文从如何获得二值码以及如何设计针对二值码距离两个方面,提出三个新颖算法,用于提升基于哈希的最近邻查找的准确性。理论证明和大量实验结果表明了所提出方法相对于已有方法的优越性。