位置敏感哈希函数数据结构的概率分析

陆可镜 王洪亚

摘要：对于高维空间的近邻查找问题，位置敏感哈希 （LSH）在查询代价和磁盘空间利用上有着出色表现。在传统分析模型下，LSH被视作随机算法，唯一不确定因素就是哈希函数的选择。研究中将这种模型下得到的碰撞概率称为基于哈希函数的碰撞概率。在本文中，我们用不同的分析模型对LSH作了理论分析。此工作的出发点有2个：（1）在现有的分析模型下，用户为了达到理论的效果，必须对每个查询点产生随机的数据结构，这在实际应用中是不现实的。（2）用户所关心的性能指标是随机查询点在一个数据结构上的期望碰撞概率。基于此，在本篇论文中推导了在汉明距离下，随机点对在任意单个哈希函数上的碰撞概率。研究将此模型下推导出的碰撞概率称为基于随机查询的碰撞概率。同时也一并证明了在汉明空间中，2种碰撞概率完全相同。

关键字：位置敏感哈希函数，碰撞率，算法的概率分析

中图分类号：TP391. 文献标识码：A

The probabilistic analysis of Locality Sensitive Hashing data structures

LU Kejing， WANG Hongya

（College of Computer and Technology， Donghua University， Shanghai 201620， China）

Abstract： Locality Sensitive Hashing （LSH） owns nice asymptotic performance bounds on query cost and space consumption for similarity search problem in high-dimensional spaces. In traditional analysis model， LSH is regarded as a randomized algorithm， where the only source of uncertainty is the random choice of hash functions. The research calls the probability of collision obtained under this model the hash-function-based collision probability. The paper conducts the theoretical analysis of LSH using a different model. The motivations are that （1） in the existing analysis model ， for the purpose of achieving the ideal performance ，one has to generate a random data structure for each query， which is obviously unaffordable in practice； （2） the performance metric that practitioners are interested in is the expected success probability of a random query over a single randomly generated data structure. To this end， the paper analytically derives the probability of collision that random pairs of data points collide over any single hash function for hamming distance. So the research calls the probability of collision derived following this model the random-input-based collision probability. Also， the paper proves that these two kinds of collision probabilities are exactly equivalent.

Key word： Locality Sensitive Hashing； the probability of collision； the probabilistic analysis of algorithms Algorithms

0 引言

作为在高维空间中质精效优的近邻搜索方法，位置敏感哈希（LSH）在许多领域都有着广泛的应用，包括网络聚类，计算机视觉，生物计算等等[1-2]。LSH的原理思想就是在不同的度量空间中设计哈希函数，使得距离近的点对的碰撞概率大于距离远的点对。目前针对多种不同的相似度，已经推出多种哈希函数族，诸如汉明距离， 距离（ ），Jaccard相似度，以及Arccos相似度等等。

研究可知，基于LSH的算法一般情况下都会具有稳定的错误概率，以及出色的实用性能[3-6]，但是全部LSH算法都将依据如下事实为依据：给定一个距离为r的点对，而这一点对在随机选取的哈希函数上的碰撞概率（记作 ）必将随着r的减小而降低。由此即将 称为基于哈希函数的碰撞概率。另据研究可知，对于点q的近似近邻查找，LSH算法可以保证其成功率至少为P。然而由现有的文献[4，7-9]表明， 的推导中可归为不确定的唯一因素就是哈希函数的选择。至此，可给出精确的表述为：给定一个查询点q，找到q近似最近邻的概率（随机选出足够多的LSH数据结构，数量记为n）将随着n的趋于无穷大而渐近达到于P。换句话说，如果要获得理论上的最佳效果，用户就必须对所有查询点生成大量的独立随机LSH数据结构，而这却显然不具备现实可行性。

在实际应用中，基于LSH的算法通常按照如下方式运行展开。首先独立随机地产生一组哈希函数，然后利用这组哈希函数，将数据点映射到对应的哈希桶中形成数据结构。对于每一个查询点，数据结构均将获得访问，而后将返回近似近邻。但是多数情况下，用户关注的却是随机查询点在单个数据结构上的碰撞概率期望[3，5-6，10]，也就是说与上文提及的传统释义解析出现了一定不同。在数据库应用中，哈希函数随机产生之后，数据结构随之确定，而数据点的分布对于这个固定的数据结构却在不断变化[11]。

综合上述研究可知，亟需对LSH数据结构演绎另一种概率分析。在这种分析模型下，当随机选出了哈希函数之后，LSH即可视作一个确定的数据结构。在本篇论文中，针对汉明空间，研究得到了随机点对在单个哈希函数上碰撞概率（记作 ），同时证明了该结果和传统模型下得到的 完全相同。