最近邻搜索是机器学习、计算机视觉和信息检索里一个重要的基础性问题。然而,在大规模高维数据环境下,给定查询点,找到其精确的最近邻需要大量的计算及存储空间。近似最近邻搜索算法由于其存储空间少、查找效率高等优点引起了人们的广泛关注。而如何快速、高效、准确地进行近似最近邻搜索是目前学术研究的一个热点和难点。一般来说,近似最近邻搜索的算法在尽可能保证其准确性的情况下主要从两个方面提高搜索速度。第一个是利用特殊的数据结构来减少查询点与数据点的比较次数;第二个是利用紧凑码来加速计算查询点与数据点之间的距离,比如通过哈希算法或量化算法将数据点映射为紧凑码。本文主要从第二个方面——基于量化的近似最近邻搜索算法——研究如何获得更优质的紧凑码来提高查找准确率和查找效率。本文主要研究内容和创新成果如下:1.针对无监督的近似最近邻搜索,本文提出一种组合量化方法。其主要思想是用若干个子中心点之和作为重构点来近似数据点,其中每个子中心点来自不同的子字典,数据点用这些子中心点在各自子字典中的索引值来表示。同时,我们引入近似正交约束条件,使得计算查询点与重构点的距离可以用查询点和这几个子中心点的距离之和来代替进而加速距离计算。与已有的量化方法的对比实验结果表明,近似正交的组合量化可以获得更高的查找准确率。2.本文提出一种稀疏组合量化算法,用以减少组合量化中创建查阅表所需的时间。大规模数据的近似最近邻搜索通常结合倒排表进一步加速搜索。而组合量化在对倒排表返回的数据点进行排序的时候,创建查阅表所需的时间变得不可忽视。针对这一问题,本文提出的稀疏组合量化方法,引入了一个稀疏条件,使得重构字典里的每一个子中心点是一个稀疏向量。其好处是,当创建查阅表需要计算查询点与子中心点的欧氏距离的时候,由于子中心点是一个稀疏向量,可以加速距离计算。在大规模数据集上的近似最近邻搜索表明,稀疏组合量化相比较于组合量化,可以获得更快的查找速度。3.本文提出基于量化的近似最近邻搜索算法用于跨模态最近邻搜索领域中。所谓跨模态最近邻搜索,指的是查询点和数据点来自不同的数据模态,例如用图像查询点去搜索相似的文本数据点,或用文本查询点去搜索相似的图像数据点。本文提出的算法只假设一幅图像和一段文本是一一对应的,而不需要已知图像和文本的类别。该算法首先将来自不同模态的一对数据映射到同一空间中,之后在这个映射后的空间对不同模态的数据通过组合量化进行近似,同时使来自不同模态的一对数据的近似表示尽可能相同。大量的实验比较表明,本文提出的算法在跨模近似态最近邻搜索中可以获得更高的查找准确率。4.针对有监督近似最近邻搜索,本文提出了一种新的量化方法。不同于无监督近似最近邻搜索,量化算法直接在数据库上进行量化,本文提出的算法是使数据点首先通过一个线性变换,之后在线性变换后的数据点上进行组合量化。其优化的目的不仅要使得量化后的近似表达能准确地代表线性变换后的数据点,同时也使得数据点在线性变换后具有类别可分离性,即相同类别的数据点在线性变换后距离很近,不同类别的数据点在线性变换后的空间内相距很远。与现有的有监督近似最近邻搜索算法的实验比较表明,本文提出的算法可以获得更高的查找准确率。综上,本文在无监督的近似最近邻搜索,跨模态的近似最近邻搜索,以及有监督的近似最近邻搜索这三个领域提出了四个新颖的算法,用于提高近似最近邻搜索的查找准确率以及查找效率。大量实验结果表明了本文提出的方法的查找结果好于已有方法的查找结果。