정밀도 개선을 위한 순열 기반 추가 루프를 적용한 이동 정렬 기반 근사 k개 최근접 검색 알고리즘 (Shifted Sorting-based k-Approximate Nearest Neighbor Searching Algorithm with Extra Loops Based on Permutation for Better Accuracy)

서지정보

· 발행기관 : 한국디지털콘텐츠학회
· 수록지 정보 : 디지털콘텐츠학회논문지 / 22권 / 2호 / 325 ~ 330페이지
· 저자명 : 박태정

초록

인공지능과 빅데이터의 적용 범위가 확대됨에 따라 다차원 벡터 공간 상에서 특정한 질의 지점을 나타내는 벡터로부터 가장 가까운 순서로 k개의 데이터 벡터를 찾는 알고리즘(kNN)이 다양한 분야에서 활용되고 있다. 특히 자율주행과 같은 실시간 애플리케이션, 실시간 온라인 문서 검색 등에 대한 수요가 증가하면서 kNN 알고리즘의 병렬화, 고속화가 진행되고 있다. 이러한 실시간 애플리케이션에 적용하기 위해 어느 정도의 정밀도를 희생하면서 빠른 시간 내에 검색을 수행하는 근사 k개 최근접 검색 알고리즘(kANN)도 널리 사용되고 있으며 shifted sorting 기반 kANN 알고리즘은 GPU 병렬처리에 적합한 구조를 가지고 있다. 그러나 shifted sorting 기반 kANN 알고리즘은 정밀도를 컨트롤 할 수 있는 방안이 연구되지 않았다는 한계가 있다. 본 논문에서는 기존 shifted sorting 기반 kANN 알고리즘의 원리를 살펴 봄으로써 정밀도를 개선할 수 있는 방안을 논의하고 구체적인 방식으로 각 축의 순서를 순열을 통해 재배치한 후 Morton 코드를 생성하고 기존 방법을 적용함으로써 약간의 시간을 희생하고 상대적으로 높은 정밀도를 달성하는 개선 방안을 제안한다.

영어초록

The k-nearest neighbor (kNN) search algorithm - which finds the k-nearest data vectors for query vectors - has been increasingly applied to various applications including artificial intelligence and big data analysis. Some realtime applications like autonomous driving and online document search require fast parallel kNN algorithms for fast response to environment or user interaction. For this purpose, the k-approximate nearest neighbor (kANN) searching algorithms reduce process time with sacrification of certain level of accuracy. Among various approaches, the shifted sort-based kANN method is well suited for GPU parallel implementation but there have been no ways to control accuracy of the results. In this paper, I examine and discuss the feature of shifted sort-based kANN method which affects accuracy and present a method to improve its accuracy. The suggested method adopts extra loops based on permutation of vector axes for better accuracy. The test results show that we can achieve improvement in accuracy at a slight cost of increased processing time.

참고자료

· 없음