Zilliz 벡터 검색 알고리즘, BigANN의 4개 트랙 모두 석권
BigANN 챌린지는 벡터 검색 분야의 절정에 해당하는 대회로, Approximate Nearest Neighbor(ANN) 문제의 실용적인 변형을 위한 인덱싱 데이터 구조와 검색 알고리즘의 발전을 촉진합니다. Zilliz는 이 중요한 대회의 핵심 주최자로서 전 세계 참가자들의 독창적인 솔루션을 지켜볼 수 있었던 것을 자랑스럽게 생각합니다. Milvus 벡터 데이터베이스의 제작자로서, 우리는 제시된 챌린지에 우리의 인사이트와 솔루션을 기여해야 한다고 느꼈습니다.
오늘, 저희는 기쁜 소식을 전하게 되어 매우 설렙니다: 저희 Zilliz 솔루션은 BigANN의 네 개 트랙 모두에서 다른 벤더들의 기존 제출물과 솔루션을 모두 능가했으며, 최대 2.5배라는 놀라운 성능 향상을 달성했습니다. 이 게시물에서는 BigANN 2023을 소개하고 Zilliz 솔루션과 그 성능 결과를 깊이 있게 살펴보겠습니다.
BigANN 2023
ANN benchmark는 벡터 검색 알고리즘을 평가하기 위한 업계 표준 도구이지만, 소규모 평가 데이터셋으로 인해 실제 운영 환경의 과제에 적용하는 데 한계가 있습니다. 이에 대응하여 BigANN이 탄생했으며, 대규모 데이터셋에서 알고리즘을 평가하고 발전시킴으로써 이러한 한계를 해결하는 대회이자 벤치마킹 이니셔티브 역할을 합니다.
올해 BigANN 2023은 더 큰 데이터셋(최대 1,000만 개의 벡터 포인트)과 더 복잡한 시나리오를 강조하며 더욱 중요한 과제를 도입합니다. 이 대회는 ANNS의 filtered, out-of-distribution, sparse, streaming 변형이라는 네 개 트랙으로 구성되어 실제 시나리오를 위한 현실적인 테스트 환경을 제공합니다.
Table1: BigANN 2023의 네 개 트랙
Filtered Track: 이 과제는 YFCC 100M 데이터셋을 사용하여 1,000만 장의 이미지를 선택합니다. 각 이미지에 대해 CLIP 임베딩을 추출하고, 다양한 어휘에서 가져온 이미지 설명, 카메라 모델, 촬영 연도, 국가와 같은 측면을 포함하는 태그를 생성해야 합니다. 여기서의 과제는 이미지 임베딩과 특정 태그로 구성된 100,000개의 쿼리를 데이터셋 내 해당 이미지 및 태그와 능숙하게 매칭하는 것입니다.
Out-Of-Distribution(OOD) Track: 이 트랙은 참가자들에게 Yandex Text-to-Image 10M 데이터셋을 제공하며, 크로스 모달 데이터의 통합을 강조합니다. 기본 데이터셋에는 Se-ResNext-101 모델을 사용해 생성된 Yandex 시각 검색 데이터베이스의 1,000만 개 이미지 임베딩이 포함됩니다. 반면, 쿼리 임베딩은 텍스트 검색을 기반으로 하며 다른 모델을 통해 처리됩니다. 여기서의 주요 과제는 이러한 서로 다른 데이터 모달리티 간의 간극을 효과적으로 메우는 것입니다.
Sparse Track: 이 트랙은 MSMARCO passage retrieval 데이터셋을 활용하며, SPLADE 모델을 사용해 희소 벡터로 인코딩된 880만 개 이상의 텍스트 passage로 구성된 방대한 컬렉션을 특징으로 합니다. 이 벡터들은 약 30,000차원을 가지지만 희소한 특성을 보입니다. 동시에 거의 7,000개의 쿼리도 동일한 모델을 통해 처리되지만, 길이가 간결하기 때문에 non-zero 요소가 더 적습니다. 이 트랙의 주요 과제는 쿼리 벡터와 데이터베이스 벡터 간의 최대 내적에 특히 중점을 두고, 주어진 쿼리에 대해 상위 결과를 정확하게 검색하는 것입니다.
Streaming Track: 이 트랙은 MS Turing 데이터셋의 일부를 기반으로 하며, 3,000만 개의 데이터 포인트로 구성됩니다. 참가자들은 데이터 삽입, 삭제, 검색 작업의 순서를 정교하게 설명하는 제공된 "runbook"을 따라야 합니다. 이러한 작업은 1시간 이내, 8GB DRAM 이하에서 완료되어야 합니다. 이 트랙은 이러한 작업을 처리하는 과정을 최적화하고 데이터셋의 간소화된 인덱스를 유지하는 데 중점을 둡니다.
이 대회에서 각 트랙은 알고리즘 순위를 매기기 위한 고유한 기준을 가지고 있습니다:
Filters, OOD, Sparse 트랙에서는 알고리즘이 최소 90% recall@10을 달성하는 경우 QPS를 기준으로 평가됩니다.
Streaming 트랙에서는 알고리즘이 recall@10에 따라 순위가 매겨지며, runbook을 1시간 이내에 완료해야 한다는 추가 요구 사항이 있습니다.
Zilliz 솔루션을 포함한 모든 성능 테스트는 Azure D8lds_v5(8 vCPU 및 16 GiB 메모리)에서 수행되었습니다.
Zilliz 솔루션 및 성능 결과
다음의 모든 결과는 BigANN 대회에서 제시한 평가 프레임워크와 지침을 준수하여 공정하고 포괄적인 비교를 보장합니다.
Filtered Track
우리의 Filter 트랙 솔루션(zilliz)을 공식 기준선(faiss), 우승자(parlayivf), Pinecone 솔루션과 비교한 것입니다. 90% recall에서 우리의 처리량은 약 82,000 QPS로, 3,200 QPS인 기준선의 약 25배, 32,000 QPS인 트랙 우승자의 2.5배이며, 68,000 QPS인 Pinecone 솔루션보다 훨씬 높습니다.
우리의 솔루션은 그래프 알고리즘과 태그 분류를 기반으로 합니다. 빌드 단계에서 각 잠재적 태그 조합의 카디널리티를 분석합니다. 많은 수의 벡터를 가진 조합에 대해서는 그래프를 구성하고, 그 외에는 역색인을 구축합니다. 검색 시에는 각 태그 조합의 고유한 특성을 기반으로 적절한 검색 방법을 선택합니다.
동시에, 관련 태그에 따라 쿼리를 분류합니다. 검색 중에는 각 쿼리를 해당 태그를 기반으로 검색합니다. 이 접근 방식은 두 가지 이점을 제공합니다. 1) 캐시 사용을 극대화하고, 2) 특히 전수 검색 중에 유용한 행렬 곱셈을 통한 가속을 가능하게 합니다.
데이터를 양자화하여 계산을 가속하고 SIMD를 사용해 거리 계산을 세밀하게 조정하여 높은 계산 효율성을 보장합니다.
OOD Track
우리의 OOD 트랙 솔루션을 공식 기준선(diskann), 트랙 우승자(pyanns), Pinecone 솔루션(pinecone-odd)과 비교한 것입니다. 90% recall에서 우리의 처리량은 약 33,000 QPS로, 약 4,000 QPS인 기준선의 8배이며, 약 23,000 QPS인 트랙 우승자와 26,000 QPS인 Pinecone 솔루션을 능가합니다.
참고: 이 트랙에는 숨겨진 쿼리 세트가 없기 때문에 공개 쿼리 세트를 사용하여 이 비교를 수행했습니다.
우리의 솔루션은 그래프 알고리즘과 고도로 최적화된 검색 프로세스의 시너지를 기반으로 합니다.
계산을 위해 검색과 정제 모두에 서로 다른 정밀도 수준의 양자화를 사용하고, 가속 계산을 위해 SIMD의 성능을 활용합니다. 검색 전에 쿼리 벡터를 클러스터링합니다. 그래프 검색 중에는 각 쿼리 클러스터에 서로 다른 초기 지점을 할당하여 각 클러스터 내에서 순차 검색을 위한 기반을 마련합니다.
이 클러스터링 전략에는 두 가지 장점이 있습니다. 1) 서로 다른 클러스터를 순차적으로 탐색함으로써 캐시 활용을 극대화하고, 2) 다양한 클러스터에 적응형 초기 지점을 할당함으로써 서로 다른 벡터 분포에서 발생하는 문제를 완화합니다.
또한 다중 레벨 bitset 데이터 구조도 구현합니다. 복잡한 이미지 검색 프로세스에서 방문한 지점을 표시하기 위한 데이터 구조가 필요합니다. 기존 방법은 bitset이나 hash table을 사용하는 경우가 많지만, 각각 단점이 있습니다. bitset은 종종 비효율적인 메모리 사용과 캐시 미스를 초래하는 반면, hash table은 불리한 상수로 인해 성능이 좋지 않습니다. 우리는 메모리의 다중 레벨 페이지 테이블에서 영감을 얻은 다중 레벨 bitset 데이터 구조를 혁신적으로 개발했습니다. 이 설계는 CPU 캐시 활용을 최적화하여 읽기 및 쓰기 성능을 크게 향상시킵니다.
Sparse Track
공식 베이스라인(linscan), 트랙 우승자(pyanns), Pinecone 솔루션(pinecone_smips)과 비교한 우리의 Sparse 트랙 솔루션(zilliz). 90% recall에서 우리의 throughput은 약 8,200 QPS로, 약 100 QPS인 베이스라인의 82배이며, 6,000 QPS의 트랙 우승자와 7,400 QPS의 Pinecone 솔루션을 모두 능가했습니다.
이 트랙에서 우리의 솔루션은 그래프 알고리즘과 희소 벡터 기반 최적화의 시너지를 기반으로 합니다. 각 희소 벡터는 튜플 목록(data[float32], index[int32])으로 표현됩니다. 우리는 그래프 검색 중 계산과 이후 refinement를 처리하기 위해 다중 정밀도 양자화를 도입했습니다. 또한 int16을 사용해 index를 표현함으로써 메모리 대역폭을 최적화합니다.
이 과제는 내적 검색을 극대화하는 것입니다. 내적 계산에서는 크기가 값의 중요도에 영향을 미칩니다. 크기가 클수록 더 큰 의미를 가지며, 작은 값은 덜 중요합니다. 이러한 통찰을 활용해, 우리는 그래프 검색 중 절댓값 크기가 더 작은 값을 버리는 pruning 전략을 구현했습니다. 그래프 검색 이후에는 전체 벡터를 사용해 refinement를 수행합니다. 실험 결과, recall을 크게 저하시키지 않고 query 벡터 데이터의 80% 이상을 pruning할 수 있음을 확인했습니다.
우리는 정렬된 리스트의 빠른 교집합 계산을 위해 SIMD 기술을 사용하여 계산을 신속하게 수행하며, 이를 통해 희소 벡터 내적에 대해 매우 효율적인 계산을 달성합니다.
Streaming 트랙
공식 베이스라인(diskann), 트랙 우승자(puck), Pinecone 솔루션(pinecone)과 비교한 우리의 Streaming 트랙 솔루션(zilliz). 우리의 알고리즘은 0.9982의 recall을 달성하여, 각각 0.986 및 0.9975의 recall을 기록한 트랙 우승자와 Pinecone 솔루션을 능가했습니다.
우리의 streaming 트랙 솔루션은 그래프 알고리즘과 SQ 양자화를 기반으로 합니다.
우리는 삭제 작업에 대해 lazy deletion 전략을 구현하여, 그래프 구조를 즉시 변경하지 않고 벡터를 삭제 대상으로 표시합니다. 지정된 수의 삭제 작업이 누적될 때까지 그래프는 재구성되지 않습니다.
우리는 그래프 검색과 refinement 모두를 위해 다양한 정밀도로 벡터를 양자화합니다. 먼저 그래프 검색에는 더 낮은 정밀도의 벡터를 사용합니다. 하지만 우리의 lazy deletion 전략으로 인해 삭제된 벡터가 검색 결과에 나타날 수 있습니다. 따라서 이러한 삭제된 벡터를 제거하기 위해 post-filtering 전략을 활용합니다. 마지막으로 더 높은 정밀도로 양자화된 벡터를 사용해 결과를 refine합니다.
Note: 우리의 솔루션은 오픈소스로 공개되어 있지는 않지만, 폭넓은 접근성과 재현성을 위해 방법론을 설명하고 BigANN's GitHub repo에 바이너리를 공개했습니다.
BigANN 알고리즘은 Zilliz 제품에 통합될 예정입니다
AI가 발전함에 따라 벡터 검색은 복잡한 프로덕션 시나리오를 지원하는 데 필수적인 요소가 되었습니다. BigANN이 여러 시나리오를 포괄한다는 점은 상당한 실용적 가치를 더합니다. 우리는 이 BigANN 대회에 적극적으로 참여하고 이러한 도전적인 알고리즘 문제를 해결하는 것을 즐기게 되어 매우 기쁩니다. 이 과정에서 얻은 인사이트를 우리 제품에 통합하여, 더 광범위한 문제에 그 영향력을 확장할 것입니다.
함께하세요!
Zilliz에서는 벡터 검색을 사용해 실제 문제를 해결하는 세계 최고의 벡터 데이터베이스를 구축하는 데 전념하고 있습니다. 또한 BigANN과 그 너머에서 영감을 받은 도전적인 사용 사례를 탐구하는 여정을 계속하고 있습니다. 벡터 검색, 데이터베이스 시스템 또는 AI 기술에 관심 있는 같은 뜻을 가진 분들을 이 여정에 초대합니다. 관심이 있으시다면 연락해 주세요! 더 자세한 정보와 지원을 위해 career 페이지에서 기회를 확인해 보세요.
이 글은 Li Liu와 Zihao Wang이 작성했습니다.
계속 읽기
Introducing Loon: A New Storage Engine for Vector Data That Never Stops Changing
Loon is a new storage engine for Milvus 3.0 and Zilliz Vector Lakebase, built to manage evolving vector datasets with ColumnGroups, row ID alignment, and Manifests.
How to Build an Enterprise-Ready RAG Pipeline on AWS with Bedrock, Zilliz Cloud, and LangChain
Build production-ready enterprise RAG with AWS Bedrock, Nova models, Zilliz Cloud, and LangChain. Complete tutorial with deployable code.
Balancing Precision and Performance: How Zilliz Cloud's New Parameters Help You Optimize Vector Search
Optimize vector search with Zilliz Cloud’s level and recall features to tune accuracy, balance performance, and power AI applications.