정확한 Nearest Neighbor를위한 구조와 근사 버전을위한 구조 중 어느 것입니까?

Question

LSH는 ANN에 널리 사용되는 알고리즘입니다.

k-d 트리가 아마도 NN을 정확하게 해결하기위한 가장 일반적인 솔루션 일 수 있습니다.

그러나 this survey를 읽고 나는이 구조를 발견하고 나는 NN 또는 ANN 해결하기 위해있는 것을 이해하지 않는다 :

• 쿼드/옥트 트리
• 볼 트리
• R-트리
• M-트리

나는 ANN에 전념 어떤 설문 조사를 발견하지 않았다, 그래서 나는이 모든 NN과 만족을 위해 있다고 생각 (비 메트릭 공간에는 사용할 수 없습니다).

Answer 1

먼저 Nearest Neighbor Search (NNS)에 quadtree, Ball tree, R-tree 및 M-tree을 사용할 수 있습니다.

구조가 NNS를 지원할 수 있다면 은 근처의 근사치 검색을 지원할 수 있습니다.

예를 들어 kd-tree를 사용하면 더 잘 알 수 있습니다. 쿼리에 대한 답변 일 수있는 포인트 후보를 수집합니다. 을 모두으로 선택하면 가장 가까운 이웃 쿼리에 응답 할 수 있습니다. 의 후보를 확인하면 대략적인 Nearest Neighbor 쿼리에 응답 할 수 있습니다.

희망 하시겠습니까? :)