分布式LSH（局部敏感哈希）

Question

我想使用LSH构建一个具有数百万个高维向量的大型可扩展数据库。由于我必须将所有数据保存在内存中以实现快速查询，因此必须将数据分布到多个服务器上以容纳所有对象。

一种天真的方法是将所有对象分散到不同的服务器上，并向每个服务器发送一个查询。具有最佳答案的服务器应该有正确的对象。

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

对于分布式LSH表，什么是好的方法？也许有一些项目？

感谢任何提示。

- Marlon

---

我会看一下 Cassandra，使用自定义分区。 - Savino Sguera

这可能与之相关：使用局部敏感哈希在高维空间中进行分布式相似性搜索，作者为Haghani，Michele和Arberer。 - Kipton Barros

@KiptonBarros的链接已经消失，但是这篇论文可以在这里找到：https://openproceedings.org/2009/conf/edbt/HaghaniMA09.pdf - duhaime

Answer 1

首先，您需要考虑访问数据的键。这些键是您想要进行哈希的键 - 如果您知道要访问的确切键，则可以对它们进行哈希以确定要查询哪个服务器 - 从而消除了查询每个服务器的需要。

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

在我看来，一切都取决于你的 LSH 函数 - 选择取决于你的应用程序的具体情况。

- aSteve