Continuous Nearest Neighbor(CNN)

CNN정의 

CNN: Continuous에서 split points(s1, s2, s3)와 대응되는 NN을 찾는 것임

 

 

용어정리

1. split list: [s, s1, s2, s3, e]

2. vicinity circle: split point에 대응되는 원

3. cover: [a,c,f,h]들은 특정 구간에 있는 point u에 대해서 NN이기 때문에

                특정 구간을 cover한다고 할 수 있음

 

 

CNN법칙 Lemma 1.

- 점a가 추가 되었을 때, 

  s까지의 거리와, e까지의 거리를 반지름으로 하는 원을 그림

 

- 점c가 추가되었을 때, 원e 안에 존재하므로

  a와 c를 연결한 후, 수직인 선분을 그어 그점이 기존 s-e의 직선과

  만나는 원의 중심인 s1이 됨 

 

 

CNN 법칙 Lemma 2. Covering Continuity

점 p가 추가되었을 때 영향을 받는 원들은 연속으로 겹쳐있어야 함

(p는 원 si, si+1, si+2에만 영향을 줌)

 

 

 

R-tree 탐색 기법

Branch-and-bound 기법을 사용함

- leaf node를 만나는 경우, 점 p가 특정구간(예를 들어, s-e)을 커버하는 경우

  Lemma1의 법칙을 따라 update함

- internal node를 만나는경우 (intermediate entry)

  아래와 같이 heuristics방법을 사용함

 

 

Heuristics1 : point와 MBR간의 최단 거리를 구하는 방법 

1. 아래와 같이 mindist를 구하는 방법을 사용함

mindist = MBR의 각 꼭지점과 직선간의 거리와

split point와 MBR간의 최단거리 모두 중에서의 MIN값

 

SLmaxd = 가장큰 원의 반지름

위에서 mindist를 구하는 방법을 적용하여 mindist를 구함

- 비교 결과

MBR과 split point간의 mindist가 SLmaxd보다 크면 검색 시, 제외시킴

 

 

Heuristics2 : point와 MBR간의 최단 거리를 구하는 방법

 

노란색 mindist가 SLmaxd(파란선)보다 작으므로  heuristic1 case처럼 prunning이 불가능함

그러므로, 각각의 원과 비교하여 prunning할지 결정해야함

1. split point s를 기준으로 원의 반지름보다 mindist가 더 크므로 prunning함

   (원 밖에 있으므로 prunning가능)

2. split point s1를 기준으로 원의 반지름보다 mindist가 더 크므로 prunning함

   (원 밖에 있으므로 prunning가능)

3. split point e를 기준으로 원의 반지름보다 mindist가 더 크므로 prunning함

   (원 밖에 있으므로 prunning가능)

(참고. 첫 번째 heuristic방법은 하나의 원을 비교하는 것으로 간단히 prunning할 수 있었음)

 

 

 

Heuristics3 : Access order에 대하여

E1과 E2가 있을 때 mindist가 작은 순서로 먼저 탐색하는게 더 빨리 탐색할 수 있음

E1을 먼저 탐색한뒤 s1을 생성하면 E2는 prunning이 되지만

E2를 탐색한 후 신규 vincinity원을 생성하면 E1을 또 한번 탐색해야되는 과정을 거쳐야 됨

 

 

CNN 알고리즘 예시1)

p가 추가 되었을 때, 연속적인 s3, s4 원이 영향을 받음 (Covering Continuity)

그리고, s3의 NN인 c와 p를 연결하여 s3'를 찾고 기존 s3는 제거함

s4에대해서도 동일한 작업을 함

 

 

CNN알고리즘 예시2)

E1 root node아래로 탐색하는 경우

점 g는 원e안에 들어오는 점이므로 그 점을 기준으로 s1을 split point로 발견함

그 다음, d는 제거

그리고, E3와 se간의 거리는 는 SLmaxd보다 작으므로 prunning이 불가능함

b는 s-f를 반지름으로 하는 원안에 들어와 있으므로 b-f를 이등분하는 직선을 통해 s1을 추가함

E2 root node아래로 탐색하는 경우

E5는 반지름밖에 있으므로 prunning됨