커버 트리

표지 트리는 컴퓨터 공학에서 가장 가까운 이웃의 검색 속도를 높이기 위해 특별히 고안된 데이터 구조의 한 유형이다.그것은 항법망 데이터 구조를 정교하게 다듬은 것이며, 본질적으로 저차원 데이터를 인덱싱하기 위해 개발된 다양한 다른 데이터 구조와 관련이 있다.^[1]

트리는 루트 포인트를 포함하는 최상위 수준과 메트릭 공간의 모든 점을 포함하는 하위 수준을 가진 수준의 계층 구조로 생각할 수 있다.각 수준 C는 나무가 하강할 때 1씩 감소하는 정수 값 i와 연관된다.커버 트리의 각 레벨 C에는 다음과 같은 세 가지 중요한 특성이 있다.

• 중첩: ${\displaystyle C_{i}\subseteq C_{i-1}$
• 커버:For every point ${\displaystyle p\in C_{i-1}}$, there exists a point ${\displaystyle q\in C_{i}}$ such that the distance from ${\displaystyle p}$ to ${\displaystyle q}$ is less than or equal to ${\displaystyle 2^{i}}$ and exactly one such ${\displaystyle q}$ is a parent$[\displaystyle p}$의$.$
• 분리:모든 포인트 $p{\displaystyle }$ ,${\displaystyle q}$ ${\displaystyle \in }$ ${\displaystyle C_{}}$ i ${\$에 대해$,$ $p{\displaystyle }$ ${\displaystyle p}$에서 $q{\displaystyle }$ ${\displaystyle q}$까지의 거리는 $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle i^{}}$ ${\$ 2$^{i}$보다 크다$$$.$

복잡성

찾다

다른 메트릭 트리와 마찬가지로 커버 트리는 $O{\displaystyle (}$ ${\displaystyle \eta }$ ∗ ${\displaystyle \ast }$ ${\displaystyle \log }$ $){\displaystyle O(\eta *\log {n})$에서 가장 가까운 인접 검색을 허용하며, 여기서$$ $\eta {\displaystyle }$ ${\displaystyle \eta}$은 데이터 집합의 차원성과 연관된 상수이고 n은 카디널리티입니다.비교하자면 기본 선형 검색에는 O (${\displaystyle n}$) ${\displaystyle$ O$(n$이 필요하며, $이$는 n ${\displaystyle$ n$}$에 훨씬 더 심하게 의존한다. 그러나$$고차원 메트릭 공간에서는 $in{\displaystyle }$ ${\displaysty \eta }$ 상수가$$ 비삼각적이므로 복잡도 분석에서 무시할 수 없다.다른 메트릭 트리와 달리 커버 트리는 데이터 집합의 확장 상수 또는 두 배 상수(추정 NN 검색의 경우)를 기반으로 하는 상수에 이론적으로 바인딩되어 있다.검색 제한 시간은 $O{\displaystyle ({}^{}}$ ${\displaystyle {12}^{}}$ ${\displaystyle \log logn}$) ${\displaystyle O(c^{12}\log {n})$이며, $여기$서 c ${\displaystyle c}$은(는) 데이터 집합의 확장 상수입니다.

삽입하다

비록 커버 트리가 순진한 접근법보다 더 빠른 검색을 제공하지만, 이러한 이점은 데이터 구조를 유지하는데 드는 추가 비용에 의해 평가되어야 한다.순진한 접근방식에서 데이터 집합에 새로운 점을 추가하는 것은 순전히 순서가 보존될 필요가 없기 때문에 사소한 것이지만 표지 트리에서 $O{\displaystyle ({}^{}}$ ${\displaystyle {6\mathrm{}}^{}}$ ${\displaystyle \log logn}$ )${\displaystyle O(c^{6}\log {n})$ 시간이$$ 걸릴 수 있다.그러나 이것은 상행선이며, 실제로 성과를 향상시키는 듯한 기법이 일부 구현되었다.^[2]

공간

표지 트리는 반복된 점을 추적하기 위해 암묵적 표현을 사용한다.따라서 O(n) 공간만 있으면 된다.

참고 항목

• 가장 가까운 이웃 검색
• kd-트리

참조

메모들

참고 문헌 목록

• 알리나 비겔지머, 샴 카케이드, 존 랭포드.가장 가까운 이웃을 위해 나무를 덮어라.Proc.기계학습 국제회의(ICML), 2006.
• JL의 커버 트리 페이지.존 랭포드의 페이지는 서류와 코드로 연결된다.
• GitHub에 C++ 커버 트리 구현.
• Java의 커버 트리 구현.