海量高维数据查找与某个数据最相似的一个或者多个数据。与其它基于Tree的数据结构,诸如KD-Tree、SR-Tree相比,它较好地克服了Curse of Dimension,能够将KNN的时间复杂度缩减到sub-linear。LSH多被用于文本、多媒体(图像、音频)的相似性判断。
谷歌的文档去重算法。主要步骤:
比较的时候只需要计算两个hash的海明距离:两个二进制串对应的位有几个不一样,那么海明距离就是几,值越小越相似(异或)。
存储: 1、将一个64位的simhash code拆分成4个16位的二进制码。(图上红色的16位) 2、分别拿着4个16位二进制码查找当前对应位置上是否有元素。(放大后的16位) 3、对应位置没有元素,直接追加到链表上;对应位置有则直接追加到链表尾端。(图上的 S1 — SN)
查找: 1、将需要比较的simhash code拆分成4个16位的二进制码。 2、分别拿着4个16位二进制码每一个去查找simhash集合对应位置上是否有元素。 2、如果有元素,则把链表拿出来顺序查找比较,直到simhash小于一定大小的值,整个过程完成。
局部敏感hash可以比较相似度,普通的hash不可以