周文桦，刘华文，李恩慧

浙江师范大学数学与计算机科学学院，浙江 金华 321001

1 引言

随着互联网技术的高速发展，需要处理的数据的量爆炸式增长。在海量数据中检索出所需的数据变得越来越困难。最近邻搜索（nearest neighbor search，NNS）[1]在海量数据中寻找与查询数据最相似的近邻数据，在信息检索、数据挖掘、机器视觉等领域起到了至关重要的作用。若数据集中含有N个数据，则检索准确近邻数据的时间复杂度为O(N)。当数据库规模非常庞大时，计算成本迅速增加，因此通常使用近似最近邻（approximate nearest neighbor search，ANN）搜索作为替代方案来解决最近邻搜索问题[2]。因为在很多应用领域中，无须找到最近邻的数据，只要找到相似的数据即可。在过去的研究中，基于树结构（如KD tree[3]、K-means tree[4]）的算法在近邻问题上得到广泛应用。其主要思想是对数据空间进行划分，从而提高检索速度。但基于树结构的算法仅适用于低维数据，当遇到高维数据时，其性能快速下降。基于哈希的搜索算法在数据规模与数据维度很大时仍具有高效的检索性能，且其时间、空间复杂度较低，因此该算法成为主流的检索算法之一[5-6]。

在基于哈希的检索方法中，局部敏感哈希（locality-sensitive hashing，LSH）算法[6-8]是有代表性的算法之一。LSH会随机生成一组哈希函数，每一个哈希函数生成一个对应二值哈希位，将由多个哈希位组成的编码称为哈希码。LSH将原空间中的数据点映射成哈希码，使得相似度越高的数据具有相同哈希码的概率越高，而相似度越低的数据具有相同哈希码的概率越低。……