问如何理解位置敏感的哈希？

EN

向量空间中的Tweets就是高维数据的一个很好的例子。

请查看我的博客文章，将位置敏感的散列应用到tweet中，以找到类似的推文。

http://micvog.com/2013/09/08/storm-first-story-detection/

因为一张图片是千言万语，所以看看下面的图片：

​

http://micvog.files.wordpress.com/2013/08/lsh1.png

希望能有所帮助。@mvogiatzis

这是来自斯坦福大学的演示文稿，解释了这一点。这对我来说有很大的不同。第二部分更多的是关于LSH，但第一部分也涵盖了它。

概述图片(幻灯片中有更多内容)：

​

​

高维数据中的近邻搜索-- Part1：http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf

高维数据中的近邻搜索-- Part2：http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf

我是一个视觉的人。这就是我的直觉。

假设你要搜索的每一样东西都是物理对象，如苹果、立方体、椅子。

我对LSH的直觉是，它类似于拍摄这些物体的阴影。例如，如果你把一个三维立方体的阴影放在一张纸上，你会得到一个2D方形的阴影，或者一个三维球体会让你在一张纸上得到一个圆形的阴影。

最终，搜索问题中存在的不仅仅是三维问题(文本中的每个单词都可以是一个维度)，但shadow类比对我仍然非常有用。

现在我们可以有效地比较软件中的位串。固定长度的位串有点，或多或少，就像一维的一条线。

因此，使用LSH，我最终将对象的阴影投影为单个固定长度的线/位字符串上的点(0或1)。

整个技巧是采取阴影，使它们在较低的维度仍然有意义，例如，它们以足够好的方式与原始对象相似，可以识别。

透视中的立方体的2D图形告诉我这是一个立方体。但是，如果没有透视，我很难区分2D正方形和3D立方体阴影:在我看来，它们都像一个正方形。

我如何将我的物体呈现给光线将决定我是否得到一个好的可识别的阴影。因此，我认为一个“好的”LSH会将我的物体转到光的前面，这样它们的阴影就可以很好地识别为代表我的物体。

所以重述一下:我把要用LSH索引的东西想象成像立方体、桌子或椅子这样的物理对象，然后在2D中投影它们的阴影，最终沿着一条线(位字符串)投影。一个“好的”LSH“函数”是我如何将我的物体呈现在光的前面，以便在2D平面中获得大致可区分的形状，然后是我的位串。

最后，当我想要搜索我拥有的对象是否与我索引的一些对象相似时，我使用相同的方式获取这个"query“对象的阴影，将我的对象呈现在光的前面(最终也以位串结束)。现在我可以比较这个位串和我所有其他索引位串的相似性，如果我找到了一种好的和可识别的方式来将我的对象呈现给我的光，它是搜索整个对象的代理。