공간 데이터 베이스 - RNN(Reverse nearest neighbor)

RNN(Reverse nearest neighbor)

1. 개요

RNN은 Query q에 대해 어떤 점 p가 p의 최근접이 q인 경우 p를 q의 역최근접 이웃으로 간주하는 개념으로, 직관적으로 q가 특정 점들의 NN이 되는 집합을 찾는 문제를 말한다.

q의 가장 최근접이 p일 때 q 역시 p의 가장 최근접이 아닌가 하고 그냥 언뜻 생각하면 그렇게 생각할 수 있지만 꼭 역이 성립하지는 않는다.

위와 같은 경우에는 q의 가장 최근접 이웃은 p이지만 p의 최근접 이웃은 s이다.

2. Precomputing

1) KM00

KORN과 Muthukrishnan이 00년도에 냈다고 KM00이라고 붙은 것 같다.
이 방법을 정리하자면 굉장히 간단하다.

모든 데이터점 p에 대해 NN(p)을 사전 계산하고 이를 기반으로 p의 근방을 원(비서티 원)으로 표현한 뒤, 모든 원의 MBR을 R-tree(RNN-tree)에 색인하여 q를 포함하는 원들의 집합을 RNN(q)로 반환한다. 두 개의 트리(RNN-tree와 데이터 R-tree)가 필요하다는 점이 구현·유지 비용으로 작용한다.

2) YL01

Congjun Yang과 King-Ip Lin이 01년도에 만들었다고 YL01이다.
KM00과 같이 별도의 RNN-tree를 유지하는 것까지는 같으나 구조가 다르다.

논문이 제안하는 RdNN-tree는 잎 노드에 각 데이터점 p의 비서티 원(중심 p, 반경 = NN(p)까지의 거리)을 저장하고, 내부 노드는 하위 원들의 최소 경계 사각형(MBR)들을 보관한다. 이렇게 하면 질의 시 점 위치 질의를 통해 q를 포함할 수 있는 원들의 후보 집합을 신속히 결정할 수 있으며, 원의 유지·갱신도 R-tree 연산으로 처리 가능하다.

3. Filter/refinement

1) SAA

a. 필터 단계

질의점 q를 중심으로 공간을 6개의 동일 각도(60°) 영역 S₁, S₂, …, S₆로 분할하고, 각 영역 Sᵢ 내에서 q에 가장 가까운 점(NN(q) in Sᵢ)을 찾아 후보 키 집합에 추가한다. 이렇게 하면 최대 6개의 후보 점이 수집되며, 사전에 모든 점의 NN을 계산·저장할 필요가 없어 KM00 대비 갱신 부담이 줄어든다.

b. 정제

각 후보 p에 대해 다음 두 조건 중 하나가 성립하는지 확인한다.

• p ∈ RNN(q): p의 실제 최근접 이웃이 q이므로 p를 결과에 포함한다.
• 해당 영역 Sᵢ에 RNN 없음: 영역 Sᵢ 내에 q를 최근접 이웃으로 갖는 점이 존재하지 않음을 확인하고, 해당 후보를 기각하거나 다른 후보를 결과로 확정한다.

c. 단점

영역 수가 차원에 대해 지수적으로 증가한다. 이 말은 2차원에서는 6개 영역이 충분하지만, 3차원 이상으로 확장 시 필요한 영역 개수가 급증하여 후보 탐색·비교 비용이 폭발적으로 늘어나므로 고차원 데이터에 적용하기 어렵다.

2) SFT

a. 필터

1. 먼저 질의점 q에 대해 k-최근접 이웃(kNN)을 계산하여 q 주변의 k개의 최근접 이웃 점들을 후보(key) 집합에 추가한다.
2. 일반적으로 이 k-NN은 R-tree와 같은 공간 인덱스를 이용해 수행하며, k값은 임의로 정해진다.

b. 정제

수집한 후보 p들끼리 서로를 거르며 일부 후보를 제거할 수 있습니다.

예를 들어, 다른 후보에 비해 q에서 멀리 떨어져 있을 경우 후보에서 제외되는 방식입니다. 남은 후보에 대해, 해당 점이 정말로 RNN(q)에 포함되는지 판정해야 합니다.

이를 위해 보통 불리언 범위 질의(Boolean range query)를 수행합니다:

후보 p에 대해, q와 p 사이의 거리가, 다른 어떤 데이터점 p′ 와 p의 거리보다 더 작은지 점검합니다. 실제로는, p를 중심으로 q까지의 거리만큼의 원(또는 영역)을 그려 두고, 그 원 내부(p에서 q까지의 거리보다 더 가까운 거리에) 다른 데이터점이 있다면 p는 제외됩니다.

c. 장단점 및 한계

• 불리언 범위 질의 과정에서, 처음 데이터점을 찾거나 노드 MBR 한 변 전체가 원 안에 들어오면 질의를 조기 종료할 수 있다.
• k값이 작을 경우 실제 정답을 포함하지 못하는 경우가 발생할 수 있고, 반대로 k를 크게 잡으면 후보 수가 불필요하게 많아져 성능이 저하될 수 있다.

4. TPL

모든 데이터는 R-tree에 색인되어 있고, RNN 후보 추출 및 검증을 위해 관리되는 두 가지 집합을 정의한다(필터 후보 집합 Scnd와 정제 후보 집합)

1) 필터

R-tree의 루트에서부터 우선순위 기반(힙)으로 순차적으로 노드를 탐색한다. 각 노드 또는 포인트에 대해 TPL의 가지치기 조건(예: 반평면 또는 MBR 근사 등)을 적용하여, 불필요한 노드·포인트를 건너뛴다. 후보 포인트가 필터 집합에 추가된다.

2) 정제

후보 집합(Scnd)에서 실제로 역최근접이웃이 될 수 있는지를 판정하기 위해 정제 집합(Srfn)을 활용한다.
포인트 $p$가 실제로 $q$의 역최근접이웃이 되려면, $p$의 실제 최근접 이웃이 $q$여야 하며, 다른 후보나 노드에 의해 가로막히지 않아야 한다.
만약 $p$가 다른 후보 포인트들(Prfn) 중 어느 것보다 $q$에서 멀거나, 정제 노드들(Nrfn)에 의해 잠재적으로 가로막힐 가능성이 있다면, $p$는 제거된다.
$p$에 대해 모든 정제 후보가 충분히 검증되면, 실제 RNN 결과로 확정된다.
mindist(최소거리) 기준으로 추가 방문이 필요하면, 힙에서 더 노드를 꺼내 정제 단계를 반복한다.

※ 추가 업데이트 및 검증 예정이다.

참고자료

• 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
• Korn, Flip, and S., Muthukrishnan. “Influence sets based on reverse nearest neighbor queries.” . In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data (pp. 201–212). Association for Computing Machinery, 2000.
• Tao, Yufei, Dimitris, Papadias, and Xiang, Lian. “Reverse kNN search in arbitrary dimensionality.” . In Proceedings of the Thirtieth International Conference on Very Large Data Bases - Volume 30 (pp. 744–755). VLDB Endowment, 2004.