볼트리

컴퓨터 과학에서 볼트리, 볼트리^[1] 또는 미터법 트리는 다차원 공간에서 포인트를 구성하기 위한 공간 분할 데이터 구조다.볼 트리는 데이터 포인트를 "볼"로 알려진 교차 하이퍼스피어의 중첩 집합으로 분할한다는 사실에서 이름을 얻는다.그 결과 데이터 구조는 특히 가장 가까운 이웃 검색 등 여러 애플리케이션에 유용하게 사용할 수 있는 특성을 가지고 있다.

비공식 설명

볼 트리는 모든 노드가 검색할 포인트의 하위 집합을 포함하는 D-차원 하이퍼스피어 또는 볼을 정의하는 이진 트리다.트리의 각 내부 노드는 데이터 포인트를 서로 다른 볼과 연관된 두 개의 분리 세트로 분할한다.볼 자체가 교차하는 동안, 각 점은 볼의 중심으로부터의 거리에 따라 칸막이에 있는 하나 또는 다른 공에 할당된다.트리의 각 리프 노드는 볼을 정의하고 해당 볼 내부의 모든 데이터 포인트를 열거한다.

트리의 각 노드는 하위 트리의 모든 데이터 포인트를 포함하는 가장 작은 볼을 정의한다.이것은 공 바깥의 주어진 시험 지점 t에 대해, 나무의 볼 B의 어떤 지점까지의 거리가 t에서 공 표면까지의 거리보다 크거나 같은 유용한 특성을 발생시킨다.공식:

${\displaystyle D^{B}(t)={\begin{cases}\max( t-B.pivot -B.radius,D^{B.parent}),&{\text{if }}B\neq Root\\\max( t-B.pivot -B.radius,0),&{\text{if }}B=Root\\\end{cases}}}$

여기서 $D{\displaystyle {}^{}}$ ${\displaystyle B{}^{}}$( t${\displaystyle }$) ${\displaystyle D^{B}(t)}$은(는) 볼 B의 어떤 지점에서 어떤 지점 t까지의 최소 가능한 거리다$$.

볼트리는 M-트리와 관련이 있지만 이진 분할만 지원하는 반면, M-트리에서는 각 $레벨$이 m ${\displaystyle$ m$}~$$[\displaystyle 2m]$로 분할되어 셸로우 트리 구조로 이어지기 때문에 거리 연산이 더 적게 필요하며, 일반적으로 더 빠른 쿼리를 산출한다.게다가, M-tree는 페이지로 구성된 디스크에 더 잘 저장될 수 있다.또한 M-트리는 쿼리를 가속화하기 위해 미리 계산된 상위 노드와의 거리를 유지한다.

밴티지 포인트 트리도 비슷하지만 두 개의 공을 사용하는 대신 한 개의 공, 그리고 남은 데이터로 2진법으로 쪼개진다.

건설.

많은 볼 트리 구성 알고리즘을 사용할 수 있다.^[1]그러한 알고리즘의 목적은 평균적인 경우에서 원하는 유형(예: 가장 가까운 이웃)의 질의를 효율적으로 지원하는 트리를 생산하는 것이다.이상적인 트리의 구체적인 기준은 답변되는 질문의 유형과 기초 데이터의 분포에 따라 달라질 것이다.그러나 효율 트리의 일반적으로 적용 가능한 척도는 내부 노드의 총 볼륨을 최소화하는 척도다.실제 데이터 세트의 다양한 분포를 고려할 때 이는 어려운 작업이지만 실제로 데이터를 잘 분할하는 여러 가지 경험적 발견이 있다.일반적으로 나무 건설 비용과 이 측정기준에 의해 달성되는 효율성 사이에는 절충이 있다.^[2]

이 절에서는 이러한 알고리즘 중 가장 간단한 알고리즘을 간략히 설명한다.스테판 오모훈드로에 의해 5개의 알고리즘에 대한 보다 심도 있는 논의가 이루어졌다.^[1]

k-d 시공 알고리즘

이러한 가장 간단한 절차는 k-d 트리를 건설하는 데 사용되는 프로세스와 유사하게 "k-d 건설 알고리즘"이라고 불린다.이것은 오프라인 알고리즘, 즉 한 번에 전체 데이터 집합에서 작동하는 알고리즘이다.트리는 데이터 포인트를 재귀적으로 두 세트로 분할하여 하향식 빌드된다.분할은 점의 범위가 가장 큰 단일 차원을 따라 선택되며, 세트는 해당 차원을 따라 모든 점의 중위수 값으로 분할된다.각 내부 노드에 대한 분할을 찾으려면 해당 노드에 포함된 샘플 수에서 선형 시간이 필요하며, 시간 $복잡성$이${\displaystyle }$O(${\displaystyle n}$ ${\displaystyle log}$ n${\displaystyle }$) ${\displaystyle O(n\,\log \,n)}$인 알고리즘이 생성된다$.$ 여기서 n은 데이터 포인트 수입니다.

