针对大量数据集设计一种高效算法以实现其与给定数据集超过预设阈值的杰卡德相似度检索

概要

假设你面对的是一个规模极为庞大的数据集 S = \{S_1, S_2, ..., S_n\}, 其中 n 值极其庞大。现在的问题是需要从中筛选出所有满足条件的小型数据集（ miniSet）。具体来说, 就是要找出所有与给定的大型数据集 S 的杰卡德相似度高于 0.5 的小型数据集（ miniSet）。常用的方法是为每个待比较的数据集计算其miniHash值, 然后计算目标数据集 A 对应的miniHash值, 最后逐一将该miniHash与已有数据集进行对比, 最终筛选出所有满足条件的小哈希匹配结果。

然而此类型查询的复杂度仍然是线性的亦即O(N)亦即其复杂度与集合数量呈线性增长趋势相关当集合数量足够大时此类型查询将会耗时较长

一种比线性更快的方法是基于局部敏感哈希的索引技术。因为采用了miniHash算法以及结合了局部敏感哈希(LSH)技术,从而可能导致一定程度的误判,即查询结果不符合预设条件,但仍会将一些不相关的数据返回出来。总体上,当两个对象之间具有较高相似度时,系统有较高的概率将其正确地识别并返回结果。

一个例子

    from datasketch import MinHash, MinHashLSH
    
    set1 = {'minhash', 'is', 'a', 'probabilistic