ANN 벤치마크 종합 가이드: 근사 최근접 이웃 검색(ANNS) 성능 평가
ANN 벤치마크 종합 가이드: 근사 최근접 이웃 검색(ANNS) 성능 평가
수십억 개의 이미지, 텍스트 문서 또는 기타 비정형 데이터가 포함된 데이터베이스에서 가장 유사한 항목을 빠르게 찾아야 하는 검색 엔진을 구축하고 있다고 상상해 보세요. 검색 알고리즘이 정확한 결과를 반환할 뿐만 아니라 번개처럼 빠르게 수행되도록 하려면 어떻게 해야 할까요? 바로 여기서 근사 최근접 이웃(ANN) 검색이 등장합니다. ANN 검색은 추천 시스템부터 대규모 이미지 검색에 이르기까지 많은 실제 애플리케이션에서 매우 중요합니다.
시장에 수많은 ANN 검색 솔루션이 나와 있는 상황에서, 특히 대규모 환경에서 서로 다른 ANN 알고리즘의 효과를 어떻게 평가할 수 있을까요? ANN 벤치마크가 등장합니다. ANN 벤치마크는 대규모 데이터셋에서 ANN 검색 방법의 성능을 테스트하는 표준으로 자리 잡았습니다.
이 블로그에서는 ANN 벤치마크가 무엇인지, 왜 중요한지, 그리고 개발자와 알고리즘 엔지니어가 작업에 적합한 벡터 검색 솔루션을 선택하는 데 어떻게 도움이 되는지 살펴보겠습니다. 또한 오늘날 사용되는 가장 인기 있는 벤치마크 몇 가지와 그것들이 벡터 검색에서 필수적인 이유도 알아보겠습니다.
ANN 검색이란 무엇이며 어떻게 작동하나요?
벤치마크를 자세히 살펴보기 전에, 근사 최근접 이웃(ANN) 검색, 즉 ANNS와 그것이 어떻게 작동하는지 이해하는 것이 중요합니다. ANN 검색은 Zilliz Cloud와 같은 벡터 데이터베이스에서 흔히 발견되는 대규모 데이터셋에서 효율적인 의미적 유사도 검색을 가능하게 하는 머신러닝(ML)의 강력한 기법입니다. 데이터셋에서 주어진 쿼리 항목과 가장 가까운 항목을 빠르게 찾을 수 있습니다. 100% 정확도를 보장하는 정확 검색 방법과 달리, ANNS는 속도와 확장성의 상당한 향상을 위해 소량의 정확도를 절충합니다.
ANN 검색의 작동 방식:
데이터 표현: 데이터셋의 각 항목은 다차원 공간의 벡터로 표현됩니다. 벡터는 일반적으로 OpenAI 텍스트 임베딩 모델, Cohere 다국어 모델, OpenAI 멀티모달 모델과 같은 임베딩 모델에 의해 인코딩됩니다. 예를 들어, 이미지는 128차원 공간에서 색상이나 형태와 같은 특징의 벡터로 표현될 수 있습니다.
쿼리 처리: 쿼리가 이루어지면, ANN 검색 알고리즘은 프로세스 속도를 높이기 위해 근사를 사용하여 쿼리 벡터와 가까운 벡터를 데이터셋에서 검색합니다.
결과 순위 지정: 알고리즘은 고차원 공간에서 쿼리로부터의 거리를 기준으로 최근접 이웃의 순위를 매기며, 종종 유클리드 거리나 코사인 유사도와 같은 지표를 사용합니다. 벡터가 더 가깝게 위치할수록 더 유사하고 관련성이 높습니다.
효율성: ANN 검색의 핵심 장점은 정확 검색에 걸리는 시간의 일부만으로 결과를 제공할 수 있다는 점이며, 이는 대규모 데이터셋에 이상적입니다.
ANNS 방법은 최근접 이웃을 빠르게 근사하기 위해 다양한 전략을 사용합니다:
트리 기반 방법: KD-Trees 및 Ball Trees와 같은 기법은 검색 과정을 단순화하기 위해 데이터를 계층적으로 구성합니다. 낮은 차원에서는 효과적이지만, 차원이 증가할수록 성능이 저하됩니다.
해싱 방법: Locality-sensitive hashing (LSH)는 유사한 데이터 포인트를 동일한 해시 버킷으로 그룹화하여 검색 중 필요한 비교 횟수를 줄입니다.
그래프 기반 방법: Navigable Small World (NSW) 그래프 및 Hierarchical Navigable Small World (HNSW) 그래프와 같은 알고리즘은 데이터 포인트의 네트워크를 생성하여 이웃 조회를 신속하게 수행합니다.
양자화 방법: Product Quantization (PQ)와 같은 기법은 데이터를 더 관리하기 쉬운 형태로 압축하여 검색 효율성을 향상시킵니다.
이러한 방법을 활용함으로써 ANNS 알고리즘은 검색 정확도와 성능 사이의 균형을 맞출 수 있어 대규모 데이터셋에 적합합니다.
ANN 검색 vs. KNN 검색
정확한 K-nearest neighbor 검색(KNN)과 Approximate Nearest Neighbor Search (ANNS)는 벡터 검색에 사용되는 두 가지 기본 접근 방식으로, 각각 고유한 장점과 트레이드오프가 있습니다.
정확한 KNN은 쿼리 포인트와 데이터셋의 모든 데이터 포인트 간 거리를 평가하여 식별된 이웃이 가능한 한 가장 가까운지 보장함으로써 정밀한 결과를 제공합니다. 그러나 이 방법은 브루트포스 방식의 특성 때문에 계산 집약적이고 느릴 수 있으며, 특히 대규모 데이터셋이나 고차원 공간을 다룰 때 그렇습니다. 따라서 정확한 KNN은 더 작은 데이터셋이나 정밀도가 가장 중요하고 계산 리소스가 상대적으로 덜 중요한 시나리오에 적합합니다.
반면, ANNS는 더 빠른 성능을 위해 어느 정도의 정확도를 희생함으로써 대규모 데이터를 처리하기 위한 실용적인 솔루션을 제공합니다. ANNS는 트리 기반 구조, 해싱 방법 및 그래프 기반 접근 방식과 같은 다양한 알고리즘과 기법을 사용하여 최근접 이웃을 효율적으로 근사합니다. 이 접근 방식은 계산 비용을 크게 줄이고 방대한 데이터셋에서도 잘 확장되므로, 속도가 중요한 검색 엔진 및 추천 시스템과 같은 실시간 애플리케이션에 이상적입니다. ANNS가 항상 정확히 가장 가까운 이웃을 제공하지는 않을 수 있지만, 거의 정확한 결과를 빠르게 제공하는 능력 덕분에 현대적인 데이터 검색 및 분석 작업에서 가치 있는 도구가 됩니다.
자세한 내용은 ANNS 용어집 페이지를 참조하세요.
ANN Benchmark란 무엇인가요?
ANN Benchmark는 다양한 ANNS 알고리즘의 성능을 측정하고 비교하도록 설계된 포괄적인 평가 도구입니다. ann-benchmarks.com에서 호스팅되며, 다음을 포함하여 ANNS 방법의 다양한 측면을 평가하기 위한 표준화된 테스트와 지표를 제공합니다.
검색 속도: 알고리즘이 최근접 이웃을 얼마나 빠르게 찾을 수 있는지.
정확도: 알고리즘의 결과가 실제 최근접 이웃에 얼마나 근접하는지의 정도.
확장성: 데이터셋 크기나 차원이 증가할 때 알고리즘이 얼마나 잘 수행되는지.
이 벤치마크는 다양한 데이터셋과 평가 기준을 제공하여, 개발자가 공정한 조건에서 여러 상황별로 다양한 알고리즘의 효과를 가늠할 수 있게 합니다.
ANN 벤치마크의 핵심 지표:
재현율: 알고리즘이 성공적으로 검색한 실제 최근접 이웃의 비율입니다. 높은 재현율은 더 나은 정확도를 나타냅니다.
검색 시간: 알고리즘이 결과를 반환하는 데 걸리는 시간입니다. 더 빠른 검색 시간은 실시간 응답이 필요한 애플리케이션에 매우 중요합니다.
메모리 사용량: 알고리즘이 데이터셋을 저장하고 검색하는 데 필요한 메모리의 양입니다. 효율적인 메모리 사용은 확장성에 중요합니다.
확장성: 데이터셋 크기가 증가함에 따라 성능을 유지하는 알고리즘의 능력입니다. 확장성은 데이터셋이 빠르게 증가할 수 있는 실제 애플리케이션에서 중요한 요소입니다.
ANN Benchmarks에서 사용되는 주요 데이터셋
ANN Benchmark는 알고리즘을 테스트하기 위해 다양한 데이터셋을 사용합니다. 이러한 데이터셋은 이미지 특징, 텍스트 임베딩, 합성 데이터와 같은 다양한 도메인을 포괄합니다. 벤치마크에서 사용되는 주요 데이터셋은 다음과 같습니다:
| 데이터셋 | 차원 | 학습 크기 | 테스트 크기 | 이웃 | 거리 | 다운로드 |
|---|---|---|---|---|---|---|
| DEEP1B | 96 | 9,990,000 | 10,000 | 100 | 각도 | HDF5 (3.6GB) |
| Fashion-MNIST | 784 | 60,000 | 10,000 | 100 | 유클리드 | HDF5 (217MB) |
| GIST | 960 | 1,000,000 | 1,000 | 100 | 유클리드 | HDF5 (3.6GB) |
| GloVe | 25 | 1,183,514 | 10,000 | 100 | 각도 | HDF5 (121MB) |
| GloVe | 50 | 1,183,514 | 10,000 | 100 | 각도 | HDF5 (235MB) |
| GloVe | 100 | 1,183,514 | 10,000 | 100 | 각도 | HDF5 (463MB) |
| GloVe | 200 | 1,183,514 | 10,000 | 100 | 각도 | HDF5 (918MB) |
| Kosarak | 27,983 | 74,962 | 500 | 100 | 자카드 | HDF5 (33MB) |
| MNIST | 784 | 60,000 | 10,000 | 100 | 유클리드 | HDF5 (217MB) |
| MovieLens-10M | 65,134 | 69,363 | 500 | 100 | 자카드 | HDF5 (63MB) |
| NYTimes | 256 | 290,000 | 10,000 | 100 | 각도 | HDF5 (301MB) |
| SIFT | 128 | 1,000,000 | 10,000 | 100 | 유클리드 | HDF5 (501MB) |
| Last.fm | 65 | 292,385 | 50,000 | 100 | 각도 | HDF5 (135MB) |
테스트된 ANN 알고리즘 또는 벡터 검색 엔진
ANN Benchmarks는 Annoy, Faiss, Knowhere(Milvus의 검색 엔진), Glass(Zilliz Cloud의 레거시 검색 엔진)를 포함한 광범위한 ANN 알고리즘 및 벡터 검색 엔진을 평가해 왔습니다. 테스트된 알고리즘의 수는 계속 증가하고 있습니다. 아래는 2024년 9월 기준으로 테스트된 알고리즘 및 검색 엔진 목록입니다.
scikit-learn: LSHForest, KDTree, BallTree
NMSLIB (Non-Metric Space Library) : SWGraph, HNSW, BallTree, MPLSH
NGT : ONNG, PANNG, QG
Elasticsearch : HNSW
DiskANN : Vamana, Vamana-PQ
scipy: cKDTree
참고: Zilliz Cloud는 Cardinal이라는 새로운 검색 엔진을 출시했으며, 이는 기존 Glass 엔진보다 세 배 높은 성능을 제공하고 Milvus보다 최대 열 배 높은 검색 처리량(QPS)을 제공합니다. 그러나 시간 제약 및 기타 요인으로 인해 Cardinal의 성능은 ANN 벤치마크 결과에 포함되지 않았습니다. 다음 섹션에서는 VectorDBBench를 사용하여 해당 성능을 살펴볼 수 있습니다.
벤치마크 결과
아래 그래프는 GIST1M 데이터셋(960차원의 벡터 100만 개)을 기반으로 다양한 알고리즘의 재현율/초당 쿼리 수 테스트 결과를 보여줍니다. x축에는 재현율을, y축에는 QPS를 표시하여 각 알고리즘이 서로 다른 검색 정확도 수준에서 보이는 성능을 나타냅니다.
그림 1: GIST1M 데이터셋에 대한 ANN 벤치마크 결과
그림 1: GIST1M 데이터셋에 대한 ANN 벤치마크 결과
위 그래프에 표시된 결과에 따르면, 960차원의 벡터 1,000,000개를 처리할 때 Knowhere(Milvus의 검색 엔진), Glass(Zilliz Cloud의 레거시 검색 엔진), HNSW 라이브러리가 상위 3개의 최고 결과를 달성했습니다.
더 많은 벤치마킹 결과는 ANN-Benchmark의 웹사이트를 참조하세요.
VectorDBBench: 벡터 데이터베이스를 위한 오픈 소스 벤치마킹 도구
벡터 검색, 또는 벡터 유사도 검색은 데이터셋 내에서 유사한 벡터를 찾는 과정을 가리키는 더 넓은 개념입니다. ANNS는 벡터 검색을 구동하는 알고리즘 집합을 나타냅니다. 벡터 데이터베이스는 효율적인 벡터 유사도 검색을 위해 특화되어 구축된 솔루션입니다.
ANN-Benchmark는 다양한 벡터 검색 알고리즘을 선택하고 비교하는 데 매우 유용하지만, 벡터 데이터베이스에 대한 포괄적인 개요를 제공하지는 않습니다. 리소스 소비, 데이터 로딩 용량, 시스템 안정성과 같은 요소도 고려해야 합니다. 또한 ANN Benchmark는 필터링된 벡터 검색과 같은 많은 일반적인 시나리오를 놓칩니다.
이러한 과제를 해결하기 위해 Zilliz 개발자들은 Milvus and Weaviate와 같은 오픈 소스 벡터 데이터베이스 및 Zilliz Cloud and Pinecone과 같은 완전 관리형 서비스를 위해 설계된 오픈 소스 벤치마킹 도구인 VectorDBBench를 제안했습니다. 많은 완전 관리형 벡터 검색 서비스는 사용자가 튜닝할 수 있도록 매개변수를 공개하지 않기 때문에, VectorDBBench는 QPS와 재현율을 별도로 표시합니다.
아래 차트는 768차원의 벡터 1,000,000개를 처리할 때 다양한 주류 벡터 데이터베이스의 QPS와 재현율에 대한 테스트 결과를 보여줍니다.
그림 2: QPS 벤치마크 결과
그림 3: 재현율 벤치마크 결과
위 차트의 결과를 바탕으로, Milvus와 Zilliz 같은 특화된 벡터 데이터베이스는 QPS와 재현율 모두에서 뛰어난 성능을 보였습니다. 이러한 결과는 특화된 벡터 데이터베이스가 방대한 양의 데이터를 빠르게 처리하고 더 정확한 결과를 검색할 수 있음을 나타냅니다. 반면, 기존 데이터베이스 기반의 벡터 검색 애드온은 더 낮은 성능을 보였습니다.
벤치마크 결과를 재현하거나 자체 데이터셋에서 성능 결과를 얻으려면 GitHub repository에서 VectorDBBench를 다운로드하세요.
VectorDBBench 리더보드
VectorDBBench는 테스트 결과의 표시를 간소화하고 철저한 성능 분석 보고서를 제공하도록 설계된 전용 리더보드 페이지도 제공합니다. 이 리더보드를 통해 Queries Per Second (QPS), Query Price ($) 지표, 지연 시간과 같은 핵심 지표를 선택하여 종합적인 성능 평가를 수행할 수 있습니다.
vectordbbench 리더보드 스크린샷
그림 4: VectorDBBench 리더보드 스크린샷
ANN Benchmarks vs. VectorDBBench
ANN Benchmarks는 벡터 인덱스 알고리즘을 평가하여 다양한 벡터 검색 라이브러리를 선택하고 비교하는 데 도움을 줍니다. 그러나 복잡하고 성숙한 벡터 데이터베이스를 평가하는 데에는 적합하지 않으며, 필터링된 벡터 검색과 같은 상황을 간과합니다.
Zilliz의 엔지니어들은 포괄적인 벡터 데이터베이스 평가에 맞춰 VectorDB Bench를 만들었습니다. 이는 리소스 소비, 데이터 로딩 용량, 시스템 안정성과 같은 필수 요소를 고려합니다. 테스트 클라이언트와 벡터 데이터베이스를 분리하고 독립적인 배포를 보장함으로써, VectorDB Bench는 실제 프로덕션 환경을 밀접하게 반영하는 테스트를 가능하게 합니다.
성능 평가에 영향을 미치는 요인
벡터 데이터베이스 또는 ANN 알고리즘의 성능에는 데이터셋, 네트워크 조건, 데이터베이스 구성 등 여러 요인이 영향을 미칩니다.
네트워크
네트워크 조건은 매우 중요합니다. 지연 시간은 쿼리 응답을 늦출 수 있으며, 제한된 대역폭은 데이터 전송 속도에 영향을 미칩니다. 네트워크 안정성도 중요하며, 변동이 발생하면 성능이 일관되지 않을 수 있습니다.
데이터셋
데이터셋 크기는 메모리 및 디스크 사용량에 영향을 미칩니다. 더 큰 데이터셋은 더 많은 리소스를 필요로 합니다. 벡터 차원 수는 연산 복잡도와 쿼리 시간에 영향을 미칩니다. 데이터 분포와 인덱싱 구조(예: 계층형, 플랫)도 검색 효율성과 정확도에 영향을 미칩니다.
데이터베이스 구성
인덱스 매개변수(예: 트리 수)와 검색 설정(예: 최근접 이웃)은 검색 효율성과 속도에 직접적인 영향을 미칩니다. 캐싱은 자주 액세스되는 데이터의 응답 시간을 개선할 수 있습니다.
환경 요인
운영 체제와 백그라운드 프로세스는 리소스 가용성과 시스템 응답성에 영향을 미쳐 전체 성능에 영향을 줄 수 있습니다.
이러한 요인을 고려하면 벡터 데이터베이스의 성능을 이해하고 최적화하는 데 도움이 됩니다.