bigdata - 使用最小哈希估计集合相似度的最佳排列数

Question

假设我必须估计文档 A 和 B 之间的 jaccard 相似性，并且我使用这些集合/文档的并集的 k 个随机排列来确定文档的签名。

我应该如何设置我的 k 值？因为将它设置为一个非常高的值会显着增加计算时间，所以可以给我一个好的 jaccard 指数估计值的 k 的最小值是多少？

给定容错 e>0 和 delta，我如何确定 k 的最小值，使得 jaccard 索引介于 (1-e)jaccard_estimate 和 (1+e)jaccard_estimate 之间，概率大于或等于 (1-delta) ?

我相信这可以使用 chernoff 不等式界限得出，但我无法弄清楚如何去做。任何帮助，将不胜感激。提前致谢！

Answer 1

如果 J' 表示估计并且 J 是真正的 Jaccard 相似度，则 (k * J') 遵循参数为 k 和 J 的二项式分布。因此，估计的方差为 Var(J') = J(1- J)/k <= 1/(4*k)。因此，J 的标准偏差以 stdev(J') <= 1/(2*sqrt(k)) 为界。