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

《位置敏感哈希函数数据结构的概率分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、哈希函数上的碰撞概率。研究将此模型下推导出的碰撞概率称为基于随机查询的碰撞概率。同时也一并证明了在汉明空间中，2种碰撞概率完全相同。　　关键字：位置敏感哈希函数，碰撞率，算法的概率分析　　中图分类号：TP391.文献标识码：A　　TheprobabilisticanalysisofLocalitySensitiveHashingdatastructures　　LUKejing，WANGHongya　　（CollegeofComputerandTechnology，DonghuaUniversity，Shanghai201620，China）　　Abstract：Localit

3、ySensitiveHashing（LSH）ownsnice4asymptoticperformanceboundsonquerycostandspaceconsumptionforsimilaritysearchprobleminhigh-dimensionalspaces.Intraditionalanalysismodel，LSHisregardedasarandomizedalgorithm，wheretheonlysourceofuncertaintyistherandomchoiceofhashfunctions.Theresearchcallstheprobab

4、ilityofcollisionobtainedunderthismodelthehash-function-basedcollisionprobability.ThepaperconductsthetheoreticalanalysisofLSHusingadifferentmodel.Themotivationsarethat（1）intheexistinganalysismodel，forthepurposeofachievingtheidealperformance，onehastogeneratearandomdatastructureforeachquery，wh

5、ichisobviouslyunaffordableinpractice；（2）theperformancemetricthatpractitionersareinterestedinistheexpectedsuccessprobabilityofarandomqueryoverasinglerandomlygenerateddatastructure.Tothisend，thepaperanalyticallyderivestheprobabilityofcollisionthatrandompairsofdatapointscollideoveranysinglehas

6、hfunctionforhammingdistance.Sotheresearchcallstheprobabilityofcollisionderivedfollowingthismodeltherandom-input-basedcollisionprobability.Also，thepaperprovesthatthesetwokindsofcollisionprobabilitiesareexactlyequivalent.　　Keyword：LocalitySensitiveHashing；theprobabilityofcollision；theprobabil

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