R 트리

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

1. 개요
2. R-트리의 기본 개념
3. R-트리의 변종
4. 알고리즘
참조

1. 개요

R-트리는 공간 데이터를 효율적으로 관리하기 위한 트리 자료구조의 일종이다. 객체를 최소 경계 사각형(MBR)으로 묶어 계층적으로 구성하며, B-트리와 유사하게 균형 잡힌 검색 트리를 유지한다. R-트리는 대용량 데이터베이스에 적합하며, 검색, 삽입, 삭제, 전체 로드(Bulk-loading) 등의 연산을 지원한다. R-트리의 변종으로는 R* 트리, R+ 트리, 힐베르트 R-트리, 우선순위 R-트리 등이 있다.

더 읽어볼만한 페이지

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

R 트리
개요
종류	트리
자료구조 종류	공간 색인
고안자	안토닌 구트만
고안년도	1984년
공간 복잡도
검색 복잡도
평균	O(logM n)
최악	O(n)
삽입 복잡도
최악	O(n)
삭제 복잡도

2. R-트리의 기본 개념

R-트리는 공간 객체를 최소 경계 사각형(MBR, Minimum Bounding Rectangle)으로 감싸서 계층적으로 구성하는 데이터 구조이다. 이 구조는 근접한 객체를 그룹화하고, 트리 상위 레벨에서 해당 객체들을 MBR로 표현한다. R-트리의 "R"은 사각형(Rectangle)을 의미한다.

대부분의 트리와 마찬가지로, 교차, 포함, 최근접 이웃 탐색 등의 검색 알고리즘은 경계 상자를 사용하여 서브트리 내부를 검색할지 여부를 결정한다. 이러한 방식으로 검색 중에 트리의 대부분의 노드는 읽히지 않는다. B-tree처럼 R-tree는 대용량 데이터 집합과 데이터베이스에 적합하며, 필요할 때 노드를 메모리로 페이징할 수 있고, 전체 트리를 주 메모리에 유지할 수 없다. 데이터가 메모리에 맞더라도, R-tree는 실제 응용 프로그램에서 객체 수가 수백 개 이상일 때 모든 객체를 무작위로 확인하는 것보다 일반적으로 성능 이점을 제공한다.

R-tree의 핵심 어려움은 균형을 유지하면서(리프 노드가 같은 높이에 있음) 사각형이 너무 많은 빈 공간을 덮지 않고 너무 많이 겹치지 않도록(검색 중에 더 적은 서브트리를 처리해야 함) 효율적인 트리를 구축하는 것이다. 요소를 삽입하는 원래 아이디어는 경계 상자를 가장 적게 확대해야 하는 서브트리에 항상 삽입하는 것이다. 해당 페이지가 가득 차면 데이터는 각 최소 영역을 덮어야 하는 두 세트로 분할된다.

R-tree는 좋은 최악의 경우 성능을 보장하지 않지만 일반적으로 실제 데이터에서 잘 작동한다.^[7] 우선 순위 R-tree는 최악의 경우에도 최적의 성능을 보인다.^[8]

데이터가 R-tree로 구성되면, 주어진 거리 r 내의 이웃과 모든 점의 k 최근접 이웃은 공간 조인을 사용하여 효율적으로 계산할 수 있다.^[9]^[10] 이는 Local Outlier Factor와 같은 많은 알고리즘에 유용하다. DeLi-Clu,^[11] 밀도 연결 클러스터링은 R-tree 구조를 사용하여 OPTICS 클러스터링을 효율적으로 계산하는 클러스터 분석 알고리즘이다.

2. 1. 최소 경계 사각형 (MBR)

R-트리의 핵심 개념은 인접한 객체들을 묶어, 트리 상위 레벨에서 이 객체들을 최소 경계 사각형(MBR)으로 표현하는 것이다. R-트리의 "R"은 사각형(Rectangle)을 의미한다. 모든 객체는 이 경계 사각형 안에 위치하며, 경계 사각형과 교차하지 않는 쿼리는 포함된 객체와도 교차할 수 없다. 리프 레벨에서 각 사각형은 단일 객체를 나타내고, 상위 레벨에서는 점점 더 많은 객체를 포함한다. 이는 데이터 집합의 점진적으로 더 개략적인 근사치로 볼 수 있다.^[6]

