python - SQL中的KD树实现

Question

有人知道用 SQL 实现的KD-Tree或类似的空间索引吗？我正在考虑使用 Python 和 Django 的 ORM 编写自己的代码，但我想避免重新发明轮子。

我有一个包含数百万行的表，每行包含 128 列代表图像特征数据。给定一个任意的 128 元素长的图像特征列表，我想使用 KD-Tree 在数据库中找到 N 个最相似的图像。我发现了很多 KD-Tree 实现，但它们似乎都只加载到本地内存中，不能扩展或与数据库通信。

Answer 1

KD-tree 不适用于高维数据，128 维会相当高。KD-tree 在树的不同级别索引每个维度，并且在执行查询时，该算法将执行大量回溯（搜索分支的两侧）并最终搜索树中的大部分点。当这种情况发生时，使用树结构的优势就会消失，详尽的比较最终会运行得更快。

您可能希望找到可以将数据映射到的现有图像相似性搜索系统。这里有一个叫 Lire，它从图像中提取特征并使用 Lucene 对它们进行索引。

如果您的工作更注重研究，您可能需要阅读度量空间索引和近似 k 最近邻搜索。

Answer 2

我可能有点出格，但你最好的选择可能是使用 Postgresql 中的 Gist / Gin 索引