位置敏感哈希函數(shù)數(shù)據(jù)結(jié)構(gòu)的概率分析

陸可鏡 王洪亞

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

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

中圖分類號(hào)：TP391. 文獻(xiàn)標(biāo)識(shí)碼：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ì)算機(jī)視覺，生物計(jì)算等等[1-2]。LSH的原理思想就是在不同的度量空間中設(shè)計(jì)哈希函數(shù)，使得距離近的點(diǎn)對(duì)的碰撞概率大于距離遠(yuǎn)的點(diǎn)對(duì)。目前針對(duì)多種不同的相似度，已經(jīng)推出多種哈希函數(shù)族，諸如漢明距離， 距離（ ），Jaccard相似度，以及Arccos相似度等等。

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

在實(shí)際應(yīng)用中，基于LSH的算法通常按照如下方式運(yùn)行展開。首先獨(dú)立隨機(jī)地產(chǎn)生一組哈希函數(shù)，然后利用這組哈希函數(shù)，將數(shù)據(jù)點(diǎn)映射到對(duì)應(yīng)的哈希桶中形成數(shù)據(jù)結(jié)構(gòu)。對(duì)于每一個(gè)查詢點(diǎn)，數(shù)據(jù)結(jié)構(gòu)均將獲得訪問，而后將返回近似近鄰。但是多數(shù)情況下，用戶關(guān)注的卻是隨機(jī)查詢點(diǎn)在單個(gè)數(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ù)點(diǎn)的分布對(duì)于這個(gè)固定的數(shù)據(jù)結(jié)構(gòu)卻在不斷變化[11]。

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