据我所知,simhash 和 minhash 可用于此任务。但是所有这些算法都必须遍历整个文本数据库,这将是非常可怕的。是否有任何优化或其他算法可以加速任务?我想出的只是将文本数据库分成几个部分并并行获得成对相似度。我的文本数据库有大约 10 亿条记录。
1 回答
您必须遍历整个数据库一次(10 亿条记录)。
minhash 和 simhash 的好处是您不必单独比较每个可能的配对来查看它们是否相似(大约 500 万亿个可能配对)。
将数据库拆分为多个部分无济于事;你只会错过一些相似之处。仅当记录自然地分成您知道它们之间没有任何相似性的组时,拆分才有意义(例如,如果您有两种非常不同类型的记录彼此从不相似,则可以将它们分开处理以进行相似性检测) .
simhash 和 minhash 都可以从分布式计算中受益。生成散列可以随心所欲地分发。如果您愿意,可以使用 map/reduce 拆分哈希的存储,但对于 simhash,您可能不需要它,因为它足够紧凑,可以放入相当标准的机器的主内存中。
Simhash 只能找到非常相似的相似性对,并且它通常需要进行一些调整才能很好地工作。如果您想找到更松散的相似性,请使用一种更宽容的 minhash 变体。我建议结合 LSH 查看 superminhash。Superminhash 可以快速生成哈希,但可能更重要的是它可以实现更好的精度,因此需要存储的哈希更少。LSH 将散列分组为带,这样您就不会比较单个散列;您一次比较整个乐队。这两种技术都意味着需要更少的查询来找到单独的共享哈希(或带,在后一种情况下),特别是 LSH 意味着需要为每个单独的查询处理更少的结果。这应该会给你很大的加速。