问题标签 [lsh]

我正在实现 minhash 和 LSH 以在 C++11 中对某些字符串元素进行相似性搜索。我的实现的 minhash 草图是 200 个 64 位整数的向量，即vector<uint64_t> MinHashSketch. 我有超过 200 万个条目，草图生成部分不需要太多时间。但是，分桶阶段需要很长时间。我想知道是否可以得到一些建议以使其更快一些。以下是我使用 LSH 的分桶阶段。

我在草图中使用连续的元素来创建一个成为桶 id 的哈希。如果bsize = 5，则（对于第 i 个元素）中的元素构成存储桶 ID 1-5, 6-10, 11-15, ... 196-200。MinHashSketch[i]遵循执行此操作的代码。

嗨，我正在尝试制作一个用于确定相似性图像的 android 应用程序，而我的模型使用 lsh，那么我如何在 android studio 上使用 java 来实现它。

我正在使用此链接来解决我的问题 我有一种情况，我正在使用位置敏感度散列来查找 3 个最近的邻居。我的数据集有 22 列分类和连续，大约 5000 行。我正在使用以下代码运行 LSH：

我收到此错误：ValueError: data type must provide an itemsize

在传递到 LSH 之前，我已经对所有数据集进行了编码，并且我的数据帧的数据类型是浮点数。我在这里想念什么？

如何打印前三个邻居的结果？我在数据框中的第一列是 Cust_ID，我需要打印输出如下：

等等

我是一名初学者数据科学家，尝试使用 datasketch 中的 LSH 实现来编写快速重复搜索。当我使用大尺寸的输入文本（文档数 > 250000）运行我的程序时，第 1 步很好，但随后程序在第 2 步挂起。当我用小输入运行程序时，一切正常。有没有决定如何解决这个问题？

我有这段代码：

cm 包含 = [ column-for-document1，column-for-document-2，column-for-document3 ]

其中 column-for-document1 看起来像这样 (1, 0, 1, 1, 0, 0, 1, 1 )

我需要计算 JS=a/(a+b+c)

• column-for-document1 和 column-for-document2 之间的 Jaccard 相似度 (JS)
• column-for-document1 和 column-for-document3 之间的 Jaccard 相似度 (JS)
• column-for-document2 和 column-for-document3 之间的 Jaccard 相似度 (JS)

但是cm是一个大文件，它在 3 台不同的计算机上（因为它是大数据编程），所以，

column-for-document1 在一台计算机上；column-for-document2 在另一台计算机上；column-for-document3 在第三台计算机上

如果它们都在不同的计算机上，您如何计算上述内容？

我需要为此使用笛卡尔

cm.cartesian(cm)

但我什至不确定从哪里开始，因为cm在数据集中。我想也许我可以将它转换成一个数组然后比较索引，但我以前从未使用过数据集，所以我不知道该怎么做或者什么是最好的策略。

请用java spark写下你的答案。

我想知道LSH（局部敏感散列）是否适用于任何类型的文件以查找最近的邻居？意味着我到处都注意到了，只使用文本文件，但我想找到 wim、iso 和 zip 文件。

它也适用于 wim、iso 和 zip 文件。

提前致谢

据我了解，LSH 方法的主要功能之一是数据减少，甚至超出了底层哈希（通常是 minhashes）。我一直textreuse在 R 中使用这个包，我对它生成的数据的大小感到惊讶。textreuse是一个经过同行评审的ROpenSci包，所以我认为它可以正确地完成它的工作，但我的问题仍然存在。

假设我分别为我的 minhash 和 LSH 函数使用 256 个排列和 64 个波段 - 通常用于检测相对确定性(~98%) 相似性低至 50% 的实际值。

如果我使用 (256 perms) 散列一个随机文本文件TextReuseTextDocument并将其分配给trtd，我将拥有：

现在让我们为这个对象（64 个波段）创建 LSH 存储桶并将其分配给l，我将拥有：

因此，LSH 存储桶中保留的哈希值是原始 minhashes 的六倍。我理解这是因为textreuse 使用 md5 摘要来创建存储桶哈希。

但这不是太浪费/矫枉过正，我不能改进它吗？我们的数据缩减技术最终膨胀到这种程度是否正常？根据原始哈希（类似于 perms = 256 和bands = 256）匹配文档然后使用阈值清除误报不是更有效吗？

请注意，我已经查看了诸如Mining of Massive Datasets之类的典型文本，但这个问题仍然是关于这个特定实现的。另请注意，这个问题不仅出于好奇，而且出于需要。当您拥有数百万或数十亿个哈希值时，这些差异就会变得很重要。

我了解通过应用哈希函数从带状疱疹创建签名矩阵背后的算法。但是我不明白如何将签名矩阵中的特定波段散列到桶中。假设在矩阵 M 中，带 b1 我们对文档 C1-C5 有以下值：

仅通过查看这些值，我们就可以看到 C2 和 C4 在这个波段中是相同的，它们应该散列到同一个桶中。但其他列将散列到不同的桶中。

我的问题是如何将这些列散列到桶中，并在不实际比较它们的情况下知道它们是否相同。我应该如何定义哈希函数以将列映射到存储桶？像列中元素的总和？

我必须解决非常高维（~30'000）向量的异或运算来计算汉明距离。例如，我需要计算一个充满 False 的向量与 16 个稀疏定位的 True 与 50'000x30'000 矩阵的每一行之间的 XOR 运算。

截至目前，我发现最快的方法是不使用 scipy.sparse 而是在每一行上使用简单的 ^ 操作。

这个：

l1distances=(self.hashes[index,:]^self.hashes[all_points,:]).sum(axis=1)

碰巧比这快十倍：

但是快十倍仍然很慢，因为从理论上讲，具有 16 个激活的稀疏向量应该使计算与具有 16 维一维相同。

有什么解决办法吗？我在这里真的很挣扎，感谢您的帮助！

我有几列，如文件名、文件大小和日期，我想通过考虑所有参数来查找附近的重复项。

与上面的数据框一样，我们有 4 个文件，它们具有附近的文件名、大小和日期。

预期产出