最近傍探索

最近傍探索（英: Nearest neighbor search, NNS）は、距離空間における最も近い点を探す最適化問題の一種、あるいはその解法。近接探索（英: proximity search）、類似探索（英: similarity search）、最近点探索（英: closest point search）などとも呼ぶ。問題はすなわち、距離空間 M における点の集合 S があり、クエリ点 q ∈ M があるとき、S の中で q に最も近い点を探す、という問題である。多くの場合、M には d次元のユークリッド空間が採用され、距離はユークリッド距離かマンハッタン距離で測定される。低次元の場合と高次元の場合で異なるアルゴリズムがとられる。

ドナルド・クヌースは、The Art of Computer Programming Vol.3（1973年）で、これを郵便局の問題で表した。これはすなわち、ある住所に最も近い郵便局を求める問題である。

解法

最近傍探索問題の解法としては、様々なものが提案されている。そのアルゴリズムの品質と利便性は、クエリへの応答にかかる時間とデータ構造が使用するメモリ量で判断される。直観的には、次元の呪いと呼ばれる特徴があるため、あらゆる場合に最適な解法は存在しないと言われている。

線形探索

最も単純な解法は、クエリで示された点とデータベース内の他の全ての点との距離を全部計算して、最も近いものを探すことである。データベースが小さい場合は問題ないが、その大きさや次元が増大すると急激に遅くなる。線形探索の処理時間は O(Nd) であり、N は S の基数、d は S の次元である。検索時にデータ構造は特に必要ないので、データベース以外の余分なメモリ消費はない。

空間分割

1970年代から、この問題に分枝限定法が適用されるようになった。ユークリッド空間の場合、この手法は空間索引または空間アクセス法として知られている。NNS問題を解くための空間分割法もいくつか考案された。最も単純な手法としてはkd木がある。これは、探索空間を再帰的に半分に2分割していくものである。クエリは、この木を根から葉に向かって辿っていくことで処理される（各ノードでどちらに行くかをクエリの内容と比較して判断する）。一定次元でのクエリ処理時間は O(log N) となる。R木というデータ構造も最近傍探索用に設計された。

一般の距離空間における分枝限定法の適用例として、VP木やBk木がある。

局所性鋭敏型ハッシュ

局所性鋭敏型ハッシュ（LSH）は、距離空間内の各点に距離空間的操作を施すことで、グループ分けする技法である。ある距離尺度で互いに近い点は同じグループになる確率が高くなる。

派生

k近傍法は、クエリに最も近い方から k 個の近傍を特定する。
近似最近傍探索 (英: approximate nearest neighbor, ANN) は、次元の呪いへの対策として最近特に人気がある。
最近傍距離比 (英: nearest neighbor distance ratio) とは、距離の絶対値ではなく距離と距離の比を用いる方式。内容に基づく画像検索（CBIR）で使われることがある。より一般的には、いくつかのマッチング問題と関連する。
最近点対問題 (英: closest pair problem)とは、点集合の中から最も近い距離の点のペアを1組捜すアルゴリズムであり、 $O(n\log n)$ で求められる。低次元空間のアルゴリズムは『アルゴリズムイントロダクション』(T. コルメン)や『アルゴリズムC』(R. セジウィック)などの本に掲載されている。
全最近傍問題 (英: all nearest neighbors, ANN) とは、点集合の中から各点の最も距離の近い点を探すアルゴリズムであり、近傍点1つを探すならば $O(n\log n)$ 、近傍点m個を探す問題ならば $O(mn\log n)$ で求まる^[1]。

応用

最近傍探索は、以下のような様々な分野で使われている。

参考文献

Arya, S., D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions. Journal of the ACM, vol. 45, no. 6, pp. 891-923
Zezula, P., Amato, G., Dohnal, V., and Batko, M. Similarity Search - The Metric Space Approach. Springer, 2006. ISBN 0-387-29146-6

^ Vaidya, P. M. (1989). “An O(n log n) Algorithm for the All-Nearest-Neighbors Problem”. Discrete and Computational Geometry 4 (1): 101–115. doi:10.1007/BF02187718.

外部リンク

Nearest Neighbors and Similarity Search - 最近傍探索を中心としたウェブサイト
Metric Spaces Library - 距離空間インデクシングのためのC言語ライブラリ（オープンソース）
ANN - 近似最近傍探索のためのライブラリ
STANN - スレッドセーフな近似最近傍探索ライブラリ（C++）
MESSIF - 距離類似探索実装フレームワーク（Metric Similarity Search Implementation Framework）

[Vaidya-1] Vaidya, P. M. (1989). “An O(n log n) Algorithm for the All-Nearest-Neighbors Problem”. Discrete and Computational Geometry 4 (1): 101–115. doi:10.1007/BF02187718.

[1]