1

据我了解，LSH 方法的主要功能之一是数据减少，甚至超出了底层哈希（通常是 minhashes）。我一直textreuse在 R 中使用这个包，我对它生成的数据的大小感到惊讶。textreuse是一个经过同行评审的ROpenSci包，所以我认为它可以正确地完成它的工作，但我的问题仍然存在。

假设我分别为我的 minhash 和 LSH 函数使用 256 个排列和 64 个波段 - 通常用于检测相对确定性(~98%) 相似性低至 50% 的实际值。

如果我使用 (256 perms) 散列一个随机文本文件TextReuseTextDocument并将其分配给trtd，我将拥有：

object.size(trtd$minhashes)
> 1072 bytes

现在让我们为这个对象（64 个波段）创建 LSH 存储桶并将其分配给l，我将拥有：

object.size(l$buckets)
> 6704 bytes

因此，LSH 存储桶中保留的哈希值是原始 minhashes 的六倍。我理解这是因为textreuse 使用 md5 摘要来创建存储桶哈希。

但这不是太浪费/矫枉过正，我不能改进它吗？我们的数据缩减技术最终膨胀到这种程度是否正常？根据原始哈希（类似于 perms = 256 和bands = 256）匹配文档然后使用阈值清除误报不是更有效吗？

请注意，我已经查看了诸如Mining of Massive Datasets之类的典型文本，但这个问题仍然是关于这个特定实现的。另请注意，这个问题不仅出于好奇，而且出于需要。当您拥有数百万或数十亿个哈希值时，这些差异就会变得很重要。

4

1 回答 1

1

包作者在这里。是的，使用比你需要的更多的哈希/带是浪费的。（但请记住，我们在这里讨论的是千字节，它可能比原始文档小得多。）

问题是，你需要什么？如果您只需要查找接近相同的匹配项（即 Jaccard 分数接近 1.0），那么您不需要特别敏感的搜索。但是，如果您需要可靠地检测仅共享部分重叠的潜在匹配项（即，Jaccard 分数接近 0），那么您需要更多的哈希/带。

由于您已阅读 MMD，因此您可以在那里查找方程式。但是包中有两个函数，记录在这里，可以帮助你计算你需要多少哈希/带。lsh_threshold()将计算将检测到的阈值 Jaccard 分数；whilelsh_probability()将告诉您检测到具有给定 Jaccard 分数的一对文档的可能性有多大。玩弄这两个函数，直到获得最适合您的搜索问题的哈希/带的数量。

于 2020-08-16T20:24:32.633 回答