LSH与MinHashing实现及浏览器指纹识别论文相关技术问题咨询

问题1解答 #

不需要全量重新运行整套LSH算法。你只需要对新增文档用之前生成的固定minhash哈希函数组计算签名，再用对应每个波段（band）的哈希函数把它落到各个波段对应的桶里，之后仅需要拿这份新增文档和它落在所有桶里的已有文档做比对即可，原有数据集的LSH结果可以完全复用，不需要重新计算。

问题2解答 #

必须每个波段使用独立的哈希函数，不能复用同一个。复用同一个哈希函数等于做重复的分桶操作，完全起不到提升相似对召回率的作用，属于浪费多个波段的算力。最终总桶数是波段数量 × 单个哈希函数的桶数，确实会远大于单个哈希函数的桶数n，这是LSH的标准实现逻辑。

问题3解答 #

是的，但不需要担心计算量过大的问题。LSH的核心作用就是通过分桶逻辑把绝大多数完全不相似的文档对提前排除，最终落到同一个桶里的文档对数量本来就很少，就算要遍历所有同桶文档对计算相似度，算力开销也会比全量两两比对低好几个数量级。额外注意：只要两个文档在任意一个波段的同一个桶里，就可以归为候选对，后续只需要计算一次相似度，不需要重复计算。

问题4解答 #

这篇论文的设计逻辑不需要对第二个不稳定特征的签名矩阵运行LSH。你第一次在稳定特征矩阵上运行LSH得到的候选对，本身就是稳定特征相似度足够高的配对，接下来仅需要拿这些候选对，计算它们在不稳定特征矩阵上的签名相似度即可，相当于用稳定特征先做粗筛，筛掉绝大多数不可能的配对之后，再用不稳定特征做二次校验，这么做的目的是同时兼顾指纹匹配的准确率和运行效率，不需要运行两次LSH。

问题5解答 #

最终步骤的输出确实是候选配对列表，你说的流程是对的。你可以把两个特征的签名拼接成完整签名，对候选对直接计算完整签名的Jaccard相似度，也可以分别计算稳定特征和不稳定特征的相似度之后按照论文给出的权重加权求和，再和你设定的阈值比对，筛选出来的就是最终的同一用户配对结果。

内容的提问来源于stack exchange，提问作者ianux22