非メトリック空間での最近傍検索

Question

非メトリック空間で作業する場合、最近傍検索アルゴリズムについて知りたいですか？特に、証明可能な時間の複雑さなどを伴うこの設定のkdツリーアルゴリズムの任意の変形があるか？

Answer 1

NMSLIBは、ノーメトリックのスペースでNearest Neigher Searchを実行するライブラリを提供します。そのGithubのページには、読みたい論文が12種類ありますが、すべてが非メトリックな分野には適用されません。

残念ながら、ノーメトリックスペースのNeaest Neighbour Searchの複雑さに関する理論的結果はほとんどなく、包括的な経験的評価はありません。

Effective Proximity Retrieval by Ordering Permutationsでいくつか理論的な結果があるのはわかりますが、私は確信していません。しかし、私はあなたを見てみることをお勧めします。

非メトリックスペースにk-dツリーを使用する人がいれば多くないようです。彼らは、VPツリーなどを使用しているようです。Near Neighbor Search in Nonmetric Spacesに記載されているように、濃度も使用されます。

直感的には、密度は、metric treeと同様の方法でデータセットのポイントを保持する装飾されたツリーのクラスです。クリティカルな違い は木の装飾の性質にあります。各ツリーノードに付随する三角不等式にある境界を反映する1つまたはいくつかの実際の値を有する代わりに、各密度ノードはここでは密度推定器と呼ばれる特定の分類器に関連付けられる。

Answer 2

おそらくもっと理論的な興味： PH-Treeはクアッドツリーに似ていますが、浮動小数点座標を非メトリックシステムに変換してから保存します。 PH-Treeは、非メトリック距離関数を使用して、非メトリックデータ上のすべてのクエリ（kNNクエリを含む）を実行します（それに独自の距離関数を定義できます）。

kNNに関しては、PH-TreeはR + Treesのようなツリーと同じレベルで実行され、通常はkd-treesより優れています。 非メトリックデータストレージは、変換および距離関数の（ほとんど無視できる）実行時間を除いて、パフォーマンスにほとんど影響を与えません。

データが変換される理由は、ツリーの固有の制約から来ています。ツリーはビット単位のトライであり、ビットシーケンス（整数として見ることができる）のみを格納できることを意味します。浮動小数点数をツリーに格納するには、単純に浮動小数点数のIEEEビット表現を使用し、それを整数として解釈します（これは正の数では問題なく、負の数はもう少し複雑です）。これは重要なことです。浮動小数点f1がf2より大きい場合、int（f1）のビットの整数表現も常にint（f2）より大きい簡単に言えば、この変換により、浮動小数点数を精度（！）を失うことなく整数として格納することができます。

浮動小数点数の先頭ビット（符号ビットの後ろ）が指数ビットで、小数点ビットが続くため、変換は非メトリックです。明らかに、2つの数の指数ビットが異なる場合、それらの距離は、小数点ビットの違いによって生じる距離に比べて指数関数的に速く（または負の指数では遅く）増加する。

私たちはなぜビットワイズトライを使用しましたか？ d次元があれば、座標のd個の値のn番目のビットをdビットのビット列にマップできるように簡単な変換が可能です。たとえば、d = 60の場合、60ビットの文字列が得られます。CPUレジスタの幅が64ビットであると仮定すると、これは、一定時間内にクエリに関連する多くの演算を実行できることを意味します。つまり、3次元であるか60次元であるかにかかわらず、この短いテキストから何が起こっているのかを理解することはおそらく難しいでしょう。詳細については、hereを参照してください。