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

回答