R-트리는 계층적으로 중첩된, 서로 겹칠 수 있는 최소 외접 사각형(MBR)들로 공간을 분할한다. R-트리에서 각 노드의 항목 수는 가변적이지만, 미리 정의된 상한이 있다. 리프 노드가 아닌 각 항목에는 두 가지 데이터가 저장된다. 하나는 자식 노드를 가리키는 참조이고, 다른 하나는 해당 자식 노드의 모든 항목을 둘러싸는 외접 사각형 데이터이다.

삽입 및 삭제 알고리즘은 이러한 외접 사각형을 사용하여 가까운 요소들이 같은 리프 노드에 속하도록 한다. 특히, 새로운 요소를 삽입할 때, 어떤 최하층 외접 사각형에도 들어가지 않는 경우, 가장 확대가 작게 되는 외접 사각형에 대응하는 리프 노드에 속하도록 한다. 리프 노드의 각 항목에는 두 가지 데이터가 저장된다. 하나는 실제 데이터 요소에 대한 참조이며(참조가 아닌, 리프 노드 내에 직접 데이터 요소가 저장되는 경우도 있다), 다른 하나는 해당 데이터 요소를 둘러싸는 외접 사각형 데이터이다.

마찬가지로, 탐색 알고리즘(예: 교집합, 포함, 최근접)은 외접 사각형을 사용하여 자식 노드에 해당하는 외접 사각형 내부를 탐색해야 하는지 여부를 결정한다. 이렇게 하면 탐색 시 대부분의 노드를 검사할 필요가 없어진다.

2. 2. 노드 구조

R 트리의 각 노드는 가변적인 수의 항목을 포함한다(미리 정의된 최대값까지, 그리고 보통 최소 채우기 이상). 리프 노드가 아닌 노드 내의 각 항목은 두 가지 데이터를 저장한다. 하나는 자식 노드를 식별하는 방법(자식 노드에 대한 참조)이고, 다른 하나는 이 자식 노드 내의 모든 항목의 경계 상자(MBR)이다.

리프 노드는 각 자식에 필요한 데이터를 저장하며, 종종 자식을 나타내는 점 또는 경계 상자와 자식에 대한 외부 식별자를 저장한다. 점 데이터의 경우, 리프 항목은 점 자체일 수 있다. 다각형 데이터(대용량 다각형 저장이 필요한 경우가 많음)의 경우, 일반적인 설정은 트리 내에서 고유한 식별자와 함께 다각형의 MBR(최소 경계 직사각형)만 저장하는 것이다.^[6]

2. 3. 균형 트리

B-tree와 유사하게, R-tree 또한 균형 잡힌 검색 트리이며(따라서 모든 리프 노드는 동일한 깊이에 있다), 데이터를 페이지로 구성하며, 데이터베이스에서 사용되는 것처럼 디스크에 저장을 위해 설계되었다. 각 페이지는 최대 항목 수를 포함할 수 있으며, 종종

M

으로 표시된다. 또한 최소 채우기를 보장하지만(루트 노드 제외), 최대 항목 수의 30%–40%의 최소 채우기에서 최고의 성능이 경험되었다(B-tree는 50% 페이지 채우기를 보장하고, B*-tree는 66%를 보장한다). 그 이유는 B-트리에 저장된 선형 데이터와 달리 공간 데이터에 필요한 균형 조정이 더 복잡하기 때문이다.^[6]

3. R-트리의 변종

R-트리는 다양한 변종이 존재하며, 각 변종은 특정 응용 분야나 데이터 유형에 최적화되어 있다. 주요 변종으로는 R* 트리, R+ 트리, 힐베르트 R-트리, 우선순위 R-트리, X 트리 등이 있다.^[19]

