Journal Archive

그림 1은 [1]에서 발췌한 그림으로 기존의 이동 정렬 기반 근사 k개 최근접 검색 알고리즘의 작동 방식을 제시하고 있다. n차원 벡터 공간에서 데이터 및 질의 벡터(파란색 점)가 1차원 Morton 코드 공간(분홍색 선)으로 투사된 후 이 1차원 공간에서의 근접 관계를 파악할 때의 문제(왼쪽)를 설명하고 이 문제를 해결하기 위해서 전체 벡터를 (2차원의 경우) [1,1] 벡터 방향으로 정해진 거리와 횟수(Chan의 lemma 3.3, [5]의 3.1절)만큼 이동시켜서 계산([1]의 Algorithm 1 참고)한다. 그러나 기존 shifted sorting 기술은 빠른 실행 속도가 가능하다는 장점에도 불구하고 특정 방향으로만 이동(shifted) 연산을 수행하여 정확도가 지나치게 떨어진다는 문제가 있다. 다시 말해 기존 기술이 근사 최근접 이웃 검색(kANN) 방식이라는 전제가 있기는 하지만 기존 기술이 원점에서 출발하여 벡터 공간에서 원점에서 멀어져 가는 방향으로만 정해진 정수 횟수만큼 이동한 후 질의 벡터와 데이터 벡터 모두를 Morton 코드로 투사하여 1차원 공간 상에서 정렬 후 탐색을 수행하기 때문에 실제 벡터 공간 상에서는 가깝더라도 Morton 코드 상의 1차원 공간에서는 거리가 먼 것으로 판단되어 큰 오류가 발생한다. 물론, 이러한 오류는 Chan의 lemma 3.3에 의해 허용 가능한 오차 한계 이내로 한정된다는 사실이 증명되었음에도 불구하고 기존 shifted sorting 기술은 한 마디로 다차원 데이터를 1차원 공간으로 투사하고 특정한 방향으로만 이동(shift)하면서 새롭게 발견된 가장 가까운 데이터 벡터들을 찾아서 지금까지 알고 있는 가장 가까운 데이터들을 갱신하는 과정을 거치기 때문에 오류가 발생한다고 결론을 내릴 수 있다.

Fig. 1. 
Conventional shifted sorting-based k-approximate nearest neighbor searching method

그림 2에서는 기존 알고리즘[1]의 전체적인 순서도를 정리한다.

Fig. 2. 
Flowchart for traditional shifted sorting-based k-approximate nearest neighbor searching method

전술한 기존 shifted sorting kANN 방식은 Morton 코드를 비트 단위로 변환해서 좌표축에 대한 한 가지 순서 (x, y, z) 로만 구성한다. 이러한 구성은 합당한 이유가 있는 것은 아니고 자의적인 순서이며 기존 octree의 구현에서 child tree node 배치 구성에서의 순서의 영향을 받은 것으로 보인다. 그림 5에서 볼 수 있듯이 공간 상에서 Morton 코드를 1비트 씩 증가시키면서 진행하면 Morton 코드가 3차원인 경우 octree, 2차원인 경우 quadtree가 탐색하는 공간과 동일한 공간을 순서대로 탐색하는데 그림 3 내 왼쪽 그림에서는 (x, y) 순서대로 생성한 Morton 코드의 탐색 방향을 볼 수 있고 오른쪽 그림에서는 (y, x) 순서대로 생성한 Morton 코드의 탐색 방향을 볼 수 있다. Morton 코드의 생성 방식과 기하학적인 의미, 비트 단위의 배치의 의미에 대한 세부적인 사항은 [6]을 참고한다.

논의한 한계를 보완하기 위해 본 논문에서는 Morton 코드 상의 1차원 공간에서 실제 벡터 공간 상의 공간적 배치를 보다 정확하게 반영할 수 있도록 하여 정확도를 개선하는 새로운 알고리즘 – 순열 적용 이동 정렬 기반 근사 k개 최근접 검색(permutated shifted sorting-based kANN searching) 알고리즘을 제안한다. 제안하는 새로운 알고리즘에서는 벡터의 각 원소의 순서를 순열로 변환한 후 기존 shifted sorting kANN 연산을 반복 수행한다(그림 5). 예를 들어 3차원 벡터의 경우 3! = 6개의 순열 조합 (x, y, z), (y, z, x), (z, x, y), (x,z,y), (y,x,z), (z,y,x)에 대해 각각 기존 shifted sorting의 연산을 수행하게 되는데 이러한 6개의 순열에 대해 각각 3차원 기하 정보를 1차원 기하 정보인 Morton 코드로 변환하여 1차원 Morton 코드 상에서 각 질의 지점을 기준으로 가장 가까운 k개의 데이터 지점 업데이트를 수행한다.

Fig. 5. 
Flowchart of the suggested improvement by applying extra loop based on permutation

예를 들어 2차원 예제의 경우 기존 방법은 그림 4에서 2차원 공간 상에서 질의 점 및 데이터 점(파란색 점)의 유클리드 거리 기준 최근접점을 근사적으로 찾기 위해 연산을 줄일 수 있는 1차원 공간인 Morton 코드(빨간색 선) 상에서의 순서(빨간색 선 상의 화살표로 표시)를 기준으로 데이터를 정렬한 후 이 1차원 공간 상에서 서로의 거리를 측정한다.

Fig. 4. 
Suggested improvement by applying extra loop based on permutation

(x, y) 순서로만 Morton 코드를 생성한 후 이동시키는 기존 방법(그림 1)에서 볼 수 있듯이 Shift 연산 전에는 2차원 공간 상에서 가까운 점 a와 b가 실제로 가깝지만 1차원 공간인 Morton 코드 상에서는 아주 먼 거리로 파악한다.

