问题标签 [locality-sensitive-hash]

假设我在 O(D*sqrt(D)) 时间内预处理了一百万个文档（使用 minhash 计算的签名），其中 D 是文档数。当我得到一个查询文档时，我必须在 O(sqrt(D)) 时间内返回一百万个预处理文档中的第一个，使得 jaccard 相似度大于或等于 0.8。

如果没有与查询文档相似的文档足以达到该分数，我必须返回相似度至少为 c * 0.8（其中 c<1）且概率至少为 1 - 1/e^2 的文档。我怎样才能找到这个 minhash 方案的 C 的最大值？

我已经阅读了很多教程并尝试了一些 minhash LSH，但它无法生成相似度矩阵，而是只返回超过阈值的相似数据。我怎样才能生成它？我的意图是使用 LSH 结果进行聚类。

我有一个问题，在这个答案和这个答案中也提到了，但我使用的是二进制描述符，需要更多信息：

我使用 BRAND 描述符作为 LSH 问题的输入。描述符的大小为 300*32 到 400*32，其中 32 是描述符的长度，图像有 300 到 400 个关键点。BRAND 的输出是一个整型矩阵。

由于这个答案提到 LSH 的输入是 D 维的向量，这意味着每个图像都将作为 D 维的一个向量插入到哈希表中，现在这是我的问题：

A. 如何将整数描述符矩阵转换为输入向量？我应该将矩阵行按顺序复制为向量吗？或者是否可以转换描述符的每一行，将项目转换为二进制并将它们连接为 256 位二进制并具有它们的 D 维向量？

B. 在使用 L1 范数的情况下，是否有必要将 BRAND 描述符的整数值转换为二进制数字，据我了解，二进制向量的汉明距离是否相同？

非常感谢您提前。

我正在尝试实现 LSH spark 以在包含 50000 行和每行约 5000 个特征的非常大的数据集上为每个用户找到最近的邻居。这是与此相关的代码。

这项工作陷入了 approxSimilarityJoin() 函数，并且永远不会超出它。请让我知道如何解决它。

我正在寻找一种高性能算法，根据这个数据结构按位置、性别和年龄匹配大量人：

• 经度（表示人员位置）
• 纬度（表示人员位置）
• 性别（表示人的性别）
• 生日（表示人的生日）
• LookForGender（表示该人正在寻找的性别）
• LookForMinAge（表示该人正在寻找的最小年龄）
• LookForMaxAge（表示该人正在寻找的最大年龄）
• 寻找半径（表示该人正在寻找的最大距离）
• 已处理（表示此人已经处理了哪些其他人）

对于任何人 P，算法应返回适用的候选人 C：

• C 的性别必须相等 P.LookingForGender
• P 的性别必须相等 C.LookingForGender
• C 的生日必须在 P.LookingForMinAge 和 P.LookingForMaxAge 之间
• P 的出生日期必须在 C.LookingForMinAge 和 C.LookingForMaxAge 之间
• P 和 C 之间的纬度/经度距离必须小于或等于 P.LookingForRadius
• P 和 C 之间的纬度/经度距离必须小于或等于 C.LookingForRadius
• 处理过的 P 不能包含 C

该算法应按距离（纬度/经度）顺序返回前 100 个候选 C。该算法应该针对搜索和更新进行优化，因为人们可能经常改变他们的位置。

我目前的想法是kd 树可能比locality-sensitive-hashing更适合这些需求，我应该朝这个方向发展。

你对我有什么建议？我应该寻找什么？你看到了什么风险？

谢谢！

更新：

• 我是否更愿意牺牲空间复杂度以获得更好的时间复杂度？是的，我更喜欢牺牲空间复杂性。但是，我更喜欢有一个我真正理解并可以维护的 O(log n) 解决方案，而不是我无法掌握的 O(1) 解决方案:)
• 数据是否适合主内存？不，不是的。数据将分布在分布式文档数据库 (Azure Cosmos DB SQL API) 的不同节点上。
• 你想要精确的结果还是近似的结果？近似结果是可以的，但是应该准确过滤年龄/性别。
• 在算法中添加了“已处理”，抱歉错过了！
• 人们多久改变一次他们的位置？每当用户启动应用程序并寻找候选人时，他们都会改变他们的位置。因此，每日活跃用户将每天一次或多次更改其位置。然而，位置变化可能很小，只有几公里。从 100 次应用下载中，15 位用户每月会使用一次或多次，3 位用户每天会使用一次或多次。

我有一个大小为 (160000,3200) 的数据集，其中所有元素都是零或一。我想找到类似的候选人。我已经使用 Minhash 使用一个 for 循环将它散列到 (160000,200) 并且花了大约两分钟，我很满意。我已经使用从“海量数据集挖掘”的第 3 章中学习的 AND-OR 模式实现了局部敏感哈希（LSH），以在 for 循环中使用 for 循环查找候选对，但花了 30 分钟。我想减少这个时间。有没有更快的方法？

这是我如何完成 LSH - Minhash 签名长度 (n) = 200，子签名长度 (r) = 5，波段数 (b) = 40。

大小为 (160000,200) 的 Minhash 签名矩阵是一个 numpy 数组。我的想法是，如果我可以便宜地将其转换为 (160000,40) 数组，其中新数组的每个元素由 minhash 数组的 5 个元素组成，那么也许我可以使用 numpy.unique() 为每列获取唯一的 r_signature用作候选ID字典的键。我是 python 和编码的新手。我想不出一种方法来优化它以使其运行得更快。

这是代码和数据的链接： https ://colab.research.google.com/drive/1HetBrWFRYqwUxn0v7wIwS7COBaNmusfD

注意：我观察到 Minhash 部分所花费的时间随着数据（在这种情况下为用户数）线性增加，而对于 LSH 部分，它是非线性增加的（对于前 6.25%，它花费了 20.15 秒，对于最后 6.25% 用时 132.3 秒）。我认为有必要优化这部分，如果可能的话，用数据正确扩展。我相信检查字典中是否已经存在密钥是负责此问题的代码部分。

更新：我已经通过避免检查字典中键的存在来解决这个问题，尽管我最终在 for 循环中使用了 for 循环两次。现在，160000 个候选人需要 310 秒，并且所花费的时间与数据呈线性关系。我已经更新了 google-colab notebook 中的相应代码。

例如，假设我们有一些长度不同的向量，我们想要做的是测量每两对这些向量之间的相似性。我们必须考虑的是这些向量的维度是随时间变化的。我们可以这样做吗？

我有一个数据集，其中包含从许多不同来源收集的数百万个项目。每个项目都包含从五十到一千个属性的列表。可用的特定属性因项目而异。

我正在寻找找到与集合中给定目标成员项目最相似的项目的最佳方法。（我显然想在不与集合中的所有项目进行蛮力比较的情况下完成此操作。）

我想使用类似 Locality Sensitive Hashing 和 MinHash 的东西。但是，如果目标项目有 50 个属性，而较大数据集中可能匹配的项目有 200 个，即使具有 200 个属性的项目包含目标项目的所有属性，MinHash 也会认为这些是不相似的。

用于比较具有不同数量属性的项目的最佳技术或算法是什么？

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

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

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

我试图了解 Spark 中的 MinHash LSH 实现，org.apache.spark.ml.feature.MinHashLSH.

这两个文件似乎最相关：MinHashLSH.scala和LSH.scala。

要使用 MinHashLSH，文档说它需要一个numHashTables参数，即

LSH OR-amplification 中使用的哈希表数量的参数。

我的理解是hashFunction方法计算每个输入实例的 MinHash 签名（例如代表文档的单曲/令牌集合），例如

输出：

numHashTables每个输入实例使用的哈希函数的数量/MinHash 签名的长度也是如此。

但是我还没有看到任何与代码中的Mining of Massive Datasets一书的第 3 章介绍的条带技术相关的内容。带状技术基本上将每个实例的所有 MinHash 值划分为b带状，每个带中都有行，因此和r的乘积应该等于使用的散列函数的数量。在计算候选对时，调整并在包含假阳性或假阴性方面具有重要意义。rbbr

从我看到sameBucket inapproxNearestNeighbors和two-dataset join inapproxSimilarityJoin是如何实现的方式来看，看起来行数总是假设为1，那么band的数量等于散列函数的数量，即numHashTables，这也是与numHashTablesLSH OR-amplification 中使用的描述一致。

然而，如果r总是一个，假设numHashTables=10我们可以计算比我们需要基于等式更多的对（误报，相关代码）的JarccardkeyDistance距离（又名in ）MinHashLSH

Pr = 1 - (1 - s^r)^b

其中Pr是具有 Jaccard 相似性（不是距离）的一对s哈希到同一个桶的概率。

所以我想确认一下我的理解是否正确：在 的实现中假定行数始终为 1 org.apache.spark.ml.feature.MinHashLSH，并且numHashTables等于用于计算 MinHash 签名的哈希函数数和带数/局部敏感散列中使用的散列表。