임의의 메트릭을 사용하여 KD-Tree를 검색 할 수 있습니까?

Question

가장 가까운 이웃 검색을 수행하기 위해 kd-tree을 구현했습니다. 나는 Euclidean distance이 아닌 다른 거리 메트릭으로 놀고 싶어합니다. kd-tree에 대한 나의 이해는 메트릭이 유클리드가 아닌 경우 신속한 kd-tree 검색으로 정확한 검색을 보장 할 수 없다는 것입니다. 즉, 유클리드가 아닌 데이터를 사용하려는 경우 새로운 데이터 구조 및 검색 알고리즘을 구현해야 할 수도 있습니다. 내 검색에 대한 새로운 측정 항목을 제공합니다.

1. 가 kd-tree를 사용하여 영구적으로 날이 Euclidean distance에 묶어 않습니다

   나는이 개 질문이?

2. 그렇다면 임의의 다른 알고리즘을 시도해야합니까? metrics? 다른 데이터 구조를 구현할 시간이별로 없지만 다른 구조는 cover trees과 vp-trees입니다. 당신이 링크 된 위키 백과 페이지에 설명 된

Answer 1

가장 가까운 이웃의 검색 절차는 확실히 당신이 주어진 통계에 대한 동등한 기하학적 개체 "hypersphere"를 교체하고 각 초평면을 테스트 제공, 다른 거리 측정에 일반화 될 수있는 이 개체와 교차점.

예 : 맨하탄 거리 (즉, 벡터 구성 요소의 모든 차이의 절대 값 합계)를 사용하는 경우 하이퍼 스페어는 (다차원) 다이아몬드가됩니다. (2D로 시각화하는 것이 가장 쉽습니다. 현재 가장 가까운 이웃이 거리 x의 쿼리 포인트 p에있는 경우 다른 초평선 뒤에있는 인접한 이웃은 너비와 높이가 2x 인 다이아몬드 모양과 교차해야하며 p을 중심으로 함). 이것은 초평면 교차 테스트를 코딩하기가 더 어렵거나 실행 속도가 느려지 게 만들지 만 일반적인 원칙은 여전히 ​​적용됩니다.

Answer 2

나는 당신이 유클리드 거리에 묶여 있다고 생각하지 않는다. j_random_hacker가 말했듯이 아마도 맨해튼 거리를 사용할 수 있지만, 데카르트 좌표로 표현할 수있는 지오메트리에 묶여 있다고 확신한다. 예를 들어, kd 트리를 사용하여 메트릭 공간을 인덱싱 할 수 없습니다.