정렬된 파티션에 기반한 빠른 k 최근접 이웃 탐색 알고리즘

우리는 각 투영 축의 훈련 샘플의 정렬된 목록을 기반으로 정렬된 파티션이라고 임시로 명명된 빠른 최근접 이웃 탐색 알고리즘을 제안합니다. 정렬된 파티션은 두 가지 속성을 포함하는데, 하나는 검색 영역을 제한하기 위한 정렬이고, 다른 하나는 실제 거리 계산 없이 원치 않는 샘플을 거부하기 위한 파티셔닝입니다. 제안된 알고리즘이 상수 예상 시간 안에 k 최근접 이웃을 찾을 수 있음이 입증되었습니다. 시뮬레이션 결과, 이 알고리즘은 분포에 무관하며, 평균적으로 10,000개의 샘플 중에서 가장 가까운 이웃을 찾기 위해 4.6회의 거리 계산만이 필요했습니다.