FARGO: 전역 다중 프로빙을 통한 빠른 최대 내적 검색

01/01/2023

최대 내적 검색 이해하기: 이론에서 실제까지

머신러닝과 인공지능이 계속 발전함에 따라, 고차원 벡터 공간을 효율적으로 검색하는 능력은 점점 더 중요해지고 있습니다. 이 영역의 근본적인 과제 중 하나는 최대 내적 검색(Maximum Inner Product Search, MIPS) 문제로, 주어진 쿼리 벡터와의 내적을 최대화하는 데이터셋 내 벡터를 찾는 것을 포함합니다. 이 연산은 추천 시스템, 다중 클래스 레이블 예측, 유사 항목 검색, 구조적 SVM, 딥러닝을 포함한 수많은 애플리케이션의 핵심입니다.

공간 분할 트리를 사용하는 전통적인 MIPS 접근 방식은 차원이 증가함에 따라 기하급수적으로 느려져, 수백 또는 수천 차원을 다루는 경우가 많은 현대 애플리케이션에는 실용적이지 않습니다. Locality-Sensitive Hashing(LSH)은 근사 최근접 이웃 검색에 효과적임이 입증되었지만, 내적 유사도의 고유한 특성 때문에 MIPS에는 직접 적용할 수 없습니다. 조직들이 점점 더 대규모의 고차원 데이터셋을 처리함에 따라, MIPS를 위한 효율적이고 확장 가능한 솔루션의 필요성은 그 어느 때보다 절실해졌습니다.

이 논문은 MIPS 문제에 접근하는 방식을 혁신하는 새로운 프레임워크인 FARGO를 소개합니다. 우리는 현재 MIPS 솔루션, 그 한계, 그리고 FARGO가 글로벌 멀티 프로빙과 random XBOX transformation을 포함한 혁신적인 기법을 통해 이러한 과제를 어떻게 극복하는지에 대한 포괄적인 분석을 제시합니다. 우리의 프레임워크는 기존 방법에 비해 뛰어난 정확도와 효율성을 달성할 뿐만 아니라, 대규모 고차원 데이터를 다루는 실제 애플리케이션을 위한 실용적인 솔루션도 제공합니다.

백서 받기