최근접 이웃 검색(Nearest-neighbor search)은 컴퓨터 그래픽스에서 기본적인 원시 요소이며, 거리장 계산(distance field computation), 표면 재구성(surface reconstruction), 포인트 클라우드 등록(point cloud registration) 등 다양한 응용 분야에 사용됩니다. 많은 그래픽 애플리케이션에서 데이터 포인트는 3차원 공간에 내재된 표면 매니폴드(surface manifold) 위에 위치하는 반면, 쿼리는 주변의 전체 부피(volume)에 걸쳐 분포합니다. 이러한 환경에서는 k-d 트리나 그리드와 같은 공간 분할 구조가 비효율적이 될 수 있습니다.
동적 계획법 기반 최근접 이웃 검색(Dynamic-programming-based nearest-neighbor search, DP-NNS)은 대안을 제시합니다. 이는 점진적 Delaunay 구성의 이력을 기록하는 후속자 DAG(successor DAG)를 순회하며, 종종 공간 분할 구조보다 우수한 성능을 보입니다. 하지만, DP-NNS는 순차적인 구성 과정이 느리고, 단순한 병렬화는 쿼리 성능을 저하시켜 실질적인 채택에 한계가 있었습니다.
본 논문에서는 DP-NNS의 쿼리와 구성 과정을 모두 가속화합니다. 쿼리의 경우, 후속자 DAG 상에서 유효한 시작점을 미리 계산하는 그리드 기반 초기화 전략(grid-based initialization strategy)을 도입하여 검색 경로를 단축시키면서도 정확성을 유지하고 두 배의 속도 향상(twofold speedup)을 가능하게 했습니다. 구성 과정에서는 병렬 삽입이 쿼리 비용에 어떻게 영향을 미치는지 분석하고, 제시된 기하학적 가정 하에서 로그 시간 복잡도의 기대 쿼리 비용을 보존하는 병렬 알고리즘을 개발했습니다.
저희의 병렬 구성 알고리즘은 순차적인 기준선 대비 10배의 속도 향상을 달성하면서도 거의 동일한 쿼리 비용을 유지합니다. 또한, 캐시 지역성(cache locality)을 개선하기 위해 쿼리 포인트의 재정렬 작업을 수행했습니다. 광범위한 실험 결과는 저희 방법이 최근접 이웃 쿼리 성능 면에서 널리 사용되는 라이브러리보다 우수함을 입증합니다.