A. Korotkov's New R-Tree Splitting Algorithm

공간 데이터(spatial data) 처리는 현대 데이터베이스에서 중요한 작업 중 하나이다. 공간 데이터를 효율적으로 처리하기 위해 기타 다른 정보형과 마찬가지로 인덱스 구조를 유지할 수 있다. 그러나 다차원적이고 구간(interval)을 나타내는 특성 상 기존의 B-Tree 등의 탐색 구조로는 효율적인 공간 데이터의 색인이 쉽지 않다. 따라서, 각 공간 데이터의 객체(geometry라고 부르기도 한다.)를 어느 정도 간략하게 표현하여 인덱스 구조를 생성한다. 가장 대표적인 구조가 R-Tree이다. R-Tree는 geometry를 MBR이라고 불리는 구조로 간략하게 표현하여 이를 색인에 사용한다.^[1]

MBR(Minimum Bounding Rectangle)은 geometry 정보를 간략하게 표현하기 위한 방법 중 하나이다. 어떤 geoemtry의 MBR은 각 차원 별 geometry에 속한 좌표들의 최솟값(min)과 최댓값(max) 정보를 유지하게 되므로, n차원 geometry의 경우 2 * n개의 정보를 유지하게 된다. 일반적으로 2차원을 사용하는 경우가 많으므로 2차원 MBR을 아래 글에서 서술할 때 사용한다. 임의의 2차원 MBR \( m \) 에 대해 최솟값과 최댓값 정보를 나타낼 때 \( m = \{m^x_{min}, m^x_{max}, m^y_{min}, m^y_{max}\} \)와 같은 기호를 사용할 것이다.

R-Tree의 leaf node는 복수의 어떤 geometry의 MBR과 주소 (또는 개체의 ref 값)를 갖는다. Branch node는 다른 트리 구조처럼 여러 children node들을 유지하고 있다. 이 때 한 child node를 나타내기 위해 leaf node처럼 그 child node의 MBR 값과 주소를 갖는다. 한 node의 MBR이란 그 node (와 그 이하의 subtree)가 가지고 있는 모든 객체들의 MBR을 의미한다.

R-Tree는 높이 균형(height balanced) 트리이므로 삽입 도중에서 어떤 노드의 분할(split)이 일어날 수 있다. R-Tree 탐색은 B-Tree와 달리 multipath로 이루어지기 때문에 노드의 분할이 효율적이지 않는다면 탐색 속도의 결과가 좋지 않을 것이라고 확인할 수 있다. 따라서 여러 node splitting 알고리즘이 제안되었고, ^{[2] [3] [4]} 본 글에서는 최근 A. Korotkov가 제시한 새로운 splitting 알고리즘을 제시한다. ^[5] 해당 알고리즘은 현재 PostGIS에서 사용하고 있는 알고리즘 이다.

알고리즘 소개

R-Tree node splitting 문제를 다르게 서술하면 다음과 같다. MBR의 집합 I가 주어질 때, I의 모든 원소를 두 집합 \( S_1 \) 와 \( S_2 \) 로 나누는 문제이다. 일부 R-Tree variant 중에 한 MBR이 서로 다른 두 개의 node에 속하는 경우도 있으나, A. Korotkov의 알고리즘에서는 허용하지 않으므로, \( S_1 \)와 \( S_2 \) 는 상호 배타적이다.

