k-최근접 이웃(k-nearest neighbours, k-NN) 찾기는 검색 엔진과 추천 시스템 등 많은 응용에서 핵심적인 기본 연산 중 하나이다. 그러나 방대한 양의 고차원 점들로 이루어진 거대한 컬렉션에서 k-NN 점을 탐색할 때, 그 계산 비용은 극도로 높다. 지역성 민감 해싱(locality-sensitive hashing, LSH)은 k-NN의 효율적인 근사화를 위해 도입되었지만, 기존의 어떤 LSH 접근도 다른 접근을 명확히 능가한다고 보기 어렵다. 본 연구는 다양한 데이터셋에서 매우 효율적으로 근사 k-NN 점을 찾는 새로운 LSH 접근인 Signature Selection LSH (S2LSH)를 제안한다. S2LSH는 다양한 크기를 갖는, 고도로 다양화된 시그니처 영역(signature regions)의 대규모 풀(pool)을 먼저 구성한다. 질의 점이 주어지면, 이 시그니처 풀에서 선택된 효과가 뛰어난 시그니처 영역들을 병합하여 질의에 특화된 시그니처 영역을 동적으로 생성한다. 또한 S2LSH의 변형인 S2LSH-M을 제안하며, 질의에 특화된 특징과 최적화 기법을 활용하여 다수의 질의를 보다 효율적으로 처리한다. 광범위한 실험을 통해, 본 접근들의 성능이 다양한 환경에서 우수함을 입증하였다.

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