따라서 기존 방법에서는 일정한 거리를 shift시킨 후 1차원 Morton 코드 상에서 각 점과 가장 가까운 점을 계속 기억하면서 새로운 가까운 점이 나타나면 가장 가까운 점들의 정보를 갱신한다. 그러나 xy 순서로만 1차원 Morton 공간을 생성해서 탐색하는 기존 방식은 2차원 공간에서 실제로 가까움에도 불구하고 1차원 Morton 공간에서 먼 것으로 파악하는 문제가 여전히 발생하는데 또한 이 문제는 데이터/질의 지점의 차원이 증가하더라도 1차원 Morton 코드에서만 최근접점들을 찾는데 차원이 증가하면 실제로 가까움에도 불구하고 1차원 Morton 공간에서 먼 것으로 파악하는 문제의 발생 빈도가 더 증가한다.

이 논문에서 제안하는 방법에서는 이러한 누락되는 정보가 발생하는 빈도를 줄이기 위해 Morton 코드를 구성할 때 순열을 적용하고 기존 shifted sort 정렬 방식을 반복함으로써 Morton 코드가 보다 정확하게 가까운 최근접점들을 찾을 수 있도록 한다. 따라서 그림 4에서 제시하듯이 제안하는 방식에서는 오른쪽에서 2차원 사례에 대해 (x, y)뿐만 아니라 (y, x)를 기준으로도 Morton 코드를 구성하고 검색을 실행한다. 이 과정은 제안하는 알고리즘을 정리한 그림 5에서 step 1부터 반복 수행되는 외부 루프로 적용된다.

이렇게 다차원 벡터에서 모든 순열을 조합하여 Morton 코드를 구성하고 각 Morton 코드에서 최근접점을 찾음으로써 알고리즘의 정밀도를 향상시킬 수 있다. 또한 3차원 벡터뿐만 아니라 보다 일반적인 n차원 벡터로의 확장도 가능하며 n차원 벡터의 경우 n!개의 순열 조합을 적용한다.

이 절에서는 제안하는 솔루션을 평가하기 위한 테스트 방식과 결과를 논의한다. 테스트 환경으로 Intel Xeon CPU 2.20 GHz, RAM 125GB 하드웨어 환경에서 구동되는 Ubuntu 18.04 LTS OS에서 CUDA 10.2 버전으로 작동하는 NVIDIA 2080Ti GPU 1개를 사용하여 테스트를 수행하였다. 테스트 결과, 제안하는 솔루션의 경우 n차원 벡터에 대해 n! 회만큼 반복 연산이 추가되기 때문에 전체적인 시간은 n!에 선형적으로 비례해서 증가할 것으로 예상되었으나 표 1에서 제시한 것처럼 추가된 루프로 인한 시간 증가는 선형적으로 증가하지 않고 선형적인 시간 증가보다 약간 감소하는 경향을 보였다. 이러한 특징은 GPU 처리를 위한 CUDA 아키텍처가 컴파일러 차원에서 컴파일 전 루프의 반복 횟수(여기에서는 3!=6회)가 알려진 경우 최적화(loop unrolling)[7]를 수행하고, 동시에 병렬 방식으로 처리할 데이터의 양이 많아지면 GPU 내 warp 스케줄러의 성능이 최적화[8]되어 성능이 증가하기 때문으로 판단된다. 따라서 그림 2의 코드를 n! 회만큼 반복하는 새로운 방법(그림 5)은 n이 아주 크지 않은 범위 내에서는 전체 실행 시간이 다른 기술(예. CPU 기반 또는 GPU tree 기반 검색 알고리즘)보다 빨라진다. 이에 비해서 기존 방식과 비교했을 때 정밀도가 상대적으로 크게 향상되는 장점을 얻을 수 있었다.

Fig. 3. 
Different orders in Morton codes : left (x,y), right (y,x)

2) 결과 분석 – 실행 시간

비교를 위하여 표 13에서 테스트 결과를 정리하였다.

표 1과 그림 6, 7, 8을 통해 제안하는 알고리즘의 특성을 확인할 수 있다. 먼저 제안하는 알고리즘은 허용 가능한 범위 내에서 계산 시간이 증가한다. 즉, 제안하는 방식은 3차원의 경우 3!=6배 많은 반복 루틴을 실행하나 대기 중의 작업 부하의 크기가 증가할수록 병렬 연산 효율이 증가하는 GPU의 하드웨어적인 측면 때문에 실행 시간은 정확하게 6배로 증가하지 않고 2.38배~4.2배 정도에 그치는 것을 볼 수 있다(표 1의 시간에 대한 Ⓑ/Ⓐ 비율 및 그림 6 참고). 제안하는 방식이 실행 시간이 최대 4배 정도 증가한다는 사실만 보면 실행 시간이 증가하더라도 데이터와 질의 개수가 각각 210개인 경우 0.55/0.0062 = 88.7배, 215개인 경우 23.73/0.045 = 527.3배로 연산 시간 측면에서 CPU 방식(kd-tree) 대비 상당히 빠른 속도라고 볼 수 있다(그림 7).

Fig. 6. 
Process time comparison between the previous method and the suggest one (“permutation”) (unit: seconds)

Fig. 7. 
Process time comparison among CPU-based kd-tree, the previous method, and the suggest one (“permutation”) (unit: seconds)

Fig. 8. 
Error (root mean square) comparison between the previous method and the suggest one (“permutation”)