近邻检索问题是机器学习领域的一个基础问题,在信息检索、计算机视觉、数据挖掘等领域中都有着广泛的应用,例如以图搜图、人脸识别、k-means聚类等。近年来,随着互联网的快速发展,海量多媒体数据随之而来。从多媒体数据中抽取出来的特征一般维度较高且稠密。如何对此类特征进行高效检索,成为了当前学术界和工业界炙手可热的研究内容。目前,主流的近邻检索方法包括基于树的方法和基于哈希的方法这两种。其中,许多基于树的近邻检索方法对特征空间进行树结构的划分,其时间复杂度和空间复杂度都以维度d作为指数,所以当维度d变大时,这些方法的效率就受到了限制。相反地,基于哈希算法的近邻检索方法是通过哈希函数(具有相似性保持的特性,即在原始特征空间中相似的两个特征数据在映射到汉明空间后汉明距离也近)将一个d维的特征编码成一个c位(一般地,c《d)的二进制串,并通过汉明排序或者哈希表来进行检索。其中,汉明排序可以使用硬件(XOR)来进行加速,而基于哈希表的检索时间复杂度是O(1),与维度d无关。由于哈希算法具有高计算效率与维度不敏感的优势,其已经引起了众多学者和专家的研究兴趣。围绕基于哈希算法的海量多媒体数据近邻检索方法这一重要问题,本论文开展了以下工作：(1)面向高效检索的哈希函数学习：基于哈希的近邻检索方法是以哈希函数为基础的,一个好的哈希函数应该能使用尽可能短的哈希编码得到相对较高的准确率。基于随机投影的哈希算法不考虑数据的分布,需要较长位数的二进制串才能获得较好的近似性能。而基于学习的哈希算法从数据的分布中学习出投影向量,能在较短位数的二进制串下获得较好的性能。我们从衡量哈希函数的优劣标准出发,提出了一种基于学习的哈希算法一互补投影哈希算法。其是一个既保持数据的近邻性质(保证检索准确率),又考虑哈希桶均衡性(保证检索速度)的哈希函数学习方法。该算法的提出为基于哈希的高效检索奠定了基础。(2)跨媒体数据的哈希函数学习：海量多媒体(文本、图像、视频、音频等)数据的出现,使得面向跨媒体数据的哈希函数学习变得尤为重要。其要求学习出的哈希函数能够使不同媒体之间的关联体现在哈希编码中,即具有相同概念的多媒体数据在编码后应具有相同的二进制串。为此,我们提出了迭代多视角(Multi-View)哈希算法。其是一个同时保持同模态相似性和跨模态相似性的跨媒体哈希函数学习方法。其中,相似性的保持不止体现在对于相似数据要拥有相似的哈希编码,也体现在不相似数据要拥有不相似的哈希编码(独特性)。该算法的提出为跨媒体数据的哈希函数学习提供了一个良好的优化框架。(3)优化的基于哈希表结构的快速近邻检索：目前,相比基于树结构的近邻检索方法,基于哈希表的近邻检索方法未能展现出明显的优势。其主要原因在于目前的哈希算法为了达到高准确率和高召回率,通常需要扩展汉明半径来进行搜索,这使得检索时间大大增加。为了消除这个瓶颈,我们提出了迭代扩展哈希算法,其在线上使用一个辅助索引来对使用小汉明半径检索到的点做迭代扩展,以此来保证高准确率、高召回率和低检索时间。该算法从本质上提升了基于哈希表的近邻检索性能,为线上海量数据的实时搜索提供了有力保障。