SQL で実装されたKD-Tree、または同様の空間インデックスを知っている人はいますか? Python と Django の ORM を使用して独自のコードを作成することを検討していましたが、車輪の再発明は避けたいと考えています。
何百万もの行を含むテーブルがあり、各行には画像の特徴データを表す 128 列が含まれています。画像特徴の任意の 128 要素の長いリストが与えられた場合、KD ツリーを使用して、データベース内で最も類似した N 個の画像を見つけたいと考えています。多くの KD-Tree 実装を見つけましたが、それらはすべてローカル メモリにロードするだけで、スケーリングやデータベースとの通信は行わないようです。
KD ツリーは高次元データではうまく機能せず、128 次元はかなり高くなります。KD ツリーは、ツリーの異なるレベルで各ディメンションにインデックスを付けます。クエリを実行すると、アルゴリズムは多くのバック トラッキング (分岐の両側を検索) を実行し、最終的にツリー内のほとんどのポイントを検索します。これが発生すると、ツリー構造を使用する利点がなくなり、徹底的な比較がより高速に実行されます。
データをマッピングできる既存の画像類似性検索システムを見つけたいと思うかもしれません。これは、画像から特徴を抽出し、Lucene を使用してインデックスを作成する Lire と呼ばれるものです。
あなたの仕事がより研究志向の場合は、メトリック空間インデックスと近似 k 最近傍探索を読みたいと思うかもしれません。
私はここから少し離れているかもしれませんが、Postgresql 内で Gist / Gin インデックスを使用するのが最善の策かもしれません