3. 1. R* 트리

R* 트리는 R 트리의 가장 대표적인 변종 중 하나로, 삽입 및 분할 알고리즘을 개선하여 겹침을 최소화하고 검색 성능을 향상시켰다.^[19]

3. 2. R+ 트리

R* 트리와 유사하지만, R+ 트리는 최소 경계 사각형(MBR, Minimum Bounding Rectangle) 간의 겹침을 허용하지 않는다. 이로 인해 검색 성능은 향상될 수 있지만, 삽입 및 삭제 연산은 더 복잡해질 수 있다.^[19]

3. 3. 힐베르트 R-트리

공간 채움 곡선의 일종인 힐베르트 곡선을 사용하여 공간 객체를 정렬하고, 이를 기반으로 R-트리를 구성하는 변종이다.^[19]

3. 4. 우선순위 R-트리 (Priority R-tree)

우선순위 R-트리(Priority R-tree)는 2004년에 제안된 R-트리의 변종으로, 최악의 경우에도 최적의 성능을 보장한다.^[19] PR 트리는 요소의 편차가 일정한 데이터에서는 일반적인 R 트리와 동등한 성능을 보이지만, 더 극단적인 데이터에서는 매우 좋은 성능을 발휘한다.^[19]

4. 알고리즘

R-트리는 검색, 삽입, 삭제 등의 기본 연산을 지원한다. 대부분의 트리와 마찬가지로 검색 알고리즘(예: 교차, 포함, 최근접 이웃 탐색)은 비교적 간단하다. 핵심 아이디어는 경계 상자를 사용하여 서브트리 내부를 검색할지 여부를 결정하는 것이다. 이러한 방식으로 검색 중에 트리의 대부분의 노드는 절대 읽히지 않는다. B-트리처럼 R-tree는 대용량 데이터 집합과 데이터베이스에 적합하며, 필요할 때 노드를 메모리로 페이징할 수 있으며, 전체 트리를 주 메모리에 유지할 수 없다.

R-트리의 핵심 어려움은 균형을 유지하면서(리프 노드가 같은 높이에 있도록) 사각형이 너무 많은 빈 공간을 덮지 않고 너무 많이 겹치지 않게(검색 중에 더 적은 서브트리를 처리) 효율적인 트리를 구축하는 것이다. 효율적인 트리를 얻기 위해 요소를 삽입하는 원래 아이디어는 경계 상자를 가장 적게 확대해야 하는 서브트리에 항상 삽입하는 것이다. 해당 페이지가 가득 차면 데이터는 각 최소 영역을 덮어야 하는 두 세트로 분할된다. R-tree에 대한 대부분의 연구 및 개선 사항은 트리를 구축하는 방식을 개선하는 것을 목표로 하며, 처음부터 효율적인 트리를 구축(벌크 로딩)하거나 기존 트리에 변경 사항을 수행(삽입 및 삭제)하는 두 가지 목표로 그룹화할 수 있다.

데이터가 R-tree로 구성되면, 주어진 거리 r 내의 이웃과 모든 점의 k 최근접 이웃(모든 L^p-Norm에 대해)은 공간 조인을 사용하여 효율적으로 계산할 수 있다.^[9]^[10] 이는 Local Outlier Factor 등 이러한 쿼리를 기반으로 하는 많은 알고리즘에 유용하다. DeLi-Clu,^[11] 밀도 연결 클러스터링은 R-tree 구조를 사용하여 유사한 종류의 공간 조인을 통해 OPTICS 클러스터링을 효율적으로 계산하는 클러스터 분석 알고리즘이다.

R-tree는 좋은 최악의 경우 성능을 보장하지 않지만 일반적으로 실제 데이터에서 잘 작동한다.^[7]

4. 1. 검색

