SQL中的KD-Tree实现

Question

有没有人知道在SQL中有没有实现的（一种空间索引）或者类似的东西？我本来打算用Python和Django的ORM自己写一个，但我想避免重复造轮子。

我有一个表格，里面有几百万行数据，每一行有128列，代表图像特征数据。给定一个任意的128个元素的图像特征列表，我想用KD-Tree来找到数据库中最相似的N张图片。我找到了一些KD-Tree的实现，但它们似乎都只能在本地内存中加载，不能扩展或者和数据库对接。

Answer 1

我可能有点跑题了，但你最好的选择可能是在Postgresql中使用Gist或Gin索引。

Answer 2

KD树在处理高维数据时效果不好，128维的数据算是相当高了。KD树会把每个维度放在树的不同层级上，当你进行查询时，算法会进行很多回溯（也就是要检查树枝的两边），结果是会搜索到树里大部分的点。这样一来，使用树结构的好处就没了，反而全面比较的方式会更快。

你可以找找有没有现成的图像相似性搜索系统，把你的数据放进去。这里有一个叫Lire的系统，它可以从图像中提取特征，并用Lucene来进行索引。

如果你的工作更偏向研究，可以了解一下度量空间索引和近似k近邻搜索的相关内容。