KD-트리를 검색하기 위해 임의의 측정항목을 사용할 수 있나요?

Question

방금 구현을 마쳤습니다. kd-트리 가장 가까운 이웃 검색을 빠르게 수행합니다.저는 거리 측정법 이외의 다른 거리 측정법을 가지고 놀고 싶습니다. 유클리드 거리.kd-트리에 대해 내가 이해한 바는 메트릭이 유클리드가 아닌 경우 빠른 kd-트리 검색이 정확한 검색을 보장하지 않는다는 것입니다. 즉, 시도하려면 새로운 데이터 구조와 검색 알고리즘을 구현해야 할 수도 있습니다. 내 검색에 대한 새로운 측정항목을 알아보세요.

두 가지 질문이 있습니다.

1. 사용합니까? kd-트리 나를 영원히 묶어줘 유클리드 거리?
2. 그렇다면 임의 작업을 위해 어떤 다른 종류의 알고리즘을 시도해야 합니까? 측정항목?다양한 데이터 구조를 구현할 시간이 많지 않지만 제가 생각하고 있는 다른 구조에는 다음이 포함됩니다. 나무를 덮다 그리고 vp-나무.

Answer 1

연결된 Wikipedia 페이지에 설명된 최근접 검색 절차는 "초구체"를 주어진 메트릭에 해당하는 기하학적 개체로 바꾸고 각 초평면이 이 개체와 교차하는지 테스트하는 경우 확실히 다른 거리 측정법으로 일반화될 수 있습니다.

예:대신 맨해튼 거리를 사용하는 경우(예:벡터 구성요소의 모든 차이의 절대값의 합), 초구체는 (다차원) 다이아몬드가 됩니다.(이것은 2D로 시각화하는 것이 가장 쉽습니다. 현재 가장 가까운 이웃이 멀리 떨어져 있는 경우 엑스 쿼리 포인트에서 피, 다른 초평면 뒤에 있는 더 가까운 이웃은 너비와 높이가 2x이고 중앙에 있는 다이아몬드 모양과 교차해야 합니다. 피).이로 인해 초평면 교차 테스트를 코딩하기가 더 어려워지거나 실행 속도가 느려질 수 있지만 일반 원칙은 여전히 ​​적용됩니다.

Answer 2

J_random_hacker가 말한 것처럼 맨해튼 거리를 사용할 수있을 것입니다. 그러나 나는 당신이 직교 좌표로 표현할 수있는 기하학에 묶여 있다고 확신합니다. 예를 들어 KD-Tree를 사용하여 메트릭 공간을 색인 할 수 없었습니다.