algorithm - 为什么 LSH 的 k 和 l 用于近似最近邻？

Question

在所有 Locality Sensitive Hashing 解释中（即http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search）

他们描述了生成了 k 个哈希函数，但在哈希表中只使用了 l (l < k) 来对值进行哈希处理。

为什么要生成 k 而不仅仅是生成 l？

为什么要使用单独的因子 k 和 l？

我不明白。

Answer 1

实际上使用了所有散列函数。如果您记得，例如，在“汉明距离的位采样”部分，单个散列函数可能只返回一个位，这将更有意义。事实上，LSH 散列函数的另一个例子是在某个 d 维位置考虑一个随机选择的平面，并根据被散列的点在平面的哪一侧返回 0 或 1。

要处理单个表，因为散列函数可能只返回一个位，您评估 k 个散列函数并将结果连接起来，为您提供一个可能为 k 位的密钥。现在有了 l 个表，你需要 l 个不同的键，所以实际上你总共需要 l*k 个哈希函数。

Check：看成功概率。在查找单个表时，单个哈希函数为查询和概率 P1 的近邻返回相同的值。要在单个表中找到近邻，您必须使所有散列函数起作用，因此概率为 P1^k 并且单个查找失败的概率为 1 - P1^k。但是您尝试此 l 次，因此所有查找失败的概率为 (1-P1^k)^l，成功概率为 1-(1-P1^k)^l，这正是他们计算的结果。