SQL中的KD树实现

Question

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

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

Answer 1

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

您可能希望找到一个现有的图像相似性搜索系统，您可以将您的数据映射到其中。Here is one called Lire它从图像中提取特征并使用Lucene索引它们。在

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

Answer 2

我可能有点过了，但最好的办法是使用Postgresql内部的Gist/Gin索引