가성음

함수 construct_balltree 입력: D, 데이터 포인트 배열.출력: B, 생성된 볼 트리의 루트.단일 점이 남아 있으면 D 반환 B의 단일 점을 포함하는 잎 B를 생성한다. 그렇지 않으면, c를 최대 확산 치수로 선택한다. L을 고려하여 선택한 중심점이 되도록 한다. R은 치수 C를 따라 중앙값의 왼쪽과 오른쪽에 놓여 있는 점의 집합이 된다. B는 다음과 같이 두 개의 자식과 함께 생성된다.B.pivot :=p.child1 := construct_balltree(L), B.child2 := construct_balltree(R) : construct_balltree(R), 엔드 기능이 끝나면 어린이들 사이에서 B.radius를 p로부터 최대 거리로 되돌리도록 한다.

가장 근접한 검색

볼 트리의 중요한 적용은 가장 가까운 이웃 검색 질의의 속도를 높이는 것으로, 목적은 특정 시험 지점에 가장 가까운 k 포인트를 특정 거리 측정 기준(예: 유클리드 거리)으로 찾는 것이다.KNS1이라고도 불리는 간단한 검색 알고리즘은 볼 트리의 거리 특성을 이용한다.특히 알고리즘이 테스트 포인트 t로 데이터 구조를 검색하고 있고, 지금까지 접하는 지점 중 t에 가장 가까운 p점을 이미 봤다면, 나머지 검색에서 볼이 p보다 t에서 더 먼 하위 트리는 무시할 수 있다.

설명

가장 가까운 볼 트리 알고리즘은 루트에서 시작하여 깊이 우선 순서에 따라 노드를 검사한다.검색하는 동안 알고리즘은 지금까지 발견된 k개의 가장 가까운 지점의 Q를 나타내는 최대 우선 순위 대기열(흔히 힙으로 구현)을 유지한다.각 노드 B에서는 우선 순위 대기열의 업데이트된 버전을 반환하기 전에 세 가지 작업 중 하나를 수행할 수 있다.

1. 시험 지점 t에서 현재 노드 B까지의 거리가 Q의 가장 먼 지점보다 크면 B를 무시하고 Q를 반환한다.
2. B가 리프 노드인 경우, B에 열거된 모든 지점을 스캔하고 가장 가까운 대기열을 적절하게 업데이트하십시오.업데이트된 큐를 반환하십시오.
3. B가 내부 노드인 경우 알고리즘을 B의 두 자녀에 대해 반복적으로 호출하여 중심이 t에 가까운 아이를 먼저 검색하십시오.각 호출이 차례로 업데이트되면 큐를 반환하십시오.

위의 지점 3에서 설명한 순서대로 재귀적 검색을 수행하면 추가 어린이가 검색 중에 완전히 제거될 가능성이 높아진다.

가성음

함수 knn_search는 입력: t, 쿼리 k의 목표 지점, Q를 검색할 t의 가장 가까운 이웃 수, 트리 출력에서 대부분의 k 지점 B, 노드 또는 볼에 포함된 최대 우선 순위 대기열: 거리(t, B.pivot) - B.radiu인 경우 B 내에서 가장 가까운 이웃 k를 포함하는 Q.S다음 Q는 그대로 반환합니다;만약 size(Q)을 distance(t, Q.first) 다음 Q에 p을 첨가하여 끝나면 만약 반복되는 다른 child1이 기를 알려 준 다음 Q끝에서 가장 먼 이웃을 제거하 k 다른 B의 각 점 p를 위해 B는 리프 노드 다음 만약 distance(t, p)<>distance(t, Q.first)≥.ld 고개를 끄덕이다e child2에 가장 가까운 t knn_search(t, k, Q, child1) knn_search(t, k, Q, child2)가[2] 반환 Q 엔드 기능인 경우 가장 먼 하위 노드가 되도록 한다.

퍼포먼스

다른 여러 데이터 구조와 비교하여 볼 트리는 특히 치수의 수가 증가함에 따라 가장 가까운 검색 문제에서 상당히 좋은 성능을 발휘하는 것으로 나타났다.^[3][4]그러나 특정 애플리케이션에 가장 가까운 데이터 구조는 데이터의 차원성, 데이터 지점 수 및 기본 구조에 따라 달라진다.

참조