随着信息技术的飞速发展,互联网、大数据、多媒体、云计算等信息技术逐渐成为国家发展的关键领域。各个领域的信息迅速膨胀,对海量高维数据的有效管理和快速查询成为亟需解决的问题。传统的索引方式在高维情况下受到“维度灾难”的影响,其查询性能甚至会劣于线性查询。基于哈希方法的近似最近邻查询是解决上述问题的有效方式,除海量高维数据的快速查询外,哈希方法在模式识别、计算机视觉、机器学习、数据挖掘等大规模数据领域也具有深厚的研究意义。哈希方法在高维空间下具有低存储成本和查询高效的优势,使得很多情况下近似最近邻查询的结果等同于真实最近邻。根据哈希函数的生成方式,哈希方法分为数据无关哈希和数据相关哈希两大类。局部敏感哈希作为主流的数据无关方法,使用随机投影生成哈希函数,生成的过程独立于数据分布,高维数据经过哈希映射生成二进制编码进行快速高效的查询;数据相关哈希是一种基于数据分布特征的哈希方法,根据数据集中数据的属性特征设计更有效的哈希函数,使原始空间下的高维数据点经过哈希函数的映射得到更加紧凑的二进制编码。哈希方法的研究主要分为两方面:(1)设计哈希函数,获得紧凑、保距性强、高区分度的哈希编码;(2)构建高效的索引结构,设计查询算法。首先,本文分析了传统的索引方式在高维情况下存在的问题,归纳并总结数据无关和数据相关的哈希方法,分析数据相关哈希方法相比于数据无关哈希方法在近似最近邻查询下具有的优势。其次,本文研究基于p稳定分布等数据无关哈希的近似最近邻查询算法,针对局部敏感哈希在查询精度及索引结构上存在的问题,本文研究将聚类和传统的哈希相结合的方法,通过聚类保持数据对象之间的相似性,使用哈希方法将数据对象转换成哈希编码并建立倒排索引,检查包含查询点的桶和与查询点相邻的桶中的数据,实现快速高效的近似最近邻查询。接着,由于数据无关哈希方法的查询精度有限,本文引入近邻敏感哈希这一数据相关方法,进一步提升近似最近邻的查询精度。近邻敏感哈希与传统哈希方法相反,没有选择保留汉明空间中相似对象的相似度,而是最大化相似对象之间的汉明距离,用以更好的区分近邻数据对象,提高近似最近邻的查询精度。最后,针对近邻敏感哈希方法中存在的中心点的选择问题,本文提出基于超球体聚类初始化方法,该方法可以更好地描述数据集的整个分布特征,使得聚类中心尽可能多地覆盖整个数据集中的所有数据对象,更加适用于近邻敏感哈希方法,进一步提升近似最近邻查询的精度。本文的实验证明了基于超球体聚类初始化方法的近邻敏感哈希方法与其他方法相比在查询性能上的优势。