假设我在 O(D*sqrt(D)) 时间内预处理了一百万个文档（使用 minhash 计算的签名），其中 D 是文档数。当我得到一个查询文档时，我必须在 O(sqrt(D)) 时间内返回一百万个预处理文档中的第一个，使得 jaccard 相似度大于或等于 0.8。
如果没有与查询文档相似的文档足以达到该分数，我必须返回相似度至少为 c * 0.8（其中 c<1）且概率至少为 1 - 1/e^2 的文档。我怎样才能找到这个 minhash 方案的 C 的最大值？
问问题
120 次
1 回答
0
您的复杂性/时间顺序听起来不正确。计算文档的最小哈希（签名）应该大致为 O(n)，其中 n 是特征的数量（例如，单词或 shingles）。
查找给定文档的所有相似文档（估计相似度高于给定阈值）应该大致为 O(log(n))，其中 n 是候选文档的数量。
具有（估计）最小 0.8 jaccard 相似度的文档将具有至少 80% 的 minhashes 匹配给定文档。您还没有为我们定义c和e，所以我不知道您的最低阈值是多少——我将把它留给你——但你可以轻松地一次性有效地实现这一点：
一个一个地处理所有基础文档的哈希值。对于每个哈希，在您的哈希字典中查找共享该哈希的所有其他文档。为找到的每个文档记录它共享多少哈希值。一旦其中一个计数达到哈希总数的 80%，您就找到了获胜文档并可以停止计算。但是，如果没有一个计数达到 0.8 的阈值，则继续到最后。然后，您可以选择具有最高计数的文档并决定它是否通过了您的最低阈值。
于 2019-07-11T01:53:20.527 回答