1

局部敏感哈希 (LSH) 的关键思想是相邻点v更有可能映射到同一个桶，但彼此相距较远的点更有可能映射到不同的桶。在使用随机投影时，如果数据库包含 N 个样本，每个样本都具有较高的维度 d，那么理论上我们必须创建 k 个随机生成的哈希函数，其中 k 是目标缩减维度，表示为g(**v**) = (h_1(v),h_2(v),...,h_k(v))。因此，对于任何向量点v，该点都映射到具有 g 函数的 k 维向量。那么哈希码就是长度/维度为k的缩减向量，被视为一个桶。现在，为了增加碰撞概率，理论说我们应该g_1, g_2,...,g_L随机拥有 L 个这样的 g 函数。这是我不明白的部分。

问题：如何创建多个哈希表？一个哈希表中包含多少个桶？

我正在遵循Sparse Projections for High-Dimensional Binary CodesYan Xia 等人在论文中给出的代码。al 代码链接

在文件中Coding.m 

dim = size(X_train, 2);
R = randn(dim, bit);

% coding
B_query = (X_query*R >= 0);
B_base = (X_base*R >=0);

X_query是每个维度为 d 的查询数据集，有 1000 个查询样本；R是随机投影，位是目标降维。B_query和的输出B_base是N长度k为 0/1 值的字符串。这种方式是否会创建多个哈希表，即哈希表N的数量？我很困惑如何。详细的解释将非常有帮助。

4

1 回答 1

1

如何创建多个哈希表？

LSH 通过连接使用（放大的）哈希函数创建哈希表：

g(p) = [h 1 (p), h 2 (p), · · · , h k (p)], h i ∈<sub>RH

g()是一个哈希函数，它对应一个哈希表。因此，我们通过该哈希表将数据映射g()到该哈希表，并且很有可能，接近的将落入同一个桶中，而非接近的将落入不同的桶中。

我们这样做了L，因此我们创建了L哈希表。请注意，每个散列函数g()都/应该最有可能与其他g()散列函数不同。

注：较大的 k ⇒ P 1 , P 2之间的较大差距。小 P 1 ⇒ 大 L 以便找到邻居。一个实际的选择是 L = 5（或 6）。P 1和 P 2在下图中定义：

在此处输入图像描述

一个哈希表中包含多少个桶？

希望我知道！这是一个难题，数据集中的点数在sqrt(N)哪里。N检查这个：LSH 中的桶数

言夏密码

我不熟悉，但从你所说的来看，我相信你看到的查询数据是 1000 个，因为我们希望提出 1000 个查询。

k是字符串的长度，因为我们必须对查询进行哈希处理以查看它将映射到哈希表的哪个桶中。该桶内的点是潜在的（近似的）最近邻居。

于 2016-05-26T17:01:32.997 回答