随着以互联网为代表的计算机技术的高速发展,世界开始步入大数据时代。大数据在给人们带来丰富的资讯知识的同时也对许多的传统领域产生了挑战,相似性查询就是其中之一。相似性查询即查询与给定对象之间的相似性,其中近似最近邻查询就是相似性查询的一个重要分支。近似最近邻查询牺牲少量查询精度换取更快的查询速度,在图像检索等领域有广泛的应用。查询过程中,由于“维度灾难”使得基于划分的查询方法无法有效解决高维数据的近似查询问题,为此有必要研究近似最近邻相关算法。在近似最近邻算法研究过程中,局部敏感哈希算法(Locality Sensitive Hashing)受到了越来越多的人的关注。局部敏感哈希算法将对象进行哈希,使得相似性更高的数据哈希到同一个哈希桶的概率更高。查询过程中仅对具有相同哈希的数据进行精确的相似性比较,这样就过滤了大部分相似性较低的数据,从而能够快速得到查询结果。精确欧氏局部敏感哈希算法为了提高算法的召回率,使用多张哈希表。但是每个哈希表的哈希桶中的数据会受到原始数据分布的影响,导致哈希桶中的数据数目十分不均衡,哈希桶中的数据不均衡性导致检索效率降低。针对近似最近邻算法研究中出现的问题,本文的主要工作如下:(一)研究了一种基于平衡索引的局部敏感哈希(BILSH)。首先采用稀疏子空间聚类方法,对具有聚集现象的数据实行聚类。然后在聚类后的每个类中使用局部敏感哈希,这使得哈希桶中数据分布更加平衡。提出了一种Depth优化的方法。对BILSH的查询过程中需要计算高维数据之间距离的步骤进行优化,降低了近似最近邻检索中无效的距离计算数目,进一步加快了检索时的查询速度。(二)提出了一种从高维数据中检索近似最近邻的基于编码的哈希方法——局部保留的熵量化哈希。首先,构建邻接图并最小化近邻在低维空间的距离使得投影后的矩阵保持高维的近邻关系。最后通过熵量化降低投影后矩阵在量化过程中的损失,其中量化过程中使用混合距离度量方式。(三)提出了高维数据下的近似最近邻检索模型,并在公开数据集Caltech和Cifar上对模型算法进行了实验。实验表明,基于平衡索引的局部敏感哈希检索效率有所提高,同时局部保留的熵量化哈希与其他哈希算法相比正确率和召回率也有一定的提升。验证了所提模型的算法可以有效处理近似最近邻检索问题。