分布式LSH（位置敏感哈希）

Question

我想使用LSH建立具有数百万个高维向量的大型可伸缩数据库。由于必须将所有数据保存在ram中才能进行快速查询，因此必须将数据分发到多个服务器上以容纳所有对象。

幼稚的方法是将所有对象散布到不同的服务器，并向每个服务器发送一个查询。正确答案最佳的服务器具有正确的对象。

我确信必须有一些更好的解决方案，其中不必将查询发送到所有服务器节点，并且将相似的对象分组到一台服务器上。

什么是分布式LSH表的好方法？也许那里甚至有一些项目？

感谢您的任何提示。

Answer 1

首先，您需要考虑访问数据所使用的键。您想要对这些密钥进行哈希处理 - 如果您知道想要访问的确切密钥，您可以对它们进行哈希处理以确定要查询的服务器 - 从而无需查询每个服务器。

如果您不知道确切的键（我怀疑您的情况就是这样），事情就会变得更加困难 - LSH 会为您的记录生成总排序 - 其中相似的记录可能（但不能保证）具有相同的哈希值。例如，我认为这是超平面到其法线向量从原点开始的长度的映射...因此，例如，如果搜索与 4 和 5 之间的超平面相似（但不相同）的超平面距离原点 4 到 5 个单位的超平面是一个开始寻找的好地方。因此，如果这个“距原点的距离”是您的位置敏感哈希函数，您可以使用它对数据进行分片，并且这样做时 - 您可以通过仅搜索具有匹配的分片来减少负载（同时增加最坏情况的延迟）距原点 LCH 的距离。使用这个特定的 LCH，其中相似性与哈希值线性相关，只需访问分布式服务器的子集就可以获得明确的结果。并非所有 LSH 功能都是如此。

恕我直言，一切都取决于您的 LSH 功能 - 并且选择取决于您的应用程序的具体情况。