R* 트리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. R-트리와의 차이점
- 2.1. 겹침 최소화 전략
- 2.2. 분할 알고리즘
3. 성능
4. 알고리즘 복잡도
참조

1. 개요

R* 트리는 R-트리의 개선된 버전으로, 공간 데이터 인덱싱을 위한 트리 자료구조이다. R-트리와 달리 최소 경계 사각형(MBR)의 넓이뿐만 아니라 겹침 영역도 줄이는 것을 목표로 한다. 노드 오버플로우 시 일부 자식 노드를 루트 노드에 재삽입하는 강제 재삽입을 통해 겹침을 최소화하며, 향상된 분할 알고리즘을 사용하고 재삽입 방법을 통해 기존 트리를 최적화한다. R* 트리는 R-트리보다 향상된 성능을 제공하며, 질의 및 삭제 연산의 복잡성은 R-트리와 동일하다.

더 읽어볼만한 페이지

트리 구조 - 덴드로그램
덴드로그램은 데이터 분석에서 데이터 포인트 간 계층적 관계를 시각적으로 표현하는 나무 형태의 다이어그램으로, 군집 분석에서 클러스터 간 유사성을 나타내기 위해 활용되며 다양한 분야에 응용된다.
트리 구조 - 프림 알고리즘
프림 알고리즘은 그래프의 최소 비용 신장 트리를 찾는 탐욕 알고리즘으로, 최소 가중치를 가진 간선을 선택하여 트리를 확장하며, 시간 복잡도는 사용되는 자료 구조에 따라 달라진다.

R* 트리
기본 정보
고안자	노르베르트 베크만, 한스-페터 크리겔, 랄프 슈나이더, 베른하르트 제거
고안 연도	1990년
성능
삽입 (평균)	O(log n)
공간 (평균)	O(n)
공간 (최악)	O(n)
검색 (평균)	O(log n)

2. R-트리와의 차이점

R 트리는 최소 경계 사각형(MBR)의 넓이만을 최소화하려 했지만, R*-트리는 겹침 영역 또한 줄이고자 했다. R*-트리는 노드 분할 시 강요된 재삽입(forced reinsertion) 등의 방법을 사용하여 노드의 겹침을 최소화한다.

2. 1. 겹침 최소화 전략

R-트리는 최소 경계 사각형(MBR)의 넓이만을 최소화하려고 시도했지만, R*-트리는 겹침 영역 또한 줄이려고 시도한다. R*-트리는 꽉 찬 노드가 분리되어야 하는 경우, 그 노드의 자식 노드들 중 일부를 루트 노드에 다시 삽입하는 강요된 재삽입(forced reinsertion)을 통해 노드의 겹침을 최소화한다.

R-트리의 성능에 핵심적인 요소는 커버리지와 중첩의 최소화이다. 중첩은 데이터 쿼리 또는 삽입 시 트리의 둘 이상의 분기를 확장해야 함을 의미한다. 최소화된 커버리지는 가지치기 성능을 향상시켜 특히 음의 범위 쿼리의 경우 전체 페이지를 검색에서 더 자주 제외할 수 있게 한다. R*-트리는 수정된 노드 분할 알고리즘과 노드 오버플로우 시 강제 재삽입 개념을 조합하여 커버리지와 중첩을 모두 줄이려고 시도한다.^[1]

이는 R-트리 구조가 항목이 삽입되는 순서에 매우 민감하여, 삽입으로 구축된 구조(대량 로드 방식이 아닌)가 최적이 아닐 수 있다는 관찰에 기반한다. 항목을 삭제하고 재삽입하면 원래 위치보다 더 적절한 트리의 "위치"를 "찾을" 수 있다.^[1]

노드가 오버플로우되면 해당 항목의 일부가 노드에서 제거되어 트리에 다시 삽입된다. (후속 노드 오버플로우로 인한 무한한 재삽입 연쇄를 방지하기 위해, 새 항목을 삽입할 때 트리의 각 레벨에서 재삽입 루틴을 한 번만 호출할 수 있다.) 이렇게 하면 노드에 더 잘 클러스터링된 항목 그룹이 생성되어 노드 커버리지가 감소한다. 또한 실제 노드 분할이 종종 연기되어 평균 노드 점유율이 상승한다. 재삽입은 노드 오버플로우 시 트리거되는 점진적 트리 최적화 방법으로 볼 수 있다.^[2]

R*-트리는 분할의 품질을 정량화할 수 있는 세 가지 메트릭을 설명한다. 이는 R*-트리와 R-트리 간에 공통적으로 사용되는 중첩(두 클러스터의 경계 상자의 교차 면적), 영역 값(두 클러스터 경계 상자의 영역 합), 여백 값(두 클러스터 경계 상자의 둘레 합)이다.^[3]

2. 2. 분할 알고리즘

R*-트리는 분할 품질을 정량화하기 위해 겹침(overlap), 영역(area), 여백(margin)의 세 가지 메트릭을 사용한다. 겹침은 두 클러스터의 경계 상자가 교차하는 면적으로 정의된다. 영역 값은 두 클러스터 경계 상자의 영역 합이고, 여백 값은 두 클러스터 경계 상자의 둘레 합이다. R*-트리는 R 트리와 달리 겹침 영역을 줄이고자 시도한다.

3. 성능

R*-트리는 다음과 같은 특징으로 인해 R-트리보다 향상된 성능을 제공한다.

향상된 분할 휴리스틱은 더 직사각형에 가까운 페이지를 생성하여 많은 응용 분야에 더 적합하다.
재삽입 방법은 기존 트리를 최적화하지만 복잡성을 증가시킨다.
점 데이터와 공간 데이터를 동시에 효율적으로 지원한다.

4. 알고리즘 복잡도

R* 트리는 질의 및 삭제 연산에 대해 일반 R-트리와 동일한 알고리즘을 사용한다. 삽입 전략은 R-트리의 선형 분할 전략( $\mathcal{O}(M)$ )보다 복잡한 $\mathcal{O}(M \log M)$ 이지만, $M$ 개의 객체에 대한 페이지 크기에 대한 2차 분할 전략( $\mathcal{O}(M^2)$ )보다는 덜 복잡하며 총 복잡성에 거의 영향을 미치지 않는다. 재삽입은 트리의 최대 한 개의 분기에만 영향을 미치므로, $\mathcal{O}(\log n)$ 의 복잡도를 가지며 이는 일반 R-트리에서 분할을 수행하는 것과 유사하다. 따라서 전체적으로 R* 트리의 복잡도는 일반 R-트리와 동일하다.

전체 알고리즘 구현에는 여기서 다루지 않은 많은 코너 케이스와 동점 상황 처리가 필요하다.

참조

_[1] 서적 Proceedings of the 1990 ACM SIGMOD international conference on Management of data - SIGMOD '90 https://infolab.usc.[...]
_[2] 서적 Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84 http://www-db.deis.u[...]
_[3] 간행물 New linear node splitting algorithm for R-trees Springer

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com