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