R-트리

R-trees are tree data structures that are similar to B-trees, but are used for spatial access methods i.e., for indexing multi-dimensional information; for example, the (X, Y) coordinates of geographical data. 

R-트리는 B-트리와 비슷한 트리 데이터 구조이며 부분 접근 방법(spatial access methods)을 위해 사용된다.

그 예로 다차원 정보를 찾는데(indexing) 쓰이며 지리 데이터의 좌표에 사용될 수 있다.

A common real-world usage for an R-tree might be: "Find all museums within 2 kilometres (1.2 mi) of my current location".

실 세계에서 R-트리를 사용하는 예시로는 아마 "현재 위치에서 2 킬로미터(1.2마일) 이내의 모든 박물관을 찾아라."가 될 수 있다.

The data structure splits space with hierarchically nested, and possibly overlapping, minimum bounding rectangles (MBRs, otherwise known as bounding boxes, i.e. "rectangle", what the "R" in R-tree stands for).

데이터 구조는 계층적으로 안쪽에 있고, 겹칠 수 있으며, 최소 경계 사각형(MBRs, bounding boxes로 알려짐. R-트리의 "R"은 "사각형"의 줄임말) 안의 공간으로 분리한다. 

Each node of an R-tree has a variable number of entries (up to some pre-defined maximum). 

R-트리의 각 노드는 (몇 개의 미리 정의된 최대값에 속한) 엔트리의 변수를 가지고 있다.

Each entry within a non-leaf node stores two pieces of data: a way of identifying a child node, and the bounding box of all entries within this child node.

리프 노드가 아닌 각 엔트리는 두 개의 데이터를 가진다. : 자식 노드를 나타내는 방법, 이 자식노드 안의 모든 엔트리에 대한 bounding box.

The insertion and deletion algorithms use the bounding boxes from the nodes to ensure that "nearby" elements are placed in the same leaf node (in particular, a new element will go into the leaf node that requires the least enlargement in its bounding box). 

추가와 삭제 알고리즘은 "근처" 엘레먼트에 같은 리프 노드에 위치하도록 보장하기 위해 그 노드로부터 bounding box를 사용한다.(?)

(특히, 새 엘레먼트는 bounding box에서 최소한으로 확대되어야만 하는 리프노드 안으로 진행된다..)

Each entry within a leaf node stores two pieces of information; a way of identifying the actual data element (which, alternatively, may be placed directly in the node), and the bounding box of the data element.

리프 노드 안에서 각 엔트리는 두 가지 정보를 가진다. : 실제 데이터 엘레먼트를 나타내는 방법 (노드에 직접 위치할 수 있도록 할 수 있다.), 데이터 엘레먼트의 bounding box.

Similarly, the searching algorithms (for example; intersection, containment, nearest) use the bounding boxes to decide whether or not to search inside a child node. 

비슷하게, 검색 알고리즘 (예: 교차(교집합), 포함, 최근접지)은 자식 노드 안에서 검색할 수 있는 지 아닌지 결정하기 위해 bounding box를 사용한다.

In this way, most of the nodes in the tree are never "touched" during a search. 

이 방법으로, 트리에서 대부분의 노드는 검색할 동안 "touch"되지 않는다.

Like B-trees, this makes R-trees suitable for databases, where nodes can be paged to memory when needed.

B-트리처럼 이는 R-트리를 (노드들이 필요시 페이지(교체) 될 수 있는) 데이터베이스에 적합하게 한다.

Different algorithms can be used to split nodes when they become too full, resulting in the quadratic and linear R-tree sub-types.

다른 알고리즘은 노드들이 가득 찼을 때 노드들을 분해하는 데 사용될 수 있는데 

R-trees do not historically guarantee good worst-case performance, but generally perform well with real-world data.[citation needed]

R-트리는 역사적으로 최악의 경우 수행능력을 보장하지는 못하지만 일반적으로 실세계 데이터를 잘 수행한다. [주석 필요]

However, a new algorithm was published in 2004 that defines the Priority R-Tree, which claims to be as efficient as the currently most efficient methods and is at the same time worst-case optimal.

그러나, 새로운 알고리즘은 2004년에 우선순위 R-tree로 나왔는데 현재까지 가장 효율적인 방법이고 같은 시간에 최악의 경우도 최적화할 수 있다.

Variants

변이

R* tree

R+ tree

Hilbert R-tree

Priority R-Tree (PR-Tree) - The PR-tree performs similarly to the best known R-tree variants on real-life and relatively evenly distributed data, but outperforms them significantly on more extreme data.[1]

우선순위 R-Tree (PR-트리) - PR 트리는 실생활에서 상대적으로 분산된 데이터에 대해 가장 잘 알려진 R-트리 변이와 비슷하게 실행되지만 더 많은 데이터에서 상당히 뛰어난 수행능력을 가진다.[1]

Algorithm

알고리즘

Search

검색

The input is a search rectangle (Query box). 

입력은 검색 사각형(Query box)이다.

Searching is quite similar to searching in a B-tree. 

검색은 B-tree 검색과 매우 비슷하다.

The search starts from the root node of the tree. 

검색은 트리의 루트로부터 시작한다.

Every internal node contains a set of rectangles and pointers to the corresponding child node and every leaf node contains the rectangles of spatial objects (the pointer to some spatial object can be there). 

각 내부 노드는 공간 객체(spatial objects, 몇 개의 공간 객체의 포인터가 거기에 있을 수 있다.)의 사각형들을 포함하는 각 리프 노드와 자식 노드에 대응되는 포인터와 사각형의 집합을 포함한다. 

For every rectangle in a node, it has to be decided if it overlaps the search rectangle or not. 

노드의 각 사각형에 대해 검색 사각형이 겹치는 지 아닌지 결정해야 한다.

If yes, the corresponding child node has to be searched also. 

만약 겹친다면 대응되는 자식 노드 또한 검색되어야 한다.

Searching is done like this in a recursive manner until all overlapping nodes have been traversed. 

검색은 모든 겹치는 노드들에 대해 순회할 때까지 재귀적인 방법으로 이렇게 수행된다.

When a leaf node is reached, the contained bounding boxes (rectangles) are tested against the search rectangle and their objects (if there are any) are put into the result set if they lie within the search rectangle.

리프 노드에 도달하면 포함된 bounding box들(사각형)들은 검색 사각형에 대해 검사 받고 그 객체들은(그것이 있다면) 검색 사각형안에 있는가의 여부를 판단하는 결과집합을 보여준다(put into).

Insertion

추가

To insert an object, the tree is traversed recursively from the root node. 

객체를 추가하기 위해 트리는 루트 노드로부터 재귀적으로 순회된다.

All rectangles in the current internal node are examined. 

현재 내부 노드의 모든 사각형들은 검사 받는다.

The constraint of least coverage is employed to insert an object, i.e., the box that needs least enlargement to enclose the new object is selected. 

최소 범위의 제약은 객체를 추가하는데 쓰인다. 예를 들어 새로운 객체를 포함하는 최소 확대를 필요로하는 사각형은 선택된다.

In the case where there is more than one rectangle that meets this criterion, the one with the smallest area is chosen. 

이 표준을 만족하는 하나 이상의 사각형이 있는 경우 가장 면적이 작은 사각형이 선택된다.

Inserting continues recursively in the chosen node. 

선택된 노드에서 반복해서 삽입은 계속된다.

Once a leaf node is reached, a straightforward insertion is made if the leaf node is not full. 

리프 노드에 도달했을 때, 리프노드가 채워지지 않았다면 삽입이 곧바로 이루어진다.

If the leaf node is full, it must be split before the insertion is made. A few splitting algorithms have been proposed for good R-tree performance.

리프노드가 채워지면 삽입이 이루어지기 전에 쪼개져야 한다. 몇몇개의 분리 알고리즘은 R-tree의 성능을 개선하기 위해 제안되어 왔다.