1

LSH は、ANN の一般的なアルゴリズムです。

kd Tree は、おそらく NN を正確に解くための最も一般的なソリューションです。

ただし、この調査を読んで、これらの構造を見つけましたが、どちらが NN または ANN を解くためのものかわかりません。

  • クワッド/オクトツリー
  • ボールツリー
  • Rツリー
  • Mツリー

ANN専用の調査は見当たりませんでしたので、いずれもNNとメートル空間用だと思います（非メートル空間には使えません）。

4

1 に答える 1

2

まず、quadtree、Ball tr​​ee 、R-tree、M-treeが Nearest Neighbor Search (NNS) に使用できることを確認します。

構造体が NNS をサポートできる場合、近似最近傍検索をサポートできます。

たとえば、よく知っている kd ツリーを考えてみましょう。クエリへの回答となる可能性のあるポイント候補を収集します。考えられるすべての候補をチェックすると、正確な Nearest Neighbor クエリに答えることができます。候補のいくつかを確認すると、おおよその Nearest Neighbor クエリに答えることができます。

それが役立つことを願っています! :)

于 2016-10-28T20:07:03.707 に答える