位置敏感哈希函數數據結構的概率分析

陸可鏡 王洪亞

摘要：對于高維空間的近鄰查找問題，位置敏感哈希 （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即可視作一個確定的數據結構。在本篇論文中，針對漢明空間，研究得到了隨機點對在單個哈希函數上碰撞概率（記作 ），同時證明了該結果和傳統模型下得到的 完全相同。