近隣住民検索

NNS問題に対する最も単純な解決策は、クエリポイントからデータベース内の他のすべてのポイントまでの距離を計算し、「これまでの最良」を追跡することです。このアルゴリズムは、ナイーブなアプローチと呼ばれることもあり、実行時間はO ( dN )です。ここで、NはSの要素数、dはSの次元です。維持すべき検索データ構造がないため、線形検索の空間計算量はデータベースのストレージ以外にはありません。ナイーブ検索は、平均的に、高次元空間における空間分割アプローチよりも優れたパフォーマンスを発揮します。^{[ 7 ]}

距離比較には絶対距離は必要なく、相対距離のみが必要です。幾何座標系では、2つの座標間の距離計算から平方根の計算を省略することで、距離計算を大幅に高速化できます。それでも距離比較の結果は同じになります。

1970年代以降、この問題には分岐限定法が適用されてきました。ユークリッド空間の場合、このアプローチには空間インデックスまたは空間アクセス法が含まれます。NNS問題を解決するために、いくつかの空間分割法が開発されています。おそらく最も単純なのはkd木で、これは検索空間を親領域の点の半分を含む2つの領域に繰り返し分割します。クエリは、各分割でクエリ点を評価することにより、ルートからリーフまでツリーをたどって実行されます。クエリで指定された距離に応じて、ヒットを含む可能性のある隣接するブランチも評価する必要がある場合があります。定数次元クエリ時間の平均複雑度はO (log N ) ^{[ 8 ]}で、ランダムに分布した点の場合、最悪の場合の複雑度はO ( kN ^(1-1/ k )) ^{[ 9 ]}です。 あるいは、R木データ構造は、R*木などの挿入と削除の効率的なアルゴリズムを備えているため、動的なコンテキストでの最近傍検索をサポートするように設計されています。^{[ 10 ]} Rツリーはユークリッド距離だけでなく、他の距離でも最近傍を生成することができます。 

一般的な距離空間の場合、分岐限定法は距離木法として知られています。具体的な例としては、vp木法やBK木法などがあります。

3次元空間から取得した点の集合をBSPツリーに配置し、同じ空間から取得したクエリ点が与えられた場合、クエリ点に最も近い点群点を見つける問題に対する可能な解決策が、以下のアルゴリズムの説明に示されています。

（厳密に言えば、そのような点は存在しない可能性があります。なぜなら、一意ではない可能性があるからです。しかし実際には、通常、与えられたクエリ点から最短距離にある点群のすべての点のサブセットのいずれかを見つけることだけが重要です。）アイデアは、ツリーの各分岐について、点群の中で最も近い点がクエリ点を含む半空間にあると推測することです。これは当てはまらない場合もありますが、良いヒューリスティックです。推測された半空間の問題を再帰的に解決するすべての手間をかけた後、この結果によって返される距離を、クエリ点から分割平面までの最短距離と比較します。この後者の距離は、クエリ点と、検索されていない半空間に存在する可能性のある最も近い点との間の距離です。この距離が前の結果で返された距離よりも大きい場合、明らかに他の半空間を検索する必要はありません。そのような必要性がある場合は、残りの半分の空間についても問題を解くという手間をかけ、その結果を以前の結果と比較し、適切な結果を返す必要があります。クエリ点が点群に近い場合、このアルゴリズムのパフォーマンスは線形時間よりも対数時間に近いものとなります。これは、クエリ点と最も近い点群点との距離がゼロに近づくにつれて、アルゴリズムはクエリ点をキーとしてルックアップを実行するだけで正しい結果を取得できるためです。

近接グラフ法（ナビゲーション可能なスモールワールドグラフ^{[ 12 ]}やHNSW ^{[ 13 ] [ 14 ]}など）は、近似最近傍探索の最新技術と考えられています。

これらの手法は、近接近傍グラフにおける貪欲探索に基づいている。${\displaystyle G(V,E)}$すべてのポイント${\displaystyle x_{i}\in S}$頂点と特有の関係があります${\displaystyle v_{i}\in V}$クエリqに対する集合S内の最近傍点の探索は、グラフ内の頂点の探索という形をとる。${\displaystyle G(V,E)}$基本的なアルゴリズムである貪欲探索は、次のように動作します。探索は入口となる頂点から始まります。${\displaystyle v_{i}\in V}$クエリqからその近傍の各頂点までの距離を計算することによって${\displaystyle \{v_{j}:(v_{i},v_{j})\in E\}}$そして、最小距離値を持つ頂点を見つけます。クエリと選択された頂点間の距離値が、クエリと現在の要素間の距離値よりも小さい場合、アルゴリズムは選択された頂点に移動し、それが新しい入口点となります。アルゴリズムは、局所最小値、つまり近傍にクエリ自身よりも近い頂点が存在しない頂点に到達したときに停止します。

近接近傍グラフのアイデアは、Arya と Mount による先駆的な論文^{[ 15 ]} 、飛行機用の VoroNet システム^{[ 16 ]} 、 RayNet システムなど、複数の出版物で活用されています。$\displaystyle \mathbb {E} ^{n}}$[ ^{17 ]}および Navigable Small World ^{[ 12 ]} 、 Metrized Small World ^{[ 18 ]}およびHNSW ^{[ 13 ] [ 14 ]アルゴリズムでは、距離関数を持つ空間の一般ケースが扱われて}います。これらの研究に先立って、Toussaint による先駆的な論文があり、その中で彼は相対近傍グラフの概念を導入しました。^{[ 19 ]}

局所性敏感ハッシュ(LSH) は、空間内の点を、点に作用する何らかの距離尺度に基づいて「バケット」にグループ化する手法です。選択された尺度の下で互いに近い点は、高い確率で同じバケットにマッピングされます。^{[ 20 ]}

カバーツリーには、データセットの倍増定数に基づいた理論的な上限があります。検索時間の上限はO ( c ¹²  log n ) で、 cはデータセットの拡張定数です。 

データが幾何学的点の密な 3D マップである特殊なケースでは、センシング技術の投影ジオメトリを使用して、検索問題を劇的に単純化できます。このアプローチでは、3D データが 2 次元グリッドへの投影によって整理されている必要があり、オブジェクトの境界を除いて、データが隣接するグリッド セル間で空間的に滑らかであると仮定します。これらの仮定は、測量、ロボット工学、ステレオ ビジョンなどのアプリケーションで 3D センサー データを扱う場合には有効ですが、一般的に整理されていないデータには当てはまらない場合があります。実際には、この技術を実世界のステレオ ビジョン データに適用した場合、 k近傍問題の平均検索時間はO ( 1 ) またはO ( K )になります。 ^{[ 6 ]}

高次元空間では、ノードのますます多くの割合を調べる必要があるため、ツリーインデックス構造は役に立たなくなります。線形検索を高速化するために、RAMに格納されている特徴ベクトルの圧縮バージョンを使用して、最初の実行でデータセットを事前フィルタリングします。最終的な候補は、距離計算のためにディスクからの非圧縮データを使用して、2 番目の段階で決定されます。^{[ 21 ]}

VAファイル方式は、各特徴コンポーネントが均一かつ独立して圧縮される圧縮ベースの検索の特殊なケースです。多次元空間における最適な圧縮技術は、クラスタリングによって実装されるベクトル量子化（VQ）です。データベースはクラスタリングされ、最も「有望な」クラスタが取得されます。VAファイル、ツリーベースのインデックス、シーケンシャルスキャンに比べて大きな改善が見られました。^{[ 22 ] [ 23 ]}また、クラスタリングとLSHの類似点にも注目してください。