SQL中的KD-Tree实现

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

我有一个包含数百万行的表，每行包含128列表示图像特征数据。鉴于任意128个元素的图像特征列表，我想使用KD树来查找数据库中N个最相似的图像。我发现了很多KD-Tree实现，但它们似乎只能在本地内存中加载，并且不会扩展或与数据库进行交谈。

2011-03-31 Cerin

KD-树不高维数据很好地工作，和128点的尺寸将是相当高。 KD树将每个维度索引到树的不同层次，并且在执行查询时，该算法将执行大量的后向跟踪（搜索分支的两侧）并最终搜索树中的大部分点。当发生这种情况时，使用树结构的好处消失了，并且详尽的比较结果运行得更快。

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

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

2011-03-31 18:18:17 samplebias

我可能是有点出在这里，但你最好的选择可能是使用PostgreSQL的内部主旨/ GIN索引

2011-03-31 17:55:40

我不确定这是什么意思。根据文档，这些索引类型用于全文搜索。我不明白他们将如何适用于K近邻问题。 – Cerin 2011-03-31 18:02:58

GIN索引是Gist索引，旨在成为一般索引框架的一种形式，一个人在其上放置了kd树（http://www.cs.purdue.edu/spgist/papers/icde06.pdf）。 – 2011-05-25 18:48:34

回答