oPl*_*ess 5 sql search similarity nosql hamming-distance
我有一个过程,类似于生成感知哈希的tineye,这些是32位整数.
我打算将来存储在一个sql数据库(也许是一个nosql db)中
但是,我很难理解如何根据哈希的相似性检索记录.
有任何想法吗？
一种常见的方法(至少对我来说很常见)是将哈希位串分成几个块并在这些块上查询以获得完全匹配.这是一个"预过滤"步骤.然后,您可以对返回的结果执行按位汉明距离计算,该结果应该只是整个数据集的较小子集.这可以使用数据文件或SQL表来完成.
因此,简单来说:假设您在数据库中有一堆32位哈希值,并且您希望找到位于"查询"哈希值的4位汉明距离内的每个哈希值:
创建一个包含四列的表:每列包含32位哈希的8位(作为字符串或整数)切片,islice 1到4.
在qslice 1到4中以相同的方式切割查询哈希.
查询此表使得任何一个qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4.这为您4 - 1提供了查询哈希的3位()内的每个数据库哈希.
对于每个返回的哈希,使用查询哈希成对计算精确的汉明距离(从四个切片重建索引端哈希)
步骤4中的操作数应远小于整个表的完全成对汉明计算.
Moses Charikar在其"simhash"开创性论文和相应的Google 专利中首次描述了这种方法:
- 在撞击空间中逼近最近邻居的搜索
[...]
给定每个由d位组成的位向量,我们选择N = 0(n 1 /(1+))位的随机排列.对于每个随机排列σ,我们维持位向量的排序顺序Oσ,以σ排列的位的字典顺序.给定查询位向量q,我们通过执行以下操作找到近似最近邻居:
对于每个置换σ,我们对Oσ执行二进制搜索以定位最接近q的两个位向量(按照由σ置换的位获得的字典顺序).我们现在按照与q匹配的最长前缀的长度的顺序搜索每个排序的顺序Oσ检查二进制搜索返回的位置上方和下方的元素.
Monika Henziger在她的论文"寻找近似重复的网页:对算法进行大规模评估"中对此进行了扩展:
3.3算法C的结果
我们将每个页面的位串分成12个非重叠的4字节块,创建20个块,并计算出至少有一个共同点的所有页面的C相似度.这种方法可以保证找到差异达到11的所有页面对,即C-相似度373,但是对于较大的差异可能会遗漏一些.
Gurmeet Singh Manku,Arvind Jain和Anish Das Sarma的网页抓取检测近似重复文章中也对此进行了解释:
- HAMMING DISTANCE问题
定义:给定f位指纹和查询指纹F的集合,识别现有指纹与F中的最多k位是否不同.(在上述问题的批处理模式版本中,我们有一组查询指纹而不是单个查询指纹)
[...]
直觉:考虑一个2 df位真正随机指纹的排序表.只关注表中最重要的d位.在(a)存在相当多的2d比特组合的意义上,这些d比特数的列表相当于"几乎是计数器",并且(b)非常少的d比特组合被复制.另一方面,最低有效f-d位"几乎是随机的".
现在选择d使得| d - d | 是一个小整数.由于表是有序的,因此单个探针足以识别在最重要的位位置匹配F的所有指纹.从| d - d | 虽然很小,但预计此类比赛的数量也会很少.对于每个匹配的指纹,我们可以很容易地判断它是否与F在最多k个位位置不同(这些差异自然会限制在f-d最低有效位位置).
上述过程有助于我们找到在k个位位置上与F不同的现有指纹,所有这些指针都被限制在F的最不重要的f-d位中.这需要处理相当多的情况.为了涵盖所有情况,只需构建少量额外的排序表,如下一节中正式概述的那样.
PS:大多数这些优秀的大脑在某种程度上与谷歌有关,或者在某些时候与这些相关联,FWIW.