Good bye, halcyon days...

Packed Hilbert R Tree

Packed Hilbert R Tree

Self-similar

자기 유사성(Self-Similar)은 자신의 일부분/전체가 완벽히 또는 매우 유사하게 닮음을 의미한다. 이러한 특징을 만족하는 기하학적 형태를 프랙탈(Fractal)이라고 하며, 인공적으로 만들어진 프랙탈도 매우 많이 있다. 말로 설명하면 어려울 수도 있으나, 아래 Youtube 영상을 참고하면, '아~~~ '와 함께 바로 이해할 수 있을 것이다.

이러한 자기 유사성을 만족하는 기하학적 형태는 재귀적/반복적으로 공간을 채워나가는 형태를 가지며, 특정 공간을 채워나가는 또는 정복해나가는 특징을 이용하여 공간에 대한 특별한 처리가 필요할 때 사용될 수 있다.


Hilbert Curve ( well-known Hilbert space-filling curve)

다양하게 발음되는 것 같아 영문으로만 표기한다. Hilbert Curve는 Window 화면 보호기를 통해서 이미 경험했을 확률이 매우 높다. 이는 David Hilbert[1]가 설명한 Peano curve[2] 중의 하나의 형태로 특정 공간을 2 by 2 분할 또는 2 by 2 분할 반복한 형태의 공간을 체워나가는 기법이다.

이 형태의 특징은 다중공간 정복에 있어 순회(Travel)하는 순서(Order) 측면에서 Z-order에 비해 locality-preserving에 있어서 장점을 가진다. Z-order의 경우 아래 그림과 같이 대각선으로 다음 공간을 이동하는 지점이 발생하는데, Hilbert Order의 경우는 이러한 Case가 발생하지 않는다.

z-order_and_hilbert-order

Hilbert Order를 이용한 순회(Travel)시 4개의 Pattern ( 좌/우/상/하 측이 열린 형태 )으로 하단 Level을 Recursion으로 순회(Travel)하는 것이 최하위 Level을 기준으로 Iteration 방식으로 순회(Travel)하는 것보다 수월하다.

.

Packed Hilbert R Tree

R-Tree는 Spatial Indexing Tree로서 다중 공간에 대한 Indexing을 목적으로 사용된다. R-Tree 형태에는 다양한 종류가 존재하는데, 위에서 설명한 Hilbert Curve의 Order를 이용하여 준비된 영역에 대해 2 by 2 반복 분할 후, 분할된 공간을 Merge하는 방식의 Bottom-up 방식으로의 공간에 대한 Indexing을 처리하는 방식이다. 따라서 1) 각 Node의 Bounding Box를 최소화하는 장점이 있으며 2) 정해진 공간에 대해 순회하면서 Bottom-up 방식으로 Index가 생성되는 방식으로 정적인 공간 처리에 유용하다.

packs rectangles into an R-tree [3]

Step 1. Calculate the Hilbert value for each data rectangle
Step 2. Sort data rectangles on ascending Hilbert values
Step 3. /* Create leaf nodes (level l=0) */
    While (there are more rectangles)
         generate a new R-tree node
         assign the next C rectangles to this node
Step 4. /* Create nodes at higher level (l + 1) */
    While (there are > 1 nodes at level l)
         sort nodes at level l ≥ 0 on ascending creation time
         repeat Step 3

성능 평가나 기타 상세한 내용은 VLDB '94 Proceedings of the 20th International Conference on Very Large Data Bases 의 Paper 중에서 Hilbert R-tree: An Imporved R-tree using Fractals (Author : Ibrahim Kamel, Christos Faloutsos) 를 참고 바란다.

Main Image Ref : https://www.pexels.com/photo/lights-abstract-curves-long-exposure-1944/


  1. https://en.wikipedia.org/wiki/David_Hilbert ↩︎

  2. https://en.wikipedia.org/wiki/Peano_curve ↩︎

  3. https://en.wikipedia.org/wiki/Hilbert_R-tree#Packed_Hilbert_R-trees ↩︎



e.riny

e.riny

I know what I know nothing.