陸可鏡 王洪亞

摘要：對于高維空間的近鄰查找問題，位置敏感哈希 （LSH）在查詢代價和磁盤空間利用上有著出色表現(xiàn)。在傳統(tǒng)分析模型下，LSH被視作隨機(jī)算法，唯一不確定因素就是哈希函數(shù)的選擇。研究中將這種模型下得到的碰撞概率稱為基于哈希函數(shù)的碰撞概率。在本文中，我們用不同的分析模型對LSH作了理論分析。此工作的出發(fā)點有2個：（1）在現(xiàn)有的分析模型下，用戶為了達(dá)到理論的效果，必須對每個查詢點產(chǎn)生隨機(jī)的數(shù)據(jù)結(jié)構(gòu)，這在實際應(yīng)用中是不現(xiàn)實的。（2）用戶所關(guān)心的性能指標(biāo)是隨機(jī)查詢點在一個數(shù)據(jù)結(jié)構(gòu)上的期望碰撞概率?；诖?，在本篇論文中推導(dǎo)了在漢明距離下，隨機(jī)點對在任意單個哈希函數(shù)上的碰撞概率。研究將此模型下推導(dǎo)出的碰撞概率稱為基于隨機(jī)查詢的碰撞概率。同時也一并證明了在漢明空間中，2種碰撞概率完全相同。

關(guān)鍵字：位置敏感哈希函數(shù)，碰撞率，算法的概率分析

中圖分類號：TP391. 文獻(xiàn)標(biāo)識碼：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 引言

作為在高維空間中質(zhì)精效優(yōu)的近鄰搜索方法，位置敏感哈希（LSH）在許多領(lǐng)域都有著廣泛的應(yīng)用，包括網(wǎng)絡(luò)聚類，計算機(jī)視覺，生物計算等等[1-2]。LSH的原理思想就是在不同的度量空間中設(shè)計哈希函數(shù)，使得距離近的點對的碰撞概率大于距離遠(yuǎn)的點對。目前針對多種不同的相似度，已經(jīng)推出多種哈希函數(shù)族，諸如漢明距離， 距離（ ），Jaccard相似度，以及Arccos相似度等等。

研究可知，基于LSH的算法一般情況下都會具有穩(wěn)定的錯誤概率，以及出色的實用性能[3-6]，但是全部LSH算法都將依據(jù)如下事實為依據(jù)：給定一個距離為r的點對，而這一點對在隨機(jī)選取的哈希函數(shù)上的碰撞概率（記作 ）必將隨著r的減小而降低。由此即將 稱為基于哈希函數(shù)的碰撞概率。另據(jù)研究可知，對于點q的近似近鄰查找，LSH算法可以保證其成功率至少為P。然而由現(xiàn)有的文獻(xiàn)[4，7-9]表明， 的推導(dǎo)中可歸為不確定的唯一因素就是哈希函數(shù)的選擇。至此，可給出精確的表述為：給定一個查詢點q，找到q近似最近鄰的概率（隨機(jī)選出足夠多的LSH數(shù)據(jù)結(jié)構(gòu)，數(shù)量記為n）將隨著n的趨于無窮大而漸近達(dá)到于P。換句話說，如果要獲得理論上的最佳效果，用戶就必須對所有查詢點生成大量的獨立隨機(jī)LSH數(shù)據(jù)結(jié)構(gòu)，而這卻顯然不具備現(xiàn)實可行性。

在實際應(yīng)用中，基于LSH的算法通常按照如下方式運(yùn)行展開。首先獨立隨機(jī)地產(chǎn)生一組哈希函數(shù)，然后利用這組哈希函數(shù)，將數(shù)據(jù)點映射到對應(yīng)的哈希桶中形成數(shù)據(jù)結(jié)構(gòu)。對于每一個查詢點，數(shù)據(jù)結(jié)構(gòu)均將獲得訪問，而后將返回近似近鄰。但是多數(shù)情況下，用戶關(guān)注的卻是隨機(jī)查詢點在單個數(shù)據(jù)結(jié)構(gòu)上的碰撞概率期望[3，5-6，10]，也就是說與上文提及的傳統(tǒng)釋義解析出現(xiàn)了一定不同。在數(shù)據(jù)庫應(yīng)用中，哈希函數(shù)隨機(jī)產(chǎn)生之后，數(shù)據(jù)結(jié)構(gòu)隨之確定，而數(shù)據(jù)點的分布對于這個固定的數(shù)據(jù)結(jié)構(gòu)卻在不斷變化[11]。

綜合上述研究可知，亟需對LSH數(shù)據(jù)結(jié)構(gòu)演繹另一種概率分析。在這種分析模型下，當(dāng)隨機(jī)選出了哈希函數(shù)之后，LSH即可視作一個確定的數(shù)據(jù)結(jié)構(gòu)。在本篇論文中，針對漢明空間，研究得到了隨機(jī)點對在單個哈希函數(shù)上碰撞概率（記作 ），同時證明了該結(jié)果和傳統(tǒng)模型下得到的 完全相同。