우선 순위 R-트리

우선 순위 R-트리는 공간 트리 R-트리에 대한 최악의 경우 증상 없이 최적의 대안이다.2004년 기사에서 아르게, 드 버그, 하베르코트, K.가 처음 제안한 것이다.^[1]우선순위가 정해진 R-트리(R-tree)는 기본적으로 주어진 물체의 N-차원 경계 볼륨(최소 경계 직사각형 - MBR이라 함)을 N-dimensions의 점으로 정의한다는 점에서 k-차원 트리와 r-트리 사이의 잡종이다.우선 순위가 매겨진 용어는 나무의 모든 가지에 포함된 각 치수의 가장 극단적인 값을 나타내는 네 가지 우선순위 리브의 도입에서 유래한다.하위 분지를 통과하여 창 쿼리에 응답하기 전에 우선 순위가 매겨진 R-tree는 우선 우선 우선순위 노드의 중복을 검사한다.하위 분지는 질의 첫 번째 차원의 최소값이 하위 분지의 값보다 높은지 여부를 확인하여 통과(구축)된다.이렇게 하면 경계 상자의 첫 번째 차원 값으로 빠른 인덱싱에 접근할 수 있다.

퍼포먼스

Arge et al. writes that the priority tree always answers window-queries with ${\displaystyle O\left(\left({\frac {N}{B}}\right)^{1-{\frac {1}{d}}}+{\frac {T}{B}}\right)}$ I/Os, where N is the number of d-dimensional (hyper-) rectangles stored in the R-tree, B is the disk block size, and T is t그는 출력 사이즈.

치수

In the case of ${\displaystyle d=2}$ the rectangle is represented by ${\displaystyle \,((x_{min},y_{min}),(x_{max},y_{max}))}$ and the MBR thus four corners ${\displaystyle \,(x_{min},y_{min},x_{max},y$$_{max}}$.

참고 항목

• 경계 볼륨 계층 구조
• B-트리
• R-트리

참조