Nearest neighbor search
최근접 이웃 탐색(영어: nearest neighbor search)은 가장 가까운 (또는 가장 근접한) 점을 찾기 위한 최적화 문제이다. 근접 탐색(proximity search), 유사도 탐색(similarity search), 최근접 점쌍 문제(closest point search)라고도 불린다. 근사(近似)라는 개념은 보편적으로 물체와 물체가 덜 유사할수록 그 함수의 값은 커지는 상이(相異) 함수에 의해서 표현된다. 엄밀하게, 최근접 이웃 탐색 문제는 다음과 같이 정의된다: 공간 M에서의 점들로 이루어진 집합 S 가 주어졌을 때, 쿼리점 q ∈ M에 대해 S 안에서 가장 q와 가까운 점을 찾는다. 도널드 커누스는 그의 저서 《컴퓨터 프로그래밍의 예술》(1973) 제 3권에서 사람들의 거주지를 가장 가까운 우체국에 배정하는 프로그램이라는 의미에서 이를 우체국 문제라고 명명했다. 이 문제의 직접적인 일반화 문제로써는, k 개의 가장 가까운 점을 찾는 K-최근접 이웃 알고리즘이 있다.
보편적으로, M은 거리 공간이고 상이(相異)도는 대칭성을 갖고 삼각 부등식을 만족하는 거리 계측에 의해 표현된다. 이보다도 일반적으로 표현하자면, M은 d차원의 벡터 공간이고 상이도는 유클리드 거리, 맨해튼 거리 등을 사용해 계측한다. 그러나 상이함수는 임의성을 갖기 때문에, 예를 들면 대칭성을 띄지 않고 삼각 부등식을 만족하지 않는 브레그만 발산(Bregman Divergence)등을 사용하여 정의할 수 있다.