공간 데이터 베이스 - 최근접 이웃 검색(R-tree)
R-tree에서 최근접 이웃 검색
1. 개요
Vector DB에서 말하는 그 최근접 이웃이 맞다. 물론 공간 데이터베이스는 2차원 혹은 3차원을 주로 다루기 때문에 VectorDB의 최근접 이웃 탐색보다 더 먼저이며, ANN을 다루는 것고 달리 공간 데이터 베이스에서는 진짜로 제일 가까운 값을 반환해주어야한다.
이를 위한 방법에 대해서 이번 포스팅간에 알아보겠다.
2. Depth-first Search
쿼리를 Q라고 하자. 이 Q에서 가장 가까운 점 또는 객체를 찾기 위한 가장 심플한 방법이다. DFS라고 하지만 사실 R 트리를 하나씩 Search해서 알아보는 것과 같다. 각각의 Entry들과 Q를 비교하여 가장 가까운 것을 뽑아내는 것으로 사실상 전체 검색과 다를바 없다.
3. Branch and bound
95년도 sigmod에 나온 논문으로 여기서는 각 Node별로 우선순위큐가 있다. 그리고 우선 순위는 기본적으로 MINDIST에 의해 결정되며 가지치기를 위한 MINMAXDIST가 있다. 쿼리를 Q라고 하자.
1) MINDIST
MINDIST는 Q에서 대상 MBB에서 가장 가까운 거리를 MINDIST라고 한다. 변에 가깝다면 변에 직교하는 형태이거나, 혹은 모서리에 접하는 형태이다. 모든 MBB에 대해서 MINDIST를 구했을 때 가장 작은 MINDIST보다는 긴 거리에 최근접 이웃이 있다.
2) MINMAXDIST
가장 가까운 변의 가장 먼 거리를 말한다. 그래서 가장 가까운(MIN)곳에서 먼(MAX)거리라고 MINMAXDIST이다.
이 거리가 설명하는 것은 어떤 최근접값은 모든 MBB의 MINMAXDIST중에 가장 작은 값보다 짧은 거리내에 최근접 이웃이 있다는 뜻이다.
3) Branch pruning
위와 같은 MINDIST와 MINMAXDIST를 통해 가지치기를 할 수 있다.
- 상위 노드에서 하위 노드로 탐색시 : 어떤 MBB인 R에 대해서 MINDIST가 어떤 MBB인 R’의 MINMAXDIST보다 크다면 R에 대해서 탐색하지 않아도 된다.
- 상위 노드에서 하위 노드로 탐색시 : 어떤 MBB인 R에 대해서 실질 객체 O와의 거리가 R의 MINMAXDIST보다 크다면 객체 O는 탐색하지 않아도 된다.
- 하위에서 상위노드로 다시 올라올시 : 어떤 MBB인 R에 대해서 실질 객체 O와의 거리가 R의 MINDIST 보다 작다면 R은 더 탐색하지 않아도 된다.
4) 알고리즘
위 가지치기 규칙을 기반으로 아래와 같은 알고리즘으로 탐색을 진행한다. 위에서 미리 언급했다 시피 R 트리의 각 노드는 우선순위 큐를 가지고 있으며 이를 ABL(Active Branch List)라고 한다. 여기서 우선순위 대상은 MINDIST가 작은게 가장 앞으로 와 있다.
- MINDIST를 무한으로 초기화한다.
- 루트부터 시작하여 깊이 우선 방식으로 R 트리를 탐색한다. 각 인덱스 노드에서 모든 MBR을 정렬 기준(ordering metric)을 사용하여 정렬하고 ABL에 넣는다.
- 각 노드는 적은 수의 엔트리를 갖는 자체 ABL을 유지한다.
- ABL에 가지치기 규칙 1과 2를 적용한다.
- ABL이 비어 있을 때까지 순서대로 MBR을 방문한다.
- 리프 노드인 경우, 실제 거리를 계산하고, 지금까지 가장 가까운 이웃(NN)과 비교하고, 필요한 경우 업데이트한다.
- 재귀에서 복귀할 때 가지치기 규칙 3을 사용한다.
- ABL이 비어 있으면 현재 최근접 이웃을 반환한다.
추가 업데이트 예정
4. Best-First
1999년 Hellerstein과 Stonebraker가 제안한 방식으로 각 노드마다 ABL 큐가 있는 방식과 달리 글로벌 우선순위 큐 하나만 유지하는 방식이다.
Branch bound 방식이 DFS에 가까웠따면 Best-first 방식은 BFS에 가까운 방식이다.
1) 알고리즘
- 글로벌 힙 H(priority queue)을 만드는데, 키는 각 엔트리(인덱스 엔트리 또는 객체)에 대한 MINDIST이다.
- 초기화: 힙 H에 루트 엔트리(root)를 넣는다.
- H가 비어있지 않다면 힙에서 MINDIST가 가장 작은 항목을 꺼낸다.
- 그 항목이 인덱스 엔트리(내부 노드) 이면, 그 엔트리의 자식들(즉 자식 MBR들 또는 자식 엔트리들)을 힙에 삽입한다(각자 MINDIST 계산하여 키로 사용).
- 그 항목이 객체(데이터 포인트) 이면, 이 객체를 최근접 이웃(NN) 으로 반환하고 알고리즘 종료.
5. Full Blown Algorithm
Full-Blown 알고리즘은 MINDIST를 기준으로 우선순위 큐(H)를 유지하면서, 동시에 MINMAXDIST를 이용해 현재 가능한 상한(δ)을 점점 좁혀가며 MBR(엔트리)들을 적극적으로 가지치기하는 R-tree 기반의 branch-and-bound 방식이다.
1) 알고리즘
- 글로벌 힙 H(priority queue)을 만드는데, 키는 각 엔트리(인덱스 엔트리 또는 객체)에 대한 MINDIST이다.
- 초기: H에 루트 엔트리 삽입한다. 가장 작은 MINDIST 엔트리가 앞으로 온다.
- δ ← +∞ 현재 알고 있는 NN 거리의 상한으로 처음엔 무한대이다.
- H가 비어있지 않다면 힙에서 MINDIST가 최소인 항목인 e를 꺼낸다.
- 만약 e가 객체(object) 면 그 객체를 NN으로 반환하고 종료한다.
- 그렇지 않고 e가 페이지(node)(인덱스 엔트리)면 페이지 PAGE(e) 안의 각 엔트리 se에 대해 MINDIST(q,se) ≤ δ 인 것들만 골라 H에 삽입한다.
- 그리고 (가능하면) δ를 MINMAXDIST(q,se)로 감소시킨다(즉 δ←min(δ,MINMAXDIST(q,se)) ).
- e가 객체가 나올때까지 반복한다.
추가 업데이트 예정
참고자료
- Shashi Shekhar and Sanjay Chawla, Spatial Databases: A Tour, Prentice Hall, 2003
- P. RIigaux, M. Scholl, and A. Voisard, SPATIAL DATABASES With Application to GIS, Morgan Kaufmann Publishers, 2002