任意のメトリックを使用してKD-Treeを検索できますか？

Question

私はちょうど最近最短の検索を行うためにkd-treeの実装を完了しました。私はEuclidean distance以外の距離メトリックで遊んでみたいと思っています。 kd-treeについての私の理解は、指標が非ユークリッドなら正確な検索を保証するものではなく、新しいデータ構造と検索アルゴリズムを実装する必要があるかもしれないということです私の検索のための新しい測定基準を出してください。

私は2つの質問している：永久Euclidean distanceに私を結ぶkd-treeを

1. を使用していますか？
2. もしそうなら、どんな種類のアルゴリズムを任意の方法で試すべきですかmetrics？私は多くの異なるデータ構造を実装する時間がありませんが、私が考えている他の構造にはcover treesとvp-treesが含まれています。

Answer 1

あなたがリンクしているWikipediaのページに記載されている最近隣の検索手順は、「超球」を与えられたメトリックに相当する幾何学的オブジェクトに置き換えれば確かに他の距離メトリックに一般化できます。このオブジェクトとの交差点。

例：マンハッタン距離を使用している場合（つまり、ベクトル成分のすべての差の絶対値の合計）、超球面は（多次元の）ダイヤモンドになります。 （これは2Dで視覚化するのが一番簡単です - 現在の最近隣が距離xのクエリーポイントpにある場合、別の超平面の背後にあるより近いネイバーは、幅と高さが2xのダイヤモンド形状と交差する必要があります。 pを中心に）。これは、超平面交差テストをコード化するのが困難になるか、または実行が遅くなる可能性がありますが、一般原則はそのまま適用されます。

Answer 2

ユークリッド距離に縛られているとは思わない - j_random_hackerによると、おそらくマンハッタン距離を使うことができますが、デカルト座標で表現できるジオメトリに結びついていると確信しています。たとえば、メトリック・スペースを索引付けするためにkdツリーを使用することはできませんでした。