k-최근접 이웃(k-nearest neighbor, k-NN) 검색은 주어진 데이터셋에서 질의 점에 가장 가까운 k개의 점을 찾는 것을 목표로 한다. k-NN 검색은 다양한 응용 분야에서 중요하지만, 고차원 대규모 데이터셋에서는 그 계산 비용이 극도로 커진다. 이러한 성능 문제를 해결하기 위해, 점들 사이의 상대적 거리 관계를 보존하면서 확률적 차원 축소를 수행하는 방법으로 로컬리티 민감 해싱(locality-sensitive hashing, LSH)이 제안되어 왔다. 그러나 기존 LSH 기법들의 성능은 여전히 일관적이지 않아, 일부 데이터셋에서는 탐색 시간이 크게 증가하는 반면 k-NN 근사 정확도는 낮은 경우가 있다. 본 논문에서는 k-NN 검색의 성능을 향상시키고, 다양한 데이터셋에서 잘 동작하는 일관된 k-NN 검색을 달성하는 데 초점을 맞춘다. 이를 위해 Signature Selection LSH(S2LSH)라 불리는 새로운 LSH 기법을 제안한다. 먼저, 서로 다른 크기와 모양의 시그니처 영역(signature regions)들을 포함하는, 높은 다양성을 갖는 시그니처 풀을 생성한다. 다음으로 주어진 질의 점에 대해 해당 질의의 시그니처 영역을 순위화하고, 높은 순위의 시그니처 영역에 포함된 점들을 질의의 k-NN 후보로 선택한다. 광범위한 실험 결과, 본 접근법은 최첨단 LSH 기법들에 비해 일관되게 더 우수한 성능을 보이는 것으로 나타났다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.