이 알고리즘은 기본적으로 1차원 구간에 대해서 동작하지만, 다차원일 경우 각 차원별로 projection을 수행한 뒤 동일한 알고리즘을 수행함으로써 다차원 MBR 분할이 가능하다. 2차원의 MBR이 흔히 사용되므로 알고리즘을 서술할 때 2차원을 가정한다. 또한 알고리즘의 입력인 MBR의 집합 I의 크기는 n이라고 하자; \( (|I| = n). \) 2차원 MBR을 x축으로 projection 하게 되면, \( (x_{min}, x_{max}) \) 와 같은 구간으로 표현할 수 있다. 알고리즘의 가장 첫번째 과정은 \( x_{min} \) 한번 정렬을 하고 \( x_{max} \)로도 한번 정렬을 하는 것이다. \( x_{min} \)으로 정렬한 MBR 순서를 \( L=\{l_1, l_2, \cdots , l_n \} \)이라 하고, \( x_{max} \)로 정렬한 MBR 순서를 \( U=\{u_1, u_2, \cdots , u_n \} \) 라고 하자. 물론 각각의 \( l_k \) 와 \( u_k \) 는 1차원 interval이므로, min과 max로 나타낼 수 있는 두 수의 쌍으로 표현된다; \( ( 1 \ge k \land k \ge n ) \).

이 알고리즘의 입력은 1차원 구간이므로 출력은 2개의 구간이라고 가정해도 무방하다. (각 원소를 어느 구간에 넣을지 확인하는 작업은 쉬운 작업이다.) 이 중, 둘 중 적어도 1개의 구간의 최솟값(min)은 입력 집합 \( I \) 의 모든 구간의 하한의 최솟값(minimum of lower bound; \( low_{min} = \min_{i \in I} i_{min} \) )과 일치하고 마찬가지로 적어도 1개의 구간의 최댓값(max)은 상한의 최댓값(maximum of upper bound; \( upp_{max} = \max_{i \in I} i_{max} \))과 일치한다고 할 수 있다. 따라서 알고리즘의 결과는 구간 2개 \( (low_{min}, a) \)와 \( (b, upp_{max} ) \)이고, 다시 말하면 a와 b를 정하는 작업이라고 할 수 있다.

\(a\)와 \(b\) 값은 \(L\)와 \(U\)를 각각 반복하여 총 2번의 반복문을 통해 얻어낸다. 먼저 \(L\)을 기준으로 \(b\)의 값을 정한다. 정하는 방법은 다음과 같다. 첫번째 반복문에선 각 iteration마다 순서 \(L\)의 원소들의 distinct \(min\)값들이 \(b\)가 된다. 이 때 대응하는 \( a \) 의 값은 \( b \)보다 작은 \(min\)을 갖는 \(L\)의 원소들의 \(max\) 값 중 가장 큰 값이다.

\[ a  := \max_{i \in I : i_{min} < b} i_{max}  \]

또한 여기에 덧붙여 \( (low_{min}, a) \)에 속할 입력 구간의 최소 개수 \( n_{min} \)와 최대 개수 \( n_{max} \)도 정해지는데 이는 \(b\)보다 작은 min를 갖는 원소의 개수와 \(a\)보다 작거나 같은 max를 갖는 원소의 개수로 정해진다. 즉, 다음과 같다.

\[ n_{min} := \vert\{i \in I \mid i_{min} < b \}\vert\]

\[ n_{max}  := \vert\{i \in I \mid i_{max} \le a \}\vert\]

이를 다음 예제와 함께 살펴보자. 알고리즘의 입력 I가 다음과 같이 주어졌다고 하자.

\[ I = \{ (1, 4) , (2, 3), (2, 5), (4, 7), (6, 8) , (6, 9), (7, 8) \} \]

정렬을 하면 다음과 같다:

\[ L = \{ (1, 4), (2, 3), (2, 5), (4, 7), (6, 8), (6, 9), (7, 8) \} \]

\[ U = \{ (2, 3), (1, 4), (2, 5), (4, 7), (6, 8), (7, 8), (6, 9) \} \]

