RNN

RNN 정의

q를 nearest neighbor로 하는 것을 찾는 것임 (p2, p3)

eg) 통신회사에서 요금제를 개발했을 때, 누구에게 요금제를 광고하는 것이 효과적일까?

해당 요금제와 가장 유사한(가까운) 요금제를 쓰는 사람에게 홍보하는 것이 좋음

 

RNN(p2)={ } 공란임 (참고로, RNN(p3)={q}, NN(q) = p3 )

따라서, RNN은 대칭 관계가 아님

 

 

 

RNN 알고리즘 개요

 

 

1. [KM00] KM method : pre-computing

1. 모든 점p1~4에 대해 NN을 찾고

2. 그 거리를 반지름으로 하는 원(vicinity circle)을 그림

3. RNN tree를 build함(MBR)

4. q가 포함된 원의 중심이 q의 RNN임 = p3, p4

* 미리 모든 P에 대한 NN을 계산해야되므로 overhead가 존재함

* 데이터(p)에 대한 update가 발생시, tree를 다시 구성해야함

위의 그림과 같이 원래는 하얀색 원이었는데,

p5가 추가 된 경우, p3와 p4의 원은 회색원으로 update되어야함

 

 

[KM00] KM method 장단점

장점: 빠르게 Point query를 수행할 수 있음 (RNN-tree사용)

단점:

1. 미리 모든 P에 대한 NN을 계산해야되므로 overhead가 존재함

2. 데이터(p)에 대한 update가 발생시, tree를 다시 구성해야함

 

 

 

2. SAA

1. 각 영역을 6개로 쪼갬

2. 각 영역 내에서 q와 가장 가까운 점들을 찾음 (=q의 NN을 찾음)

3. 각 점들의 NN을 찾았을 때 그것이 q가 아니면 제외시킴

→ 아래에서 p2의 NN은 p1 (p3도 마찬가지이므로) 둘 다 제외

 

단점: 차원이 높아질 수록 영역이 exponentially increase됨

 

 

 

3. SFT

Step 1: Given k=4, Find 4NN Candidates Set = {p6, p5, p4, p2}

            q근처의 4-NN에 해당하는 점을 찾음

Step 2: Discard p4 and p5 since they are closer to each other than q

            q보다 더 가깝게 위치한 점들을 제거함 (p4, p5)

            왜냐하면 이 두점은 q의 RNN이 될 수 없음(각 두점끼리 서로 더 가까우므로)

Step 3: Boolean Range Queries (p2, dist(p2,q)) and (p6, dist(p6,q))

             남은 두점을 중심으로, q와의 거리를 반지름으로 하는 원을 그림

Step 4: Discard p2 since minmaxdist(N1,p2) <= dist(p2,q) False miss: p3 due to k =4.

            그 원 안에 다른점이 존재한다면 해당 점은 제외시킴 

            (p2는 p1과 더 가까움. q 보다)

 

단점: False miss가 존재할 수 있음

→ 왜냐하면 k개의 후보외에 답이 있다면 찾을 수 있음

→ k가 작을 수록 false miss가 많음

p3도 q의 NN이지만 k=4이므로 그 집합에는 포함이 안됨

 

 

 

Half-plane prunning (아래 두 그림 제대로 이해하기) 

• q의 RNN찾기

직선위의 어떤점도 q를 RNN으로 갖지 않으므로,

(p를 RNN으로 갖기 때문에) 직선 위에 있는 모든 점은 제외시킴

→ N1은 pruning의 대상임

 

 

직선에 교차하여 MBR이 있는 경우

 

p1이 있을 때, N2는 직선과 교차하므로 pruning 시킬 수 없었음

새로운 점 p2가 들어오면서 q-p2를 연결하는 직선에 수직인 선분을 그음

그 때, N2는 노란색 영역에 포함되므로 pruning 시킬 수 있음

 

 

 

 

Computing the residual region

각 점이 추가될수록 (P1~P3) 

점점 선분이 추가되며, 그에따라 음영 영역이 다각형이됨

(계속 선분에 교차되므로)

→ MBR을 표시할때 사각형이 아니면 표현하기가 어려움

해결책: 

실제 남아있는부분(회색 영역)보다 조금 더 붙여서 사각형을 만들어 줌

사각형으로 추정한 영역은 superset이므로 이렇게 영역을 추가했을때,

한쪽선분으로 완전히 넘어가면 pruning 대상임

 

 

 

4. TPL algorithm 

TPL algorithm - q의 RNN을 찾아라

[Filtering step]

Srfn: refinement, Scnd: candidate

1. q에서 가장가까운 노드를 heap에 가까운 순서로 넣어둠

 

 

2. leaf 노드에 도달하면 두 점중 가장 가까운 점을 Scnd에 넣어줌

3. 노란색에 있는 MBR은 q-RNN이 될 수 없으므로 모두 삭제함

단, N11은 선분에 교차되어있으므로 pruning할 수 없음

단, N4, N6은 pruning 됨 →  refinement로 들어감

N5는 pruning할 수 없으므로 heap에 추가 됨

 

단 N5가 heap에 추가될때 영역은 아래 작은 빨간사각형과 같이

residual영역을 추가한 상태로 heap에 입력 됨

 

4. 작은사각형 안에 있는 leaf노드 중 가장 가까운 것은 p2이므로 

p2는 candidate에 추가, p6는 refinement에 추가 됨

그리고 p2와 q를 이어 수직으로하는 노란색 영역을 찾음

5. N12는 pruning 되고, N1영역은 직선과 교차되므로 N1을 검토함

따라서, N1의 leaf노드인 p5는 candidate에 추가되고, p7은 refinement에 추가 됨

 

 

[Refinement step]

1. p1, p2, p5각각의 거리가 q보다 가까운지 파악함(빨간원)

2. refinement에 있는 것을 point그룹과 MBR그룹으로 나눔

    {p3, p6, p7}, {N4, N6, N2, N12}

3. p3, p6, p7이 빨간원안에 포함되는지 찾아봄

    p1의 NN은 p3가 됨을 알수 있음

     → 그러므로 p1은 탈락

    {p3, p6, p7}로의 검증은 끝남 더 이상 원안에 있는 {p3, p6, p7}포인트가 없음

4. MBR중 원밖에 있는 MBR은 pruning 대상

    P2를 기준으로  N2, N6는 pruning 대상임

    남은 {N4, N12} 중 P5를 기준으로 {N4, N12} 모두는 pruning 대상임

    → p5는 q-RNN결과임

5.  P2를 기준으로  {N4, N12} 는 겹치므로 RNN tree의 leaf노드와의 관계를 확인함

     N4를 봤을 때, 그안에 P2와 가까운 P4가 있으므로 P2는 q-RNN이 될 수 없음 (탈락)

6. candidate가 empty가 되므로 종료함.