c++ - 署名されたメトリックを使用したKNN検索

Question

二乗された疑似ノルムを使用して、ポイントセット内のポイントのk最近傍を効率的に見つけることができるC++ライブラリを探しています。

ここで、私の3番目の座標には、その平方ノルムにマイナス記号がある場合とない場合があります。あるいは、3番目のコンポーネントが常に正の符号を持ち、4番目のコンポーネントが常に負の符号を持つ4D空間を考えることができます。

ANNライブラリのドキュメントには、任意の「ミンコフスキー」メトリックを使用できると記載されています。上記のメトリックは、ミンコフスキーメトリックの定義です（Wolfram Mathworldの意味ではありますが、ANNの意味ではありません）。ただし、ANNは柔軟性があり、「+」および「-」演算子のみが必要なようです（ANNドキュメント、14ページ）が、コンポーネントごとではなくグローバルに定義されています。

誰かがそのようなケースを処理するためにANNを一般化したことがありますか？些細なことですか？kd-treeを台無しにしませんか？そのための別のライブラリはありますか？

ありがとう！

Answer 1

ノルムx2 ⁺ y ² -z ²は、kdツリーを使用した検索が通常基づいているいくつかの仮定に違反しています。これらの仮定の1つは、「近隣」（「近くにある」）が「ローカル」プロパティであるということです。つまり、点Pが与えられると、すべての点Qはdist(P,Q) < r、Pの座標の周りに有限範囲の座標を持ちます。座標を利用して効率的な検索を行うことができます。しかし、上記の基準では、有限ボックスのない点Qに対してdist([0,0,0],Q) = 0も与えることができます。ポイントは無限の円錐上にあります。それでも、「コーン」構造を利用する効率的な検索アルゴリズムを設計することは可能であるはずですが、kdツリーは機能しません。