0

据我所知，simhash 和 minhash 可用于此任务。但是所有这些算法都必须遍历整个文本数据库，这将是非常可怕的。是否有任何优化或其他算法可以加速任务？我想出的只是将文本数据库分成几个部分并并行获得成对相似度。我的文本数据库有大约 10 亿条记录。

4

1 回答 1

1

您必须遍历整个数据库一次（10 亿条记录）。

minhash 和 simhash 的好处是您不必单独比较每个可能的配对来查看它们是否相似（大约 500 万亿个可能配对）。

将数据库拆分为多个部分无济于事；你只会错过一些相似之处。仅当记录自然地分成您知道它们之间没有任何相似性的组时，拆分才有意义（例如，如果您有两种非常不同类型的记录彼此从不相似，则可以将它们分开处理以进行相似性检测） .

simhash 和 minhash 都可以从分布式计算中受益。生成散列可以随心所欲地分发。如果您愿意，可以使用 map/reduce 拆分哈希的存储，但对于 simhash，您可能不需要它，因为它足够紧凑，可以放入相当标准的机器的主内存中。

Simhash 只能找到非常相似的相似性对，并且它通常需要进行一些调整才能很好地工作。如果您想找到更松散的相似性，请使用一种更宽容的 minhash 变体。我建议结合 LSH 查看 superminhash。Superminhash 可以快速生成哈希，但可能更重要的是它可以实现更好的精度，因此需要存储的哈希更少。LSH 将散列分组为带，这样您就不会比较单个散列；您一次比较整个乐队。这两种技术都意味着需要更少的查询来找到单独的共享哈希（或带，在后一种情况下），特别是 LSH 意味着需要为每个单独的查询处理更少的结果。这应该会给你很大的加速。

于 2017-10-15T23:15:40.810 回答