问题标签 [locality-sensitive-hash]

我正在阅读有关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) 进行对流散列，仅保留非空桶。

我有3个问题：

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

我正在寻找使用欧几里得距离的python 3中LSH的有效实现。

有“in-python”LSHForest实现，但它使用余弦距离。

此外，即使使用此实现，我也没有找到查看每个篮子内容的方法，例如，如果使用 LSH 进行聚类 - 它只返回一定半径内的一定数量的近似邻居。但是如果我想查看所有邻居，我看不到它是如何完成的（我不想使用任意的搜索半径，我真的不确定使用这个非常大或无限的半径是什么意思执行）。

将欣赏任何见解。非常感谢。

我已经阅读了这个问题，但不幸的是它没有帮助。

我不明白的是，一旦我们了解了哪个桶分配给我们的高维空间查询向量，我们会做什么q：假设使用我们的一组位置敏感的族函数h_1,h_2,...,h_n，我们已经转换q为低维（n维度）哈希码c。

然后c是分配给的桶的索引，q以及（希望）分配给它的最近邻居的位置，假设有 100 个向量。

现在，为了找到 NN，我们要做的是计算这100 个向量之间的q距离，对吗？所以使用仅用于索引（它仅用于决定分配给哪个存储桶），对吗？qcq

另一种解决方案，如本c调查（第 2.2 节）中所述，“哈希表查找”（前面描述的方法）的替代方案是“快速距离近似”，因此我们进行了详尽的研究，计算和生成的距离相对于数据集中每个元素的哈希码。这应该很快，因为哈希码在低维空间中，并且距离应该计算得更快（例如，如果哈希码空间是二进制的，那么我们可以使用 XOR 运算符来快速计算汉明两个哈希码之间的距离）。

现在，我想知道的是：这两种方法的优点/缺点是什么？为什么我应该使用一种方法而不是另一种方法？

我有一个应用程序，给定合理数量的图像（比如说 20K）和一个查询图像，我想找到最相似的图像。一个合理的近似值是可行的。

为了保证表示每个图像的精度，我使用了 SIFT（并行版本，也可以实现快速计算）。

现在，给定可以表示为矩阵的nSIFT 描述符集（500<n<1000通常取决于图像大小），n x 128从我在文献中看到的情况来看，我的情况有两种可能的方法：

1. 描述符匹配：我们将每个描述符向量映射到低维空间，并尝试找到最相似的近似值，例如通过 LSH。然后，我们相对于找到的相似描述符增加查询图像和图像之间的匹配数。我们在所有描述符上迭代该过程。最后，我们返回具有最多描述符匹配的图像作为结果。
2. Bag of Features：我们按照 BoF 模型为每个图像创建一个直方图向量。假设我们使用k-means（k=128例如，其中 ），我们会k为每个图像获得一个 -dimensions 向量。由于k可能太大而无法进行有效比较，我们可以再次通过 LSH 将其映射到更小的（可能是二进制）空间（就像我们在 1. 中所做的那样）。最后，作为结果，我们返回最相似的直方图。请注意，这种方法的一个大问题是，正如我在这个问题中所讨论的，为了快速定义直方图，我们需要再次使用 LSH（真是一团糟！）。

我很惊讶我没有发现这两种方法的任何比较。我的问题是：我们必须为每个人考虑什么？有这两种方法的研究吗？第一种方法似乎更有效，并且对于这样的数据集是可行的。

我有一个“实体解析”类型的用例，其中我有几个（< 100 个）设备功能可用于许多（几百万个）设备。我的目标是为这些设备生成 id。挑战在于同一个设备可能有两个或多个略有不同的表示，但我仍然想为所有设备分配相同的设备 ID。

我想要你在这方面的建议：

1. 我应该应用什么样的特征预处理？
2. 哪种算法最适合我的目的？
3. 请提及是否有此类算法的标准实现。

谢谢并恭祝安康，

如何在熊猫中使用模糊匹配来检测重复行（有效）

如何在没有将 row_i toString() 转换为巨大的 for 循环并将其与所有其他列进行比较的情况下找到一列与所有其他列的重复项？

我读了这个关于找到 3 维点的最近邻居的问题。八叉树是这种情况的解决方案。

kd-Tree是针对小空间（一般小于 50 维）的解决方案。

对于更高维度（数百维和数百万点的向量），LSH 是解决 AKNN（Aproxximate K-NN）问题的流行解决方案，如this question中所指出的。

然而，LSH 在 K-NN 解决方案中很受欢迎，其中 K>>1。例如，LSH 已成功用于基于内容的图像检索 (CBIR) 应用程序，其中每个图像都通过数百维的向量表示，数据集是数百万（或数十亿）张图像。在这种情况下，K 是与查询图像最相似的前 K 个图像的数量。

但是，如果我们只对高维空间中最近似的相似邻居（即 A1-NN）感兴趣怎么办？LSH 仍然是赢家，还是已经提出了临时解决方案？

假设我已经根据一组哈希构建了一个 LSH 数据库，我现在开始查询数据库以找到近似的最近邻居。

当您计算查询点的哈希并且相应的存储桶为空时，是否有任何指导方针？同样，假设我想找到 5 个近似最近的邻居，而桶只有 4 个其他数据点？

在 Spark 1.4 中应用 LSH 算法（https://github.com/soundcloud/cosine-lsh-join-spark/tree/master/src/main/scala/com/soundcloud/lsh），我处理一个文本文件（4GB ) 以 LIBSVM 格式 ( https://www.csie.ntu.edu.tw/~cjlin/libsvm/ ) 来查找重复项。首先，我在一台服务器上运行了我的 scala 脚本，只使用了一个 36 核的执行器。我在 1.5 小时内检索了我的结果。

为了更快地获得结果，我尝试在具有 3 个节点的 hpc 中通过 yarn 在 hadoop 集群中运行我的代码，其中每个节点有 20 个内核和 64 gb 内存。由于我在 hpc 中没有太多运行代码，因此我遵循了此处给出的建议：https ://blog.cloudera.com/blog/2015/03/how-to-tune-your-apache-spark-jobs-part -2/

结果，我提交了如下火花：

据我了解，我为每个节点分配了 3 个执行程序，并为每个执行程序分配了 19 GB。

但是，即使过去了两个多小时，我也无法得到我的结果。

我的火花配置是：

我该如何挖掘这个问题？我应该从哪里开始改进计算时间？

编辑：

1)

我注意到在纱线中合并的速度要慢得多

2)

HPC 的执行者和阶段：

服务器的执行者和阶段：

我想找到我每个点的最近邻居，我使用 karlhigley ANN 模型进行了尝试。这是一段代码

JavaRDD neighbors2 给了我所有的邻居和他们的分数为空。谁能帮助我了解我在哪里实施错误以及如何以正确的方式做到这一点？

这就是我打印输出的方式