math - 余弦相似度LSH和随机超平面

Question

我读到了一些关于使用随机超平面进行高维最近邻搜索的解决方案，但我仍然对桶的工作原理感到困惑。我有 1 亿个 100 维向量形式的文档和 100 万个查询。对于每个查询，我需要根据余弦相似度找到最近的邻居。强力方法是找到所有 1 亿个文档的查询余弦值，并选择值接近 1 的文档。我正在努力解决随机超平面的概念，我可以将文档放入其中这样我就不必为每个查询计算 1 亿次余弦值。

Answer 1

以几何方式思考。将您的数据想象成高维空间中的点。

创建随机超平面(只是更高维度的平面)，发挥你的想象力进行还原。

这些超平面切割您的数据(点)，创建分区，其中一些点与其他点分开(其分区中的每个点；将是一个粗略的近似值)。

现在应该根据超平面形成的分区来填充存储桶。因此，每个存储桶包含的点比点集的总大小少得多(因为我之前谈到的每个分区包含的点都比点集的总大小少)。

因此，当您提出查询时，您检查的点(在存储桶的帮助下)比总大小少得多。这就是这里的所有收获，因为检查更少的点，意味着您比检查所有点的蛮力方法做得更好(更快)。