大数据应用的发展给数据库管理带来了新的挑战和契机。其中,海量高维数据的快速检索作为一个非常关键的问题亟待解决。近年来,基于哈希技术的近似最近邻(ANN:Approximate Nearest Neighbor)查询方法,得到了广泛的关注。其优势在于存储效率高、检索速度快,同时保证在很多情况下近似最近邻等同于精确最近邻,在实际应用中已成为解决海量高维数据查询问题的关键技术之一。解决近似最近邻查询的哈希方法可分为两大类:其一,局部敏感哈希(LSH:Locality-Sensitive Hashing),通过一组随机投影将高维特征映射成哈希编码,生成哈希函数的过程不依赖于数据的分布特征;其二,数据依赖型哈希,根据数据分布学习哈希函数,得到更加紧凑的哈希编码。哈希方法的主要研究在于(1)设计高效的哈希函数,获得区分能力强、保距性高的哈希编码;(2)在哈希编码的基础上构建可行的索引结构,并设计高效的搜索算法。本文首先研究基于稳定分布的局部敏感哈希相关的近似最近邻查询算法,如LSB、C2LSH、SK-LSH和SRS。其中,LSB、SK-LSH和SRS算法分别使用不同的策略重新组织哈希编码,使其适应于低维的高效索引结构(如B树、B~+树、R树等),以降低查询过程中的I/O开销和时间开销。但这种哈希编码重组策略固定了哈希函数顺序,可能会导致算法拒绝某些近邻被选作候选点。C2LSH采用十分灵活的动态计数策略选择候选点,使得近邻更容易被选作候选点,但缺乏高效的外存索引结构。针对动态冲突计数策略无法进行有效外存索引的缺陷,本文提出将基于稳定分布的局部敏感哈希函数调整成Binary LSH函数,结合理论计算和实验结果探索Binary LSH函数在保证近似最近邻查询精度方面的优势。继而,将动态冲突计数问题转换成汉明查询问题,并建立一种新的索引结构,能够以较少的外存访问次数实现高精度的近似最近邻查询。为了进一步提升算法的查询精度,本文引入一种高效的数据依赖型哈希算法,近邻敏感哈希(NSH:Neighbor-Sentive Hashing),使得哈希编码对距离查询较近的数据对象具有更好的区分度。近邻敏感哈希的思路跳过了哈希方法普遍遵循的对所有数据对象进行保距的原则,产生直接面向提升近似最近邻查询效率的哈希函数。最后,将近邻敏感哈希与多索引哈希结合起来,以较高的精度实现高维数据的快速近似最近邻查询。本文的实验结果不仅证明了Binary LSH算法在查询性能上的优势,也证明了近邻敏感哈希所产生的哈希编码能够进一步提升近似最近邻查询结果的精确度。