Spatial Data = Multi Dimension Data

• 포인트, 선, 다각형 등을 데이터 타입으로 가진다.

📌 Nearest Neighbor queries(NN-query) ⇒ 점이나 object가 주어지면, 조건을 만족하는 가장 가까운 object를 찾는 것

📌 Range queries ⇒ 특정 공간의 범위 안에 존재하는 object를 찾는 것

1️⃣ K-D trees : Space-partitioning Method

BST의 확장 버전이다.

• 루트 노드부터 기준점을 찍고 x, y를 번갈아가면서 기준으로 채택하여 더 작은 값은 left에 배치되도록, 더 큰 값을 right에 배치하도록 트리를 생성해나가는 방법이다.

2️⃣ Quad trees : Space-partitioning Method

• 공간을 계속 4개로 나누는 방법이다.

• stack을 이용하여 해당 공간이 주어진 Range Query에 해당하지 않으면 바로 스택에서 pop하고, 만약 해당한다면(overlap된다면) 해당 공간의 자식 노드를 push후에 자식 노드에서도 똑같이 진행한다.

  ⇒ Range Query가 한공간에만 있는 것이 아니므로 back tracking이 필요하다.

3️⃣ R-trees : Data-partitioning Method

$B^+$-tree의 N차원 확장 버전이다.

• k개의 가까운 이웃을 하나의 Minimum Bounding Box로 묶어서 또 그 MBB를 k개끼리 묶고 이런 과정을 반복해서 1개의 Root만을 남길때까지 묶어 트리 구조로 나타내는 방법이다.
  • 위의 예시는 k = 3이라고 가정한 예시

❓ 만약 Range Query로 질의가 요청되면 어떻게 하지?

• MBB(분할한 공간)끼리 범위가 당연히 overlap된다. ⇒ 왜? Space가 아닌 Data partition이니까 !