R-트리의 검색 연산은 B 트리와 유사하게 트리의 루트 노드에서 시작한다. 내부 노드는 사각형 집합과 해당 자식 노드를 가리키는 포인터를 포함하며, 리프 노드는 공간 객체의 사각형(또는 객체를 가리키는 포인터)을 포함한다. 검색 과정에서는 각 노드의 사각형이 검색 사각형(질의 영역)과 겹치는지 확인하고, 겹치는 경우 해당 자식 노드도 탐색하는 방식이 재귀적으로 반복된다. 리프 노드에 도달하면, 포함된 경계 사각형이 검색 사각형과 겹치는지 확인하여 결과 집합에 포함할지 여부를 결정한다.^[12]

최근접 이웃 탐색과 같은 우선 순위 검색의 경우, 쿼리는 점 또는 사각형으로 구성되며, 루트 노드부터 시작하여 우선 순위 큐를 사용해 가장 가까운 항목부터 처리하는 방식으로 검색이 진행된다. 이 방법은 대원 거리를 포함한 다양한 거리 메트릭에 적용할 수 있다.^[5]

4. 2. 삽입

R-트리에 새로운 공간 객체를 삽입하려면 루트 노드에서 시작하여 재귀적으로 트리를 탐색한다. 각 단계에서 현재 노드의 모든 최소 외접 사각형(MBR, 경계 상자/바운딩 박스)을 검사하고, 다음 기준에 따라 삽입할 하위 노드를 선택한다.

최소 확장: 새로운 객체를 포함하기 위해 가장 적게 확장되는 MBR을 선택한다.
최소 영역: 확장이 동일한 경우, 원래 영역이 더 작은 MBR을 선택한다.

이 과정을 반복하여 리프 노드에 도달하면, 다음과 같이 삽입을 진행한다.

빈 항목 존재: 리프 노드에 빈 항목이 있으면 객체를 바로 삽입한다.
빈 항목 없음 (노드 가득 참): 리프 노드가 가득 차 있으면, 삽입 전에 노드 분할을 수행한다.

노드 분할 알고리즘에는 여러 가지가 있으며(선형, 사각형, 소모적), 분할된 MBR들의 겹침 정도를 최소화하는 방식으로 작동한다. 분할 결과 새로운 노드가 생성되고 이전 레벨에 추가된다. 이로 인해 상위 레벨이 다시 가득 찰 수 있으며, 이러한 오버플로는 루트 노드까지 전파될 수 있다. 루트 노드가 오버플로되면 새로운 루트 노드가 생성되고 트리의 높이가 증가한다.

4. 3. 삭제

R-트리에서 공간 객체를 삭제하는 연산은 해당 객체를 포함하는 리프 노드를 찾고, 객체를 삭제한 후, 필요한 경우 노드 병합 또는 재분배를 수행하는 방식으로 진행된다.

우선, 지울 값의 위치를 찾는다. 그리고 그 값을 가진 노드를 삭제한다. 부적절한 상태의 노드가 없다면, 삭제 과정을 종료한다. 만약 부적절한 상태의 노드가 있다면, B-트리와 유사하게 해결한다. 페이지에서 항목을 삭제하려면 상위 페이지의 경계 사각형을 업데이트해야 할 수 있다. 그러나 페이지가 언더플로우 상태가 되면 이웃 페이지와 균형을 이루지 않는다. 대신 해당 페이지가 해소되고 모든 자식 항목(리프 객체뿐만 아니라 서브트리일 수도 있음)이 다시 삽입된다. 이 과정에서 루트 노드가 단일 요소를 갖게 되면 트리의 높이가 감소할 수 있다.^[1]

4. 4. 전체 로드 (Bulk-loading)

R-트리에 대량의 데이터를 한꺼번에 로드하는 기법은 효율적인 트리 구축을 위해 사용된다. 여러 가지 벌크 로딩 알고리즘이 존재하며, 주요 알고리즘은 다음과 같다.

