数据库支持快速近似最近邻查询

Question

是否有一个数据库支持高维向量空间中的快速近似最近邻查询？

我正在寻找一个适合以下用例的数据库:

• 适用于数百万点
• 适用于数十万个维度
• 可能使用覆盖树或局部敏感散列来进行索引

是否存在强有力的实现？

Answer 1

ANN库对于高维大型数据集非常有效，但它不是一个完整的“数据库”，也不是一个分布式解决方案。

有一家名为 SpaceCurve（与我无关）的初创公司致力于商业空间数据库，因此根据您的需求和预算，他们可能值得研究。

作为一个建议：当您谈论“数十万维”时，您应该深入思考“最近邻居”的真正含义。如果在 20 维立方体中取一百万个随机点，则任何两个最近邻居之间的平均距离已经约为立方体边长的一半。

随着维度的增加，这种情况只会呈指数级恶化。一旦你谈论数百个维度，如果它们在某种程度上均匀分布，你确实需要难以置信的大量点（例如 > 10 ^{30 ）；}如果它们分布不同，您最好使用其他分类方法。