R 트리

R-tree
이 기사는 데이터 구조에 관한 것입니다.메트릭 공간의 유형은 실제 트리를 참조하십시오.
R 트리
유형트리
발명된1984
발명자안토닌 구트만
빅 O 표기의 시간 복잡도
알고리즘. 평균 최악의 경우
서치 O(로그인M)O(n)[1]
2D 직사각형용 R-트리의 간단한 예
ELKI를 사용한 3D 포인트용 R*트리 시각화(큐브는 디렉토리 페이지)

R-tree는 공간 액세스 방법, 즉 지리 좌표, 직사각형 또는 다각형과 같은 다차원 정보를 인덱싱하는 데 사용되는 트리 데이터 구조입니다.R-tree는 1984년[2] Antonin Guttman에 의해 제안되었으며 이론적인 맥락과 응용적인 [3]맥락 모두에서 상당한 사용을 발견했다.R-Tree의 일반적인 실제 용도는 레스토랑 위치나 일반적인 지도(거리와 건물, 호수 윤곽선, 해안선 등)와 같은 공간 객체를 저장한 다음 "현재 위치에서 2km 이내의 모든 박물관을 검색", "2km 이내의 모든 도로 세그먼트를 검색하십시오"와 같은 질문에 대한 답변을 신속하게 찾는 것입니다.(내 위치를 내비게이션에 표시하기 위해) 또는 "가장 가까운 주유소를 찾습니다"(도로는 고려하지 않지만).또한 R-트리는 [5]대원거리 등 다양한 거리 메트릭에 대한 가장 가까운 네이버[4] 검색을 가속화할 수 있습니다.

R-트리 아이디어

데이터 구조의 주요 아이디어는 근처 객체를 그룹화하고 트리의 다음 상위 레벨에 있는 최소 경계 직사각형으로 표현하는 것입니다. R-트리의 "R"은 직사각형에 대한 것입니다.모든 객체는 이 경계 직사각형 안에 있으므로 경계 직사각형과 교차하지 않는 쿼리는 포함된 객체 중 어느 것도 교차할 수 없습니다.리프 레벨에서는 각 직사각형은 단일 객체를 나타내며, 상위 레벨에서는 집계에 포함되는 객체의 수가 증가합니다.이는 데이터 집합의 대략적인 근사치가 증가하는 것으로도 볼 수 있습니다.

