最近傍検索 (NNS) は、データベースまたはデータ セット内の特定のクエリ ポイントに最も近いポイント (またはポイント セット) を見つけるアルゴリズム問題です。この概念は、機械学習、データ マイニング、コンピューター ビジョン、地理情報システムなどの多くの分野で重要です。機械学習では、最近傍検索は k 近傍 (k-NN) アルゴリズムの中核であり、未知のサンプルに最も類似したトレーニング サンプルを見つけて分類または回帰分析を実行します。コンピューター ビジョンの分野では、特徴ベクトルを比較して最も一致する画像または特徴点を見つけることにより、特徴マッチングやオブジェクト認識に使用されます。また、地理情報システムでは、最近傍検索は、最寄りのレストランやガソリン スタンドの検索など、特定の地理的位置の近くにある関連エンティティを特定するのに役立ちます。
最近傍検索が直面する主な課題の 1 つは、「次元の呪い」と呼ばれる高次元データの処理です。データの次元が増加すると、データ点間の距離の違いが目立たなくなり、検索効率が急激に低下します。さらに、データセットのサイズが大きくなるにつれて、最近傍データを計算するコストも増加します。これらの問題を解決するために、研究者は、kd ツリーや R ツリーなど、検索効率を大幅に向上させるさまざまなインデックス構造を開発しました。