互联网的发展带来了数据的爆炸式增长。如何在大规模数据中做基于相似度的计算和搜索是一个有广阔应用背景且具有挑战性的基础问题,而具有局部敏感性质的哈希方法则是一个有力的工具。局部敏感哈希方法将数据压缩成紧凑的哈希码,通过计算哈希码间的某种简单距离(比如海明距离)即可快速估计出原始数据对间的相似度或者距离。这种保相似度的哈希码作为对数据的一种压缩表示,可以作为各种基于相似度的机器学习和数据挖掘算法的输入,从而实现了存储上的压缩和计算上的加速。另一方面,也可以建立哈希表实现快速的相似搜索。目前有各种局部敏感哈希方法针对不同的数据类型和相似度定义。现有的局部敏感哈希方法的估计方差较大,需要计算较多的哈希函数以保证一定的估计精度,从而带来了较大的计算和存储开销。本文首先针对具有简单结构的数据——向量和集合,研究了相应的局部敏感哈希方法。相对于局部敏感哈希使用独立采样的哈希函数,本文提出使用结构化采样的哈希函数,以降低估计的方差或者哈希时间。另一方面,之前的研究大多针对简单结构的数据,而很多实际数据并不能用简单结构来表示,比如子空间、图等。本文针对具有子空间结构的数据提出了一种局部敏感哈希方法,并推广到了三阶张量类型的数据上。本文的创新点包括:1、针对向量类型的数据,本文提出了超比特局部敏感哈希,使用结构化采样的哈希函数——分组正交化的随机投影向量构成的哈希函数,作为对符号随机投影哈希的改进。本文证明了超比特局部敏感哈希可以提供对向量间角度的无偏估计,并在理论上研究了由分组正交随机投影向量构成的哈希函数所带来的方差的降低。实验验证了理论结果;2、对于集合类型的数据,本文提出了最小最大值哈希方法,采用结构化的哈希函数——最小值函数和最大值函数,作为对最小值哈希的改进。本文证明了最小最大值哈希在保证无偏估计的基础上,将哈希时间降低到最小值哈希的一半,并且方差也略有降低;实验验证了理论结果;3、本文针对子空间和三阶张量类型的数据,提出了子空间保角哈希,并进行了理论分析和实验验证。本文还提出了快速符号随机投影方法和双线性随机投影方法用于加速子空间保角哈希的计算。