一个数据库或类似的存储高维数据并从中快速查询最近的邻居/项目的对象

Question

我们正在创建一个生成模型，该模型生成项目的特征。特征向量是高维向量（大约200-500维度）。

现在，我们在数据集中喜欢超过10+百万个项目。我们正在寻找一种方法来将这些项目存储到数据库中，并根据生成的特征向量与数据库中存储的特征向量之间的距离来查询“最近”项目。确切地说，我们面临以下问题：

• 一种存储所有项目（可能在数据库中的方式，以便我们可以快速查询与所生成特征“最接近”的项目。
• 定义自定义算法以计算此距离（除欧几里得距离以外的一种方法）

PS：经过研究后，我发现this-“一个PostgreSQL模块，实现了表示多维数据的数据类型cube。”

此模块为操作员提供了计算两个cubes a和b之间的欧几里得距离，出租车（L-1公制）距离和Chebyshev（L-inf公制）距离的功能。 。

但是，多维数据集的尺寸限制为100。另外，我们不能使用自定义距离公式。

嗯，这是我能找到的最接近的。

非常感谢您提供任何帮助。

Answer 1

看看AnnDB

这是一个分布式的近似最近邻居数据库，可水平缩放到数百万个高维向量。它支持L2，L1和余弦指标。

免责声明：我是AnnDB的作者。

Answer 2

如果使用的是Python，请查看here以获取各种高亮度索引。它们主要是退火指标，这意味着（如果我错了，请纠正我），它们会牺牲一些准确性以提高速度。

如果您正在使用Java和/或对100％的精度感兴趣，请查看PhTree，尤其是HD（高亮度）版本。这是一个多维内存索引，应该能够在大约10秒钟左右的时间内建立1M点的索引。它支持不同的距离函数，存储库包含欧几里得距离和L1距离的实现。但是，您可能需要一台具有大量RAM的机器，我猜测（未进行任何测量）每1M点大约5-10GB？]

据我所知，它的性能优于KD-Trees，并且比R * Trees更快（有关索引的集合，请参见here）。我尚未对其进行测试，但是我认为它不能与退火指数竞争，但是与退火指数不同，它将提供100％正确的结果。

尽管请注意，PH树是map

，所以两次添加相同的坐标将覆盖上一个条目。一种简单的解决方法是添加具有唯一标识符的附加维度。当然，此尺寸应从距离计算中排除。

免责声明：我是PH-Tree和TinSpin索引库的作者。