B-tree와 마찬가지로 R-tree도 균형 잡힌 검색 트리이며(따라서 모든 리프 노드의 깊이가 같으며), 데이터를 페이지 단위로 정리하고, 디스크에 저장하도록 설계되어 있습니다(데이터베이스에서 사용).각 페이지에는 최대 엔트리 수종종 M {M를 할 수 있습니다.또한 최소 필(루트 노드 제외)을 보증하지만 최대 엔트리 수의 30~40%를 채우는 것이 최고의 퍼포먼스입니다(B-tree는 페이지 필을 50%, B*tree는 66% 보증).그 이유는 B-트리에 저장된 선형 데이터와 달리 공간 데이터에 더 복잡한 균형이 필요하기 때문입니다.

대부분의 트리와 마찬가지로 검색 알고리즘(예: 교차로, 격납, 가장 가까운 인접 탐색)은 비교적 간단하다.중요한 아이디어는 경계 상자를 사용하여 하위 트리 내부를 검색할지 여부를 결정하는 것입니다.이렇게 하면 트리의 대부분의 노드가 검색 중에 읽히지 않습니다.B-tree와 마찬가지로 R-tree는 필요할 때 노드를 메모리로 페이징할 수 있고 트리 전체를 메인 메모리에 보관할 수 없는 대규모 데이터 세트 및 데이터베이스에 적합합니다.데이터를 메모리에 저장할 수 있는 경우(또는 캐시할 수 있는 경우)라도 대부분의 실용적인 응용 프로그램에서 R 트리는 일반적으로 개체 수가 수백 개 이상일 때 모든 개체를 단순하게 검사하는 것보다 성능이 우수합니다.그러나 인메모리 애플리케이션에는 약간 더 나은 성능을 제공하거나 실제로 구현하기가 더 쉬운 유사한 대안이 있습니다.

R-tree의 주요 어려움은 효율적인 트리를 구축하는 것입니다.한편, 균형 잡힌(리프 노드가 같은 높이에 있음) 반면 직사각형이 너무 많은 빈 공간을 차지하지 않고 너무 많이 겹치지 않습니다(따라서 검색 중에 처리할 서브트리가 적습니다).예를 들어 효율적인 트리를 얻기 위해 요소를 삽입하는 원래 아이디어는 항상 경계 상자의 확장이 가장 적은 하위 트리에 삽입하는 것입니다.페이지가 가득 차면 데이터는 각각 최소 영역을 커버하는2개의 세트로 분할됩니다.R-Tree에 대한 조사와 개선의 대부분은 트리의 구축 방법을 개선하는 것을 목표로 하고 있으며, 효율적인 트리 구축(벌크 로딩으로 알려져 있음)과 기존 트리 변경 수행(삽입 및 삭제)의 두 가지 목표로 그룹화할 수 있습니다.

R-tree는 최악의 경우 성능을 보장하지 않지만 일반적으로 실제 [6]데이터를 사용할 경우 성능이 우수합니다.이론적으로는 R 트리의 (벌크 로딩된) priority R-tree 베리안트는 최악의 경우 [7]최적입니다만, 복잡성이 증가했기 때문에, 지금까지 실용 애플리케이션에서는 그다지 주목을 받지 못했습니다.

데이터가 R-트리에 편성되어 있는 경우, 모든 포인트의 소정의 거리 r 내의 네이버와 (임의의 L-Norm에p 대해) 가장 가까운 k개의 네이버를 공간 [8][9]결합을 사용하여 효율적으로 계산할 수 있습니다.이는 Local Outlier Factor 등 이러한 쿼리를 기반으로 하는 많은 알고리즘에 도움이 됩니다.DeLi-Clu,[10] Density-Link-Clustering은 R-트리 구조를 사용하여 Optics 클러스터링을 효율적으로 계산하는 클러스터 분석 알고리즘입니다.

변종

알고리즘.

데이터 레이아웃

R-Tree의 데이터는 다양한 수의 엔트리를 가질 수 있는 페이지로 구성됩니다(사전 정의된 최대값, 보통 최소값 이상).비리프 노드 내의 각 엔트리는 2개의 데이터, 즉 자노드를 식별하는 방법과 이 자노드 내의 모든 엔트리의 경계 상자를 기억한다.리프 노드는 각 자녀에게 필요한 데이터(종종 어린이를 나타내는 점 또는 경계 상자 및 자녀에 대한 외부 식별자)를 저장합니다.점 데이터의 경우 리프 항목은 점 자체일 수 있습니다.폴리곤 데이터(대형 폴리곤 저장 필요)의 경우 일반적으로 폴리곤의 MBR(최소 경계 직사각형)만 트리에 고유 식별자와 함께 저장합니다.

서치

범위 검색에서 입력은 검색 직사각형(쿼리 상자)입니다.검색은 B+ 트리에서 검색하는 것과 매우 유사합니다.트리의 루트 노드부터 검색이 시작됩니다.각 내부 노드는 대응하는 자노드에 대한 직사각형 및 포인터 세트를 포함하며, 각 리프 노드는 공간 객체의 직사각형(일부 공간 객체에 대한 포인터가 있을 수 있음)을 포함한다.노드의 모든 직사각형에 대해 검색 직사각형과 겹치는지 여부를 결정해야 합니다.이 경우 해당 하위 노드도 검색해야 합니다.이와 같이 검색은 중복되는 모든 노드를 통과할 때까지 재귀적으로 수행됩니다.리프 노드에 도달하면 포함된 경계 상자(직각)가 검색 직사각형에 대해 테스트되고 해당 개체(있는 경우)가 검색 직사각형 내에 있으면 결과 세트에 포함됩니다.

가장 가까운 네이버 검색과 같은 우선순위 검색의 경우 쿼리는 점 또는 직사각형으로 구성됩니다.루트 노드가 priority 큐에 삽입됩니다.큐가 비어 있거나 원하는 수의 결과가 반환될 때까지 큐에서 가장 가까운 엔트리를 처리하여 검색을 계속합니다.트리 노드가 확장되고 하위 노드가 다시 삽입됩니다.리프 엔트리는 [11]큐에서 발견되면 반환됩니다.이 접근방식은 지리 데이터의 [5]대원 거리를 포함한 다양한 거리 메트릭과 함께 사용할 수 있다.

삽입

개체를 삽입하기 위해 트리는 루트 노드에서 재귀적으로 통과합니다.각 단계에서 현재 디렉토리 노드 내의 모든 직사각형을 검사하고, 가장 확대가 적은 직사각형을 선택하는 등의 휴리스틱을 이용해 후보를 선택한다.그런 다음 리프 노드에 도달할 때까지 검색이 이 페이지로 내려갑니다.리프 노드가 가득 찬 경우 삽입하기 전에 분할해야 합니다.다시 말하지만, 완전 검색은 비용이 너무 많이 들기 때문에 노드를 두 개로 분할하기 위해 휴리스틱을 사용합니다.새로 작성한 노드를 이전 레벨에 추가하면 이 레벨이 다시 오버플로우할 수 있으며 이러한 오버플로우는 루트노드까지 전파될 수 있습니다.이 노드도 오버플로우하면 새로운 루트노드가 생성되어 트리의 높이가 증가합니다.

삽입 하위 트리 선택

알고리즘은 삽입할 서브트리를 결정해야 합니다.데이터 개체가 단일 직사각형에 완전히 포함되어 있으면 선택사항이 명확합니다.확장해야 하는 옵션이나 직사각형이 여러 개 있는 경우 트리의 성능에 큰 영향을 미칠 수 있습니다.

개체는 최소 확장이 필요한 하위 트리에 삽입됩니다.혼합 휴리스틱이 전체적으로 사용됩니다.다음에 발생하는 것은 오버랩을 최소화하려고 하는 것입니다(동일 경우 최소 확대 및 최소 영역 선택).높은 수준에서는 R-트리와 비슷하게 동작하지만 다시 작은 영역의 서브트리를 선호합니다.R* 트리의 직사각형 오버랩이 줄어든 것은 기존 R-트리에 비해 큰 장점 중 하나입니다.

오버플로우 노드 분할

마지막으로 X-트리는[12] 노드를 분할하지 않고 (특히 고차원 데이터의 경우) 적절한 분할이 발견되지 않을 때 추가 엔트리를 모두 포함하는 이른바 슈퍼노드를 구축할 수 있는 R*트리 변종이라고 볼 수 있습니다.

삭제

페이지에서 항목을 삭제하려면 상위 페이지의 경계 직사각형을 업데이트해야 할 수 있습니다.단, 페이지가 가득 차면 네이버와 균형이 잡히지 않습니다.대신 페이지가 용해되고 모든 하위 트리(리프 개체뿐 아니라 하위 트리일 수 있음)가 다시 삽입됩니다.이 프로세스 중에 루트 노드에 단일 요소가 있는 경우 트리 높이가 감소할 수 있습니다.

벌크 로딩

  • Nearest-X: 객체는 첫 번째 좌표("X")에 따라 정렬된 후 원하는 크기의 페이지로 분할됩니다.
  • 패킹 힐버트 R 트리: Nearest-X의 변형이지만 X 좌표 대신 직사각형 중심 힐버트 값을 사용하여 정렬합니다.페이지가 겹치지 않는다는 보장은 없습니다.
  • Sort-Tile-Recursive(STR):Nearest-X의 잎들 개체의 l=⌈ 수/용량 ⌉{개체의\displaystyle l=\lceil{\text{수}}{\text{용량}}\rceil}, 각 치수에 필요한 분열 인자 s로 이를 이루기 위해)⌈ 나는 1/d⌉{\displaystyl로 요구되는 총 추정 또 다른 변화[13].es=\ l은는 1차원 정렬을 사용하여 각 치수를 동일한 으로 순차적으로 분할합니다결과 페이지가 여러 페이지를 차지하는 경우 동일한 알고리즘을 사용하여 다시 일괄 로딩됩니다.점 데이터의 경우 리프 노드가 겹치지 않고 데이터 공간을 거의 동일한 크기의 페이지로 "타일링"합니다.
  • OMT([14]Overlap Minimizing Top-down): 슬라이스 간의 오버랩을 최소화하고 쿼리 성능을 향상시키는 하향식 접근 방식을 사용하여 STR보다 향상됩니다.
  • priority R 트리

「 」를 참조해 주세요.

레퍼런스

  1. ^ https://www2.cs.sfu.ca/CourseCentral/454/jpei/slides/R-Tree.pdf[베어 URL PDF]
  2. ^ Guttman, A. (1984). "R-Trees: A Dynamic Index Structure for Spatial Searching" (PDF). Proceedings of the 1984 ACM SIGMOD international conference on Management of data – SIGMOD '84. p. 47. doi:10.1145/602259.602266. ISBN 978-0897911283. S2CID 876601.
  3. ^ Y. Manolopoulos; A. Nanopoulos; Y. Theodoridis (2006). R-Trees: Theory and Applications. Springer. ISBN 978-1-85233-977-7. Retrieved 8 October 2011.
  4. ^ Roussopoulos, N.; Kelley, S.; Vincent, F. D. R. (1995). "Nearest neighbor queries". Proceedings of the 1995 ACM SIGMOD international conference on Management of data – SIGMOD '95. p. 71. doi:10.1145/223784.223794. ISBN 0897917316.
  5. ^ a b Schubert, E.; Zimek, A.; Kriegel, H. P. (2013). "Geodetic Distance Queries on R-Trees for Indexing Geographic Data". Advances in Spatial and Temporal Databases. Lecture Notes in Computer Science. Vol. 8098. p. 146. doi:10.1007/978-3-642-40235-7_9. ISBN 978-3-642-40234-0.
  6. ^ Hwang, S.; Kwon, K.; Cha, S. K.; Lee, B. S. (2003). "Performance Evaluation of Main-Memory R-tree Variants". Advances in Spatial and Temporal Databases. Lecture Notes in Computer Science. Vol. 2750. pp. 10. doi:10.1007/978-3-540-45072-6_2. ISBN 978-3-540-40535-1.
  7. ^ Arge, L.; De Berg, M.; Haverkort, H. J.; Yi, K. (2004). "The Priority R-tree" (PDF). Proceedings of the 2004 ACM SIGMOD international conference on Management of data – SIGMOD '04. p. 347. doi:10.1145/1007568.1007608. ISBN 978-1581138597. S2CID 6817500.
  8. ^ Brinkhoff, T.; Kriegel, H. P.; Seeger, B. (1993). "Efficient processing of spatial joins using R-trees". ACM SIGMOD Record. 22 (2): 237. CiteSeerX 10.1.1.72.4514. doi:10.1145/170036.170075.
  9. ^ Böhm, Christian; Krebs, Florian (2003-09-01). Supporting KDD Applications by the k-Nearest Neighbor Join. Database and Expert Systems Applications. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. pp. 504–516. CiteSeerX 10.1.1.71.454. doi:10.1007/978-3-540-45227-0_50. ISBN 9783540408062.
  10. ^ Achtert, Elke; Böhm, Christian; Kröger, Peer (2006). "DeLi-Clu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking". In Ng, Wee Keong; Kitsuregawa, Masaru; Li, Jianzhong; Chang, Kuiyu (eds.). Advances in Knowledge Discovery and Data Mining, 10th Pacific-Asia Conference, PAKDD 2006, Singapore, April 9-12, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 3918. Springer. pp. 119–128. doi:10.1007/11731139_16.
  11. ^ Kuan, J.; Lewis, P. (1997). "Fast k nearest neighbour search for R-tree family". 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). p. 924. doi:10.1109/ICICS.1997.652114. ISBN 0-7803-3676-3.
  12. ^ Berchtold, Stefan; Keim, Daniel A.; Kriegel, Hans-Peter (1996). "The X-Tree: An Index Structure for High-Dimensional Data". Proceedings of the 22nd VLDB Conference. Mumbai, India: 28–39.
  13. ^ Leutenegger, Scott T.; Edgington, Jeffrey M.; Lopez, Mario A. (February 1997). "STR: A Simple and Efficient Algorithm for R-Tree Packing". {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  14. ^ Lee, Taewon; Lee, Sukho (June 2003). "OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree" (PDF). {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

외부 링크

  • Wikimedia Commons의 R-Tree 관련 미디어