LSH中的非空桶

Question

我正在阅读关于LSH的调查，特别是引用2.2.1部分的最后一段

为了提高查全率，构造了L哈希表，并将位于L (L‘，L’< L)哈希桶中的条目h_1 (q)，···，h_L (q)作为Q的近项进行随机R-近邻搜索(或随机c-近似R-近邻搜索)。为了保证精度，每个L哈希码( y_i )都需要一个长代码，这意味着桶的总数太大，无法直接进行索引。因此，只有非空桶才能通过散列码h_l (x).的常规散列来保留。

我有三个问题：

1. 这个粗体的句子对我来说还不清楚：“诉诸传统散列码h_l (x)”是什么意思？
2. 总是关于粗体的句子，我不确定我是否有问题:我完全理解h_l(x)可以是一个长代码，所以可能的桶数量可能很大。例如，如果h_l(x)是二进制代码，而length是h_l(x)的长度，那么总的L*2^length可能有桶(因为我们使用L哈希表)...is是否正确？
3. 最后一个问题:一旦我们找到了查询向量q属于哪个桶，为了找到最近的邻居，我们必须使用原始向量q和原始距离度量？例如，假设原始向量q位于128个维q=[1,0,12,...,14.3]^T中，并且在我们的应用程序中使用了欧氏距离。现在假设我们在LSH中使用的散列函数(假设L=1是简单的)将这个向量映射到20维y=[0100...11]^T中的二进制空间，以决定哪个桶将q分配给哪个桶。因此，y具有相同的桶B索引，该索引已经包含100个向量。现在，为了找到最近的邻居，我们必须用欧氏距离来比较q和其他100 128个维向量。这是正确的吗？

Answer 1

为了提高查全率，构造了更多的哈希表，并为每个引用项存储了多个ID副本，因此空间开销较大。如果存在大量的空桶增加了检索成本，则可以使用Hamming空间中的双哈希方案或快速搜索算法来快速检索哈希桶。我认为在这种情况下，他们使用双哈希函数来检索非空桶。

桶/记忆细胞No 13 -> O(nL)

参考文献：

1

2

3.

4.