Nearest-X: 객체를 첫 번째 좌표("X")를 기준으로 정렬한 다음 원하는 크기의 페이지로 분할한다.
Packed 힐베르트 R-tree: Nearest-X의 변형으로, X 좌표 대신 사각형 중심의 힐베르트 값을 사용하여 정렬한다. 페이지가 겹치지 않음을 보장하지 않는다.
Sort-Tile-Recursive (STR):^[17] ^[20] Nearest-X의 또 다른 변형으로, 필요한 총 리프 노드 수를 $l=\lceil \text{객체 수} / \text{용량}\rceil$ 로 추정하고, 이를 달성하기 위해 각 차원에서 필요한 분할 인자를 $s=\lceil l^{1/d}\rceil$ 로 추정한 다음, 1차원 정렬을 사용하여 각 차원을 $s$ 개의 동일한 크기의 파티션으로 반복적으로 분할한다. 결과 페이지가 여러 페이지를 차지하는 경우, 동일한 알고리즘을 사용하여 다시 벌크 로드한다. 점 데이터의 경우 리프 노드는 겹치지 않으며 데이터 공간을 대략 동일한 크기의 페이지로 "타일"한다.
Overlap Minimizing Top-down (OMT):^[18] STR을 개선한 것으로, 상향식 접근 방식을 사용하여 슬라이스 간의 중첩을 최소화하고 쿼리 성능을 향상시킨다.
우선순위 R-tree: 최악의 경우 성능이 최적화된 R-트리의 변형이다.^[8]

이러한 알고리즘들은 R-트리의 핵심 어려움, 즉 균형 잡히고 사각형이 너무 많은 빈 공간을 덮지 않으면서 겹치지 않는 효율적인 트리를 구축하는 문제를 해결하는 데 기여한다. 특히, STR 알고리즘은 리프 노드가 겹치지 않고 데이터 공간을 동일한 크기의 페이지로 타일링하는 특징이 있다.

참조

_[1] PDF R Tree https://www2.cs.sfu.[...] cs.sfu.ca
_[2] 서적 Proceedings of the 1984 ACM SIGMOD international conference on Management of data – SIGMOD '84
_[3] 서적 R-Trees: Theory and Applications https://books.google[...] Springer 2011-10-08
_[4] 간행물 Proceedings of the 1995 ACM SIGMOD international conference on Management of data – SIGMOD '95
_[5] 간행물 Advances in Spatial and Temporal Databases
_[6] 간행물 " An RDMA-enabled In-memory Computing Platform for R-tree on Clusters"
_[7] 서적 Advances in Spatial and Temporal Databases
_[8] 서적 Proceedings of the 2004 ACM SIGMOD international conference on Management of data – SIGMOD '04 http://doi.acm.org/1[...]
_[9] 학술지 Efficient processing of spatial joins using R-trees
_[10] 서적 Database and Expert Systems Applications Springer, Berlin, Heidelberg 2003-09-01
_[11] 간행물 Advances in Knowledge Discovery and Data Mining, 10th Pacific-Asia Conference, PAKDD 2006, Singapore, April 9-12, 2006, Proceedings Springer
_[12] 간행물 Proceedings of ICICS, 1997 International Conference on Information, Communications and Signal Processing. Theme: Trends in Information Systems Engineering and Wireless Multimedia Communications (Cat. No.97TH8237)
_[13] 서적 "[1989] Proceedings. Fifth International Conference on Data Engineering"
_[14] 서적 Proceedings of the 1990 ACM SIGMOD international conference on Management of data – SIGMOD '90
_[15] 간행물 New linear node splitting algorithm for R-trees Springer
_[16] 학술지 The X-Tree: An Index Structure for High-Dimensional Data http://www.dbs.ifi.l[...]
_[17] 웹사이트 STR: A Simple and Efficient Algorithm for R-Tree Packing https://archive.org/[...] 1997-02
_[18] 웹사이트 OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree http://ftp.informati[...] 2003-06
_[19] 논문 The Priority RTree: A Practically Efficient and WorstCase Optimal RTree http://www.win.tue.n[...]
_[20] 논문 STR: A Simple and Efficient Algorithm for R-Tree Packing http://citeseerx.ist[...]

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

문의하기 : help@durumis.com