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

摘要

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