첫 iteration에서는 \( b = 1\)이지만 상응하는 a가 정의되지 않으므로 다음 값인 2부터 시작한다. \(b = 2 \)일 경우, \( I \)의 집합 중 min이 \(2\)보다 작은 원소는 \( \{ (1, 4) \} \) 이고 이 중 max의 최댓값은 4 이므로 \(a = 4\)가 된다. \( n_{min} \) 역시 자연스럽게 \( 1 \)이 된다. 다시 살펴보면 이미 \( L \)이 min을 기준으로 정렬 되어있고 iteration은 distinct min을 기준으로 반복하기 때문에 \( L \)을 순서대로 반복하는 것으로 충분하다. 다시 첫 번째 iteration으로 돌아와서 정해지는 값을 보면 다음과 같다; \( a = 4, b = 2, n_{min} = 1, n_{max} = 2\). \(n_{max}\)의 경우 \( L \)만 가지고는 쉽게 확인할 수 없고, \( U \) 를 통해 \( a = 4 \)보다 작거나 같은 max를 갖는 구간의 개수를 파악하면 된다. 이렇게 한 이터레이션에서 후보 군을 찾았으면 considerSplit라는 서브알고리즘을 통해 실제 split을 시도해보게 된다. 해당 알고리즘은 별도 section에서 서술한다.

다음 iteration부터 차례대로 a와 b값은 \( (a=5, b=4), (a=7, b=6), (a=9, b=7)\)로 선택할 것이다. 상세한 예시를 통해 바로 다음 iteration을 살펴보자. 이전 iteration에서 \( b= 2 \)로 선택했으므로 다음 distinct min 값은 \( 4 \) 이다. 따라서 \(b = 4\)로 선택하고, \(a\)의 값은 \( \{ (1,4), (2,3), (2,5) \} \) 중 가장 큰 max 값인 \( 5 \)로 설정된다. 자연스럽게 \( n_{min} = 3, n_{max} = 3 \) 으로 정해진다. ( \(a = 5) \) 보다 작거나 같은 max를 갖는 원소들은 \( \{ (2, 3), (1, 4), (2,5) \} \)이고 개수는 3개이다.) 역시 마찬가지로 각 iteration 마다 찾은 후보 군에 대해 considerSplit라는 서브 알고리즘을 수행한다.

두 번째 반복에서는 \( a \)값을 distinct max 값에 대해서 진행한다. 첫 반복문이 \( L \)위에서 반복문을 진행하며 \( b \)값을 결정했다면, 이후는 \( U \)위에서 뒤에서 반복문을 진행하며 \( a \)값을 결정하는 형태이다. 비슷하게 이 때 \( a \)에 대응하는 \( b \)의 값은 다음과 같이 정의된다. \( L \) 원소 중 \(max\)값이 \( a \)보다 큰 원소들의 \( min \) 값의 최소이다.

\[ b  := \min_{i \in I : i_{max} > a} i_{min}  \]

마찬가지로 \( a = 9 \) 값 다음인 \( a = 8 \)부터 시작한다. \( a = 8 \) 일 경우 \( max \)가 \( a \)보다 큰 원소 집합은 \( \{ (6, 9) \} \)이고, 이 집합에서 \( min \)값의 최소는 \(6\)이므로 \(b = 6\)이다. \( (low_{min}, a) \)에 속할 입력 구간의 최소 개수 \( n_{min} \)와 최대 개수 \( n_{max} \)는 이전 반복과 동일하게 정의된다. 이 경우 \( b = 6 \)보다 min이 작은 원소의 개수는 4개이므로 \( n_{min}= 4\) 이고 \( a = 8\) 보다 max가 작거나 같은 원소의 개수는 6개이므로 \( n_{max} = 6 \)이다. 이후 정해지는 값은 마찬가지로 \( a = 7 , b = 4 , n_{min} = 3, n_{max} = 4\) 가 될 것이다.

위 방법은 두 번의 반복이 각각 \( min \)과 \( max \)로 정렬된 배열 \(L\)과 \(U\)을 따라 순회함으로써 쉽게 구현할 수 있을 것이다. 첫 번째 반복에서 distinct min을 고를 때 \(L\)에서 카운터(인덱스)를 증가시켜가며 다른 값이 나올 때 까지 증가하며 현재 max값을 유지하면 \( a \) 와 \(b\)를 쉽게 찾을 수 있고, \( n_{min} \)은 그 당시 카운터의 개수와 일치하게 된다. \( n_{max} \)의 경우는 따로 찾아야 하는데, \(U\)를 따라 순회하면 \( a \)보다 max가 작거나 같은 원소의 개수를 쉽게 찾을 수 있다. 두 번째 반복에서는 유사하게 \( U \)를 따라 distinc max를 고를 때 인덱스를 감소시켜가며 진행하면 될 것이다. 이 방법은 A. Korotkov가 pseudo-code로 제시한 방법이며, 현재 postGIS에서도 R-Tree split 함수에 같은 접근법을 사용하고 있다.

considerSplit

위 반복에서 후보를 찾게 되면 해당 후보의 cost를 계산하고 현재 유지하고 있는 후보보다 좋다면 입력 후보를 선택하게 된다. 본래 R-Tree에는 각 node의 최소 degree가 존재한다. 즉, 두 개의 출력 집합의 원소의 개수는 하한이 있는 것이다. 이 과정에서 너무 치우친 split 후보를 금지한다. 이러한 조건을 만족시킨 후보를 유효하다고 하자. 후보마다 호출되는 considerSplit 함수는 해당 후보가 유효한지 살펴보고, 유효한 후보군 중 가장 좋은 후보를 찾는 함수이다. 여기서 가장 좋은 후보란 겹친 영역(overlapping area)가 가장 적은 후보를 지칭한다.

\( n_{min} \) 및 \( n_{max} \) 은 \( (low_{min}, a) \)의 최소 및 최대 원소의 개수를 의미할 뿐이므로, 실제로 \( (low_{min}, a) \)구간에 몇 개의 원소를 넣을지 계산해야 한다. 이를 \( n_{low} \) 라고 지칭하자. \( n_{min} \) 이 전체 개수의 절반을 넘는다면 \( n_{low} = n_{min} \) 이다. 아닐 경우 \( n_{max} \) 가 전체 개수의 절반을 넘지 않는다면 \( n_{low} = n_{max} \) 이고 그 외의 경우는 전체 개수의 절반으로 설정된다. \( (b, upp_{max} ) \) 에 속할 원소의 개수는 자연스럽게 정의된다. 이 후 겹친 영역을 계산하는데 이는 다음과 같이 정의된다.

\[ \frac{a - b}{upp_{max} - low_{min}} \]

겹친 영역 값을 바탕으로 최소가 되는 후보를 선택하면 완료된다.

결론

이 글에서는 R-Tree의 node split 방법 중 하나인 A. Korotkov의 알고리즘을 살펴보았다. 기본적으로 1차원 구간에 대한 알고리즘이지만 각 축 별로 독립적으로 수행할 수 있으므로 다차원 구간에 대해서도 동작하고 또한 A. Korotkov의 실험결과 기존 R*-Tree 방법에 비해 좋은 성능을 보여주는 것으로 확인된다.

Reference

PostGIS 3.0.0 source (git repository) (code)

Bibliography

1. A. Guttman. R-trees: A dynamic index structure for spatial searching. SIGMOD Rec., 14(2):47–57, June 1984.
2. D. Greene. An implementation and performance analysis of spatial dataaccess methods. In Proceedings. Fifth International Conference on Data Engineering , pages 606–615, 1989.
3. C. H. Ang and T. C. Tan. New linear node splitting algorithm for R-trees. In M. Scholl and A. Voisard, editors, Advances in Spatial Databases, pages 337–349, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg.
4. N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An efficient and robust access method for points and rectangles. In Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, SIGMOD ’90, page 322–331, New York, NY, USA, 1990. Association for Computing Machinery.  
5. A. Korotkov, A new double sorting-based node splitting algorithm for R-tree. Program Comput Soft 38, 109–118 (2012).