Spann: 고효율의 십억 규모 근사 최근접 이웃 검색
- 제목: SPANN: 효율적인 수십억 규모 근사 이웃 검색
- 추상: 메모리 내 근사 이웃 검색(ANNS) 알고리즘이 빠른 고회수 검색을 위해 큰 성공을 거두었으나, 매우 큰 규모의 데이터베이스를 처리할 때는 비용이 많이 든다. 따라서 작은 메모리와 저렴한 SSD를 사용하는 하이브리드 ANNS 솔루션에 대한 수요가 증가하고 있다.
- SPANN 소개: SPANN은 단순하지만 효율적인 메모리-디스크 하이브리드 인덱싱 및 검색 시스템으로, 역방향 인덱스 방식을 따른다. 메모리에는 포스팅 리스트의 중심점을 저장하고, 큰 포스팅 리스트는 디스크에 저장한다.
- 성능 보장: 디스크 접근 효율성(저지연)과 높은 회수를 보장하기 위해 디스크 접근 횟수를 효과적으로 줄이고 고품질 포스팅 리스트를 검색한다.
- 인덱스 구축 단계: 계층적 균형 클러스터링 알고리즘을 채택하여 포스팅 리스트의 길이를 균형 있게 조정하고, 해당 클러스터 경계의 점들을 추가하여 포스팅 리스트를 보강한다.
- 검색 단계: 쿼리 인식 방식을 사용하여 불필요한 포스팅 리스트의 접근을 동적으로 가지치기한다.
- 실험 결과: SPANN은 최신 ANNS 솔루션 DiskANN보다 동일한 회수 품질($90%$)을 달성하는 데 있어 2배 빠르며, 메모리 비용도 동일하다. 32GB 메모리로 1밀리초 이내에 $90%$ recall@1 및 recall@10을 달성할 수 있다.
- 코드 제공: [링크](this https URL)
- 제출 내역: Jingdong Wang, 2021년 11월 5일 (127KB)
3arxiv.org링크 복사하기
AI 뉴스 요약은 뉴스의 내용을 AI가 요약(GPT-4 활용)한 것입니다. 따라서 틀린 내용을 포함할 수 있습니다. 뉴스의 자세한 내용을 확인하시려면 해당 뉴스 링크를 클릭해주세요.