放大局部性敏感散列

Question

我试图构建一个对余弦局部性敏感的散列，这样我就可以找到候选的相似对项，而不必比较每一对可能的项。我有基本的工作，但在我的数据中的大多数对似乎有余弦相似性在-0.2到+0.2范围内，所以我试着把它切得很细，选择余弦相似性0.1及以上的东西。

我一直在阅读“挖掘海量数据集”第三章。这篇文章通过放大一个局部性敏感的家族来提高候选对选择的准确性。我想我大概能理解数学上的解释，但我很难理解我是如何实际地实现这一点的。

到目前为止，我的情况如下：

1. 我说过1000部电影，每部都有来自100万用户的收视率。每部电影都由用户分数的稀疏向量表示(行号=用户ID，value =用户分数)。
2. 我构造了N个随机向量。向量长度匹配电影向量的长度(即用户数量)。向量值为+1或-1。实际上，为了节省空间，我将这些向量编码为二进制，+1映射到1，-1映射到0。
3. 我通过获取电影的点积和N个随机向量来构建每个电影的草图向量(或者更确切地说，如果我通过水平放置N个随机向量并将它们层叠在一起来创建一个矩阵R，那么电影m的草图是R*m)，然后取结果向量中每个元素的符号，所以我以+1s和-1s的草图向量结尾，这再次我编码为二进制。每个向量都是长度N位。
4. 接下来，我通过执行下面的查找类似的草图
   1. 我将草图向量分割成r位的b波段。
   2. R位的每个频带都是一个数字。我将这个数字与带号结合起来，并将电影添加到该数字下的散列桶中。每部电影都可以添加到多个桶中。
   3. 然后我看看每个水桶。任何在同一个桶里的电影都是候选对。

与mmds的3.6.3相比，mmds是当我查看r位的波段时--如果r位具有相同的值，一对电影会通过和步骤。我的或步骤发生在桶:电影是候选对，如果他们都在任何一个桶。

这本书建议我可以通过添加更多和或步骤来“放大”我的结果，但是我对如何实际地做到这一点感到困惑，因为对于更多层的建造过程的解释是检查成对的相等，而不是想出桶号。

有人能帮我理解怎么做吗？

Answer 1

我想我已经解决了一些问题。基本上，我正在寻找一种在map/还原类型环境中工作的方法，我认为这种方法可以做到这一点。

所以,

• 假设我有b带的r行，我想要添加另一个和stage，例如另一个c‘s。
• 所以，我需要的不是b*r位，而是b*r*c位的散列。
• 然后我在b*r位上运行我以前的过程c次。
• 如果x和y是这些过程中的一个候选对，则它发出一个键值对((x，y)，1)，其中IDs (x，y)的元组为键，值为1。
• 在c过程的末尾，我按键和和对这些对进行分组。
• 在每个c轮中，与c相等的任何对(x，y)都是候选对，整个过程的候选对也是如此。

所以现在我有了一个可行的解决方案，我所需要做的就是弄清楚使用这样的三个步骤是否会帮助我获得更好的结果，减少总体哈希位，还是更好的整体性能……