DiskANN: 10억 규모 데이터셋에서 높은 재현율과 높은 QPS를 제공하는 디스크 기반 ANNS 솔루션
“DiskANN: 단일 노드에서의 빠르고 정확한 10억 포인트 최근접 이웃 검색”은 2019년 NeurIPS에 발표된 논문이다. 이 논문은 64GB RAM과 충분히 큰 SSD만을 갖춘 단일 머신을 사용하여 10억 규모 데이터셋에서 인덱스 구축과 검색을 수행하는 최신 방법을 소개한다. 또한 대규모 데이터셋에서 ANNS(Approximate Nearest Neighbor Search)의 세 가지 요구사항, 즉 높은 재현율, 낮은 지연 시간, 높은 밀도(단일 머신의 노드 수)를 충족한다. 이 방법은 64GB RAM과 16코어 CPU를 갖춘 단일 머신을 사용하여 10억 규모 데이터셋 SIFT-1B에 그래프 기반 인덱스를 구축하며, 95% 이상의 recall@1에서 5000 QPS(queries per second)를 달성하고 평균 지연 시간은 3ms 미만이다.
저자
Suhas Jayaram Subramanya: Microsoft India Research Institute의 전 직원, CMU 박사과정 학생. 주요 연구 관심사는 대규모 데이터를 위한 고성능 컴퓨팅 및 머신러닝 알고리즘이다.
Devvrit: The University of Texas at Austin의 대학원 연구 조교. 그의 연구 관심사는 이론 컴퓨터 과학, 머신러닝, 딥러닝이다.
Rohan Kadekodi: University of Texas의 박사과정 학생. 그의 연구 방향은 시스템과 스토리지이며, 주로 영구 저장장치, 파일 시스템, kV 스토리지를 포함한다.
Ravishankar Krishaswamy: Microsoft Indian research institute의 수석 연구원. CMU 박사. 연구 방향은 그래프와 클러스터링 기반의 근사 알고리즘이다.
Harsha Vardhan Simhadri: Microsoft Indian research institute의 수석 연구원. CMU 박사. 과거에는 병렬 알고리즘과 런타임 시스템을 연구했다. 현재 그의 주요 업무는 새로운 알고리즘을 개발하고 프로그래밍 모델을 작성하는 것이다.
동기
대부분의 주류 ANNS 알고리즘은 인덱스 구축 성능, 검색 성능, 재현율 사이에서 어느 정도 절충을 한다. HNSW와 NSG 같은 그래프 기반 알고리즘은 현재 검색 성능과 재현율 측면에서 최신 방법이다. 메모리 상주 그래프 기반 인덱싱 방법은 너무 많은 메모리를 차지하기 때문에, 제한된 메모리 자원을 가진 단일 머신을 사용하여 대규모 데이터셋을 인덱싱하고 검색하는 것은 상대적으로 어렵다.
많은 애플리케이션은 10억 규모 데이터셋에서 유클리드 거리 기반 ANNS의 빠른 응답을 필요로 한다. 아래는 두 가지 주요 해결책이다:
역색인 + 양자화: 데이터셋을 M개의 파티션으로 클러스터링하고 PQ(Product Quantization)와 같은 양자화 기법을 사용하여 데이터셋을 압축한다. 이 해결책은 데이터 압축으로 인한 정밀도 손실 때문에 낮은 재현율을 낸다. topk를 증가시키면 재현율 향상에 도움이 되지만 QPS는 그에 따라 감소한다.
분할 및 인덱싱: 데이터셋을 여러 개의 서로소 샤드로 나누고 각 샤드에 대해 인메모리 인덱스를 구축한다. 쿼리 요청이 오면 각 샤드의 인덱스에서 검색이 수행되고 결과는 병합된 후 반환된다. 이 해결책은 데이터셋 규모의 과도한 확장을 초래하며, 단일 머신의 메모리 자원 제한 때문에 더 많은 머신이 필요하게 되어 낮은 QPS로 이어진다.
위에서 언급한 두 해결책은 모두 단일 머신의 메모리 제한에 의해 제약을 받는다. 이 논문은 이 문제를 해결하기 위해 SSD 상주 인덱싱 메커니즘의 설계를 제안한다. SSD 상주 인덱싱의 과제는 랜덤 디스크 접근 횟수와 디스크 접근 요청 수를 줄이는 것이다.
기여
이 논문은 대규모 데이터셋에서의 검색을 효과적으로 지원할 수 있는 DiskANN이라는 SSD 상주 ANNS 기법을 제시한다. 이 기법은 이 논문에서 제시된 그래프 기반 알고리즘인 Vamana를 기반으로 한다. 이 논문의 기여는 다음을 포함한다:
DiskANN은 64GB RAM을 갖춘 단일 머신에서 100차원 이상의 10억 규모 데이터셋을 인덱싱하고 검색할 수 있으며, 5밀리초 미만의 지연 시간으로 95% 이상의 recall@1을 제공한다.
NSG와 HNSW보다 더 작은 검색 반경을 가진 Vamana라는 새로운 그래프 기반 알고리즘이 디스크 접근 횟수를 최소화하기 위해 제안되었습니다.
Vamana는 메모리에서 동작할 수 있으며, 그 성능은 NSG와 HNSW보다 느리지 않습니다.
대규모 데이터셋의 중첩 파티션 위에 구축된 더 작은 Vamana 인덱스들은 연결성을 잃지 않고 하나의 그래프로 병합될 수 있습니다.
Vamana는 PQ와 같은 양자화 기법과 결합될 수 있습니다. 그래프 구조와 원본 데이터는 디스크에 저장되는 반면, 압축 데이터는 메모리에 유지됩니다.
Vamana
이 알고리즘은 NSG[2][4]의 아이디어와 유사합니다(NSG를 이해하지 못하는 분들은 참고문헌 [2]를 참조하시고, 논문을 읽고 싶지 않다면 참고문헌 [4]를 참조하시면 됩니다). 이들의 주요 차이는 가지치기 전략에 있습니다. 정확히 말하면, NSG의 가지치기 전략에 스위치 alpha가 추가되었습니다. NSG 가지치기 전략의 핵심 아이디어는 대상 점의 이웃 선택이 가능한 한 다양해야 한다는 것입니다. 새로운 이웃이 대상 점보다 대상 점의 한 이웃에 더 가깝다면, 이 점을 이웃 점 집합에 추가할 필요가 없습니다. 다시 말해, 대상 점의 각 이웃에 대해 주변 반경 dist (대상 점, 이웃 점) 내에 다른 이웃 점이 존재할 수 없습니다. 이 가지치기 전략은 그래프의 out-degree를 효과적으로 제어하며, 비교적 급진적입니다. 이는 인덱스의 메모리 사용량을 줄이고 검색 속도를 향상시키지만, 검색 정확도도 낮춥니다. Vamana의 가지치기 전략은 매개변수 alpha를 통해 가지치기의 규모를 자유롭게 제어하는 것입니다. 동작 원리는 가지치기 조건에서 dist (이웃 점, 후보 점)에 매개변수 alpha(1 이상)를 곱하는 것입니다. dist (대상 점, 특정 후보 점)가 확대된 기준 거리보다 클 때에만 가지치기 전략이 적용되어, 대상 점의 이웃들 사이의 상호 배제에 대한 허용 범위를 늘립니다.
Vamana의 인덱싱 과정은 비교적 간단합니다:
랜덤 그래프를 초기화합니다;
시작점을 계산합니다. 이는 NSG의 내비게이션 점과 유사합니다. 먼저 전역 중심점을 찾은 다음, 전역 중심점에 가장 가까운 점을 내비게이션 점으로 찾습니다. Vamana와 NSG의 차이는 NSG의 입력이 이미 최근접 이웃 그래프이므로, 사용자는 초기 이웃 그래프에서 중심점에 대해 바로 근사 최근접 이웃 검색을 간단히 수행할 수 있다는 점입니다. 그러나 Vamana는 랜덤 최근접 이웃 그래프를 초기화하므로, 사용자는 랜덤 그래프에서 직접 근사 검색을 수행할 수 없습니다. 이후 반복의 시작점으로 사용할 내비게이션 점을 얻기 위해 전역 비교를 수행해야 합니다. 이 점의 목적은 평균 검색 반경을 최소화하는 것입니다;
초기화된 랜덤 이웃 그래프와 2단계에서 결정된 검색 시작점을 기반으로 각 점에 대해 Approximate Nearest Neighbor Search를 수행하고, 검색 경로상의 모든 점을 후보 이웃 집합으로 만들며, alpha = 1을 사용하여 엣지 가지치기 전략을 실행합니다. NSG와 유사하게, 내비게이션 점에서 시작하는 검색 경로상의 점 집합을 후보 이웃 집합으로 선택하면 일부 긴 엣지가 증가하고 검색 반경이 효과적으로 줄어듭니다.
alpha > 1(논문에서는 1.2를 권장)을 조정하고 3단계를 반복합니다. 3단계는 랜덤 최근접 이웃 그래프를 기반으로 하므로, 첫 번째 반복 이후 그래프의 품질은 낮습니다. 따라서 그래프 품질을 향상시키기 위해 또 다른 반복이 필요하며, 이는 재현율에 매우 중요합니다.
이 논문은 세 가지 그래프 인덱스, 즉 Vamana, NSG, HNSW를 비교합니다. 인덱싱 및 쿼리 성능 측면에서 Vamana와 NSG는 비교적 비슷하며, 둘 다 HNSW보다 약간 우수합니다. 데이터는 아래 Experiment 섹션을 참조하십시오.
Figure 1.
Vamana 인덱스의 구축 과정을 시각화하기 위해, 논문에서는 200개의 2차원 포인트를 사용하여 두 번의 반복 라운드를 시뮬레이션한 그래프를 제공합니다. 첫 번째 행은 alpha = 1을 사용하여 엣지를 가지치기합니다. 가지치기 전략이 비교적 과감하며, 많은 수의 엣지가 가지치기되는 것을 볼 수 있습니다. alpha 값을 증가시키고 가지치기 조건을 완화한 후에는 많은 엣지가 명확하게 다시 추가됩니다. 최종 그래프에서는 꽤 많은 긴 엣지가 추가됩니다. 이는 검색 반경을 효과적으로 줄일 수 있습니다.
DiskANN
메모리가 64GB뿐인 개인용 컴퓨터는 10억 개의 원시 데이터조차 담을 수 없으며, 그 위에 구축된 인덱스는 말할 것도 없습니다. 앞으로 두 가지 과제가 있습니다: 1. 제한된 메모리 리소스로 이러한 대규모 데이터 세트를 어떻게 인덱싱할 것인가? 2. 원본 데이터를 메모리에 로드할 수 없다면 검색 시 거리를 어떻게 계산할 것인가?
논문은 다음과 같은 해결책을 제안했습니다:
첫 번째 과제에 대해: 먼저 k-means를 사용하여 데이터를 k개의 클러스터로 나눈 다음, 각 포인트를 가장 가까운 i개의 클러스터에 할당합니다. 일반적으로 i의 값은 2면 충분합니다. 각 클러스터에 대해 메모리 기반 Vamana 인덱스를 구축하고, 마지막으로 k개의 Vamana 인덱스를 하나로 병합합니다.
두 번째 과제에 대해: 원본 벡터에 인덱스를 구축하고 압축된 벡터를 쿼리합니다. 원본 벡터에 인덱스를 구축하면 그래프의 품질이 보장되는 반면, 압축된 벡터는 대략적인 검색을 위해 메모리에 로드될 수 있습니다. 압축된 벡터로 검색하면 정확도 손실이 발생할 수 있지만, 그래프의 품질이 충분히 높다면 전반적인 방향은 올바를 것입니다. 최종 거리 결과는 원본 벡터를 사용하여 계산됩니다.
DiskANN의 인덱스 레이아웃은 일반적인 그래프 인덱스의 레이아웃과 유사합니다. 각 포인트의 이웃 집합과 원본 벡터 데이터가 함께 저장됩니다. 이는 데이터의 지역성을 더 잘 활용하게 합니다.
앞서 언급했듯이, 인덱스 데이터가 SSD에 저장되는 경우 낮은 검색 지연을 보장하기 위해 디스크 접근 횟수와 디스크 읽기 및 쓰기 요청을 최대한 줄여야 합니다. 따라서 DiskANN은 두 가지 최적화 전략을 제안합니다:
Cache hotspot: 시작점으로부터 C번의 점프 이내에 있는 모든 포인트를 메모리에 캐시합니다. C의 값은 3에서 4 이내로 설정하는 것이 좋습니다.
Beam search: 간단히 말해, 이웃 정보를 미리 로드하는 것입니다. 포인트 p를 검색할 때, p의 이웃 포인트가 메모리에 없으면 디스크에서 로드해야 합니다. 소량의 SSD 랜덤 접근 작업은 SSD 단일 섹터 접근 작업과 거의 같은 시간이 걸리므로, 접근되지 않은 W개의 포인트의 이웃 정보를 한 번에 로드할 수 있습니다. W는 너무 크거나 작게 설정해서는 안 됩니다. W가 크면 컴퓨팅 리소스와 SSD 대역폭을 낭비하고, 작으면 검색 지연이 증가합니다.
Experiment
실험은 세 그룹으로 구성됩니다:
메모리 기반 인덱스 간 비교: Vamana VS. NSG VS. HNSW
데이터 세트: SIFT1M (128차원), GIST1M (960차원), DEEP1M (96차원) 및 DEEP1B에서 무작위로 샘플링한 1M 데이터 세트.
인덱스 매개변수(모든 데이터 세트는 동일한 매개변수 세트를 사용):
HNSW：M = 128, efc = 512.
Vamana: R = 70, L = 75, alpha = 1.2.
NSG: R = 60, L = 70, C= 500.
검색 매개변수는 논문에 제공되어 있지 않으며, 인덱싱 매개변수와 일치할 수 있습니다. 매개변수 선택의 경우, 기사에서 언급된 NSG의 매개변수는 NSG의 GitHub 저장소에 나열된 매개변수를 기반으로 더 나은 성능을 보이는 그룹을 선택한 것입니다. Vamana와 NSG는 비교적 가깝기 때문에 매개변수도 비슷하게 설정되었습니다. 그러나 HNSW 매개변수 선택 이유는 제시되어 있지 않습니다. 우리는 HNSW의 매개변수 M이 비교적 크게 설정되었다고 봅니다. 그래프 기반 인덱스들의 out-degree가 같은 수준으로 설정되지 않았다면, 그들 간의 비교 설득력이 떨어질 수 있습니다.
위의 인덱싱 매개변수에서 Vamana, HNSW, NSG의 인덱싱 시간은 각각 129초, 219초, 480초입니다. NSG 인덱싱 시간에는 EFANN [3]을 사용하여 초기 이웃 그래프를 구성하는 시간이 포함됩니다.
Recall-QPS 곡선:
Figure 2.
Figure 3에서 볼 수 있듯이 Vamana는 세 데이터 세트에서 NSG와 유사하고 HNSW보다 약간 더 나은 뛰어난 성능을 보입니다.
검색 반경 비교:
Figure 2.c에서 볼 수 있듯이 Vamana는 동일한 재현율에서 NSG 및 HNSW와 비교했을 때 평균 검색 경로가 가장 짧습니다.
한 번에 구축한 인덱스와 대규모 병합 인덱스 간 비교
데이터 세트: SIFT1B
한 번에 구축한 인덱스 매개변수: L = 50, R = 128, alpha = 1.2. 1800G DDR3 머신에서 2일 동안 실행한 후, 피크 메모리는 약 1100 G이고 평균 out-degree는 113.9입니다.
병합 기반 인덱싱 절차:
kmeans를 사용하여 데이터 세트에서 40개의 클러스터를 학습합니다;
각 포인트를 가장 가까운 2개의 클러스터에 분배합니다;
각 클러스터에 대해 L = 50, R = 64, alpha = 1.2로 Vamana 인덱스를 구축합니다;
각 클러스터의 인덱스를 병합합니다.
이 인덱스는 평균 out-of-degree가 92.1인 384GB 인덱스를 생성했습니다. 이 인덱스는 64GB DDR4 머신에서 5일 동안 실행되었습니다.
비교 결과는 다음과 같습니다(Figure 2a):
Figure 3.
결론:
한 번에 구축한 인덱스는 병합 기반 인덱스보다 상당히 우수합니다;
병합 기반 인덱스도 훌륭합니다;
병합 기반 인덱싱 방식은 DEEP1B 데이터 세트에도 적용 가능합니다(Figure 2b).
디스크 기반 인덱스: DiskANN VS. FAISS VS. IVF-OADC+G+P
IVFOADC+G+P는 Reference [5]에서 제안된 알고리즘입니다.
본 논문은 DiskANN을 IVFOADC+G+P와만 비교합니다. Reference [5]에서 IVFOADC+G+P가 FAISS보다 우수하다는 것이 입증되었기 때문입니다. 또한 FAISS는 GPU 리소스를 필요로 하며, 모든 플랫폼에서 이를 지원하는 것은 아닙니다.
IVF-OADC+G+P는 HNSW와 IVF-PQ의 조합으로 보입니다. HNSW를 사용하여 클러스터를 결정하고, 대상 클러스터에 일부 pruning 전략을 추가하여 검색을 수행합니다.
결과는 Figure 2a에 있습니다. 그림의 16과 32는 codebook 크기입니다. 데이터 세트는 SIFT1B이며, OPQ로 양자화되었습니다.
코드 구현 세부 정보
DiskANN의 소스 코드는 https://github.com/microsoft/DiskANN 에 오픈 소스로 공개되어 있습니다
2021년 1월, 디스크 솔루션의 소스 코드가 오픈 소스로 공개되었습니다.
다음은 주로 인덱싱 프로세스와 검색 프로세스를 소개합니다.
인덱스 구축
인덱스를 구축하기 위한 매개변수는 8개입니다:
data_type: 옵션에는 float/int8/uint8이 포함됩니다.
data_file.bin: 원본 데이터 바이너리 파일입니다. 파일의 처음 두 정수는 각각 데이터 세트 벡터의 총 개수 n과 벡터 차원 dim을 나타냅니다. 마지막 n * dim * sizeof(data_type) 바이트는 연속적인 벡터 데이터입니다.
index_prefix_path: 출력 파일의 경로 접두사입니다. 인덱스가 구축된 후 여러 인덱스 관련 파일이 생성됩니다. 이 매개변수는 해당 파일들이 저장되는 디렉터리의 공통 접두사입니다.
R: 전역 인덱스의 최대 out-degree입니다.
L: Vamana 인덱스의 매개변수 L로, 후보 집합 크기의 상한입니다.
B: 쿼리 시 메모리 임계값입니다. PQ codebook 크기를 GB 단위로 제어합니다.
M: 인덱스 구축 시 메모리 임계값입니다. fragment의 크기를 GB 단위로 결정합니다.
T: 스레드 수입니다.
인덱싱 프로세스(진입 함수: aux_utils.cpp::build_disk_index):
index_prefix_path에 따라 다양한 출력 파일 이름을 생성합니다.
매개변수 검사.
data_file.bin의 메타를 읽어 n과 dim을 가져옵니다. B와 n에 따라 PQ의 codebook subspace 수 m을 결정합니다.
generate_pq_pivots: p = 1500000/n의 샘플링 비율을 균등하게 사용하여 PQ 학습 세트의 중심점을 샘플링해 PQ를 전역적으로 학습합니다.
generate_pq_data_from_pivots: 전역 PQ codebook을 생성하고, 중심점과 codebook을 별도로 저장합니다.
build_merged_vamana_index: 원본 데이터 세트를 슬라이스하고, 세그먼트별로 Vamana 인덱스를 구축한 뒤, 마지막으로 인덱스를 하나로 병합한다.
partition_with_ram_budget: 매개변수 M에 따라 프래그먼트 수 k를 결정한다. kmeans를 사용하여 데이터 세트를 샘플링하고, 각 포인트를 가장 가까운 두 클러스터에 분배한다. 데이터셋을 프래그먼트로 나누며, 각 프래그먼트는 두 개의 파일을 생성한다: 데이터 파일과 ID 파일. ID 파일과 데이터 파일은 서로 대응되며, ID 파일의 각 ID는 데이터 파일의 벡터 하나에 대응된다. ID는 원본 데이터의 각 벡터에 0부터 n-1까지 번호를 매겨 얻는다. ID는 비교적 중요하며 병합과 관련이 있다.
1500000 / n의 샘플링 비율로 학습 세트를 전역적으로 균일하게 샘플링한다;
num_parts = 3으로 초기화한다. 3부터 반복한다:
- 단계 i의 학습 세트에 대해 num_parts-means++를 수행한다;
- 0.01의 샘플링 비율을 사용하여 테스트 세트를 전역적으로 균일하게 샘플링하고, 테스트 세트를 가장 가까운 2개의 클러스터로 나눈다;
- 각 클러스터의 포인트 수를 세고 이를 샘플링 비율로 나누어 각 클러스터의 포인트 수를 추정한다;
- Vamana 인덱스 크기에 따라 단계 3에서 가장 큰 클러스터에 필요한 메모리를 추정하고, 매개변수 M을 초과하지 않으면 단계 iii로 진행하며, 그렇지 않으면 num_parts ++ 후 단계 2로 돌아간다;
원본 데이터 세트를 num_parts개의 그룹 파일로 나누며, 각 파일 그룹에는 프래그먼트 데이터 파일과 해당 프래그먼트 데이터에 대응하는 ID 파일이 포함된다.
단계 a의 모든 슬라이스에 대해 Vamana 인덱스를 별도로 생성하고 디스크에 저장한다;
merge_shards: num_parts개의 shard Vamana를 전역 인덱스로 병합한다:
num_parts 프래그먼트의 ID 파일을 idmap으로 읽어들인다. 이 idmap은 fragment->id의 순방향 매핑을 설정하는 것과 동일하다;
idmap에 따라 id-> fragments의 역방향 매핑을 설정하고, 각 벡터가 어느 두 프래그먼트에 있는지 파악한다;
1GB 캐시를 가진 reader를 사용하여 num_parts 슬라이스 Vamana 인덱스를 열고, 1GB 캐시를 가진 writer를 사용하여 출력 파일을 열어 병합을 준비한다;
Vamana 인덱스의 num_parts개 navigation points를 center point 파일에 배치하며, 이는 검색 시 사용된다;
ID를 작은 것부터 큰 것 순서로 병합을 시작하고, 역방향 매핑에 따라 각 프래그먼트에서 각 원본 벡터의 이웃 포인트 집합을 차례로 읽고, 중복 제거, shuffle, truncate를 수행한 뒤 출력 파일에 쓴다. 슬라이싱이 원래 전역적으로 정렬되어 있었고, 이제 병합도 순서대로 이루어지므로 최종 flush된 인덱스의 ID와 원본 데이터의 ID는 일대일 대응된다.
프래그먼트 파일, 프래그먼트 인덱스, 프래그먼트 ID 파일을 포함한 임시 파일을 삭제한다.
7.create_disk_layout: 단계 6에서 생성된 전역 인덱스는 compact adjacency table만 가지고 있다. 이 단계는 인덱스를 정렬하기 위한 것이다. adjacency table과 원본 데이터가 함께 저장된다. 검색 시 adjacency table을 로드하고 원본 벡터를 함께 읽어 정확한 거리 계산을 수행한다. SECTOR라는 개념도 있으며, 기본 크기는 4096이다. 각 SECTOR에는 4096 / node_size개의 벡터 정보만 포함된다. node_size = single vector size + single node adjacency table size.
8.마지막으로, 150000 / n의 전역 균일 샘플링을 수행하고 저장하며, 검색 시 warmup에 사용한다.
Search
검색 매개변수는 10개이다:
index_type: 옵션에는 Float/int8/uint8이 포함되며, 인덱스를 구축할 때의 첫 번째 매개변수 data_type과 유사하다.
index_prefix_path: 인덱스 매개변수 index_prefix_path를 참조한다.
num_nodes_to_cache: cache hotspots의 수.
num_threads: 검색 스레드 수.
beamwidth: preload points 수의 상한. 0으로 설정된 경우 시스템이 결정한다.
query_file.bin: 쿼리 세트 파일.
truthset.bin: 결과 세트 파일, "null"은 결과 세트가 제공되지 않으며 프로그램이 직접 계산한다는 의미이다;
K: topk;
result_output_prefix: 검색 결과를 저장할 경로;
L*: 검색 매개변수 목록. 여러 값을 추가할 수 있습니다. 각 L에 대해, 서로 다른 L로 검색하는 동안 통계 정보가 제공됩니다.
검색 프로세스:
관련 데이터 로드: 쿼리 세트, PQ 중심점 데이터, 코드북 데이터, 검색 시작점 및 기타 데이터를 로드하고, 인덱스 메타를 읽습니다.
인덱싱 중에 샘플링된 데이터 세트를 사용하여 cached_beam_search를 수행하고, 각 포인트의 접근 횟수를 집계한 뒤, 접근 빈도가 가장 높은 num_nodes_to_cache개 포인트를 캐시에 로드합니다.
기본적으로 WARMUP 작업이 있습니다. 2단계와 마찬가지로, 이 샘플 데이터 세트도 cached_beam_search를 수행하는 데 사용됩니다.
주어진 매개변수 L의 개수에 따라, 각 L은 쿼리 세트로 다시 cached_beam_search를 수행하며, 재현율 및 QPS와 같은 통계가 출력됩니다. warmup 및 핫스팟 데이터 통계 프로세스는 쿼리 시간에 포함되지 않습니다.
cached_beam_search에 대하여:
후보 시작점에서 쿼리 포인트에 가장 가까운 후보를 찾습니다. 여기서는 PQ 거리가 사용되며, 시작점이 검색 큐에 추가됩니다.
검색 시작:
검색 큐에서, 방문하지 않은 포인트는 beam_width + 2개를 넘지 않습니다. 이러한 포인트가 캐시에 있으면 캐시 히트 큐에 추가합니다. 히트하지 않으면 미스 큐에 추가합니다. 미스 큐의 크기가 beam_width를 초과하지 않도록 합니다.
미스 큐에 있는 포인트에 비동기 디스크 접근 요청을 보냅니다.
캐시에 히트한 포인트의 경우, 원본 데이터와 쿼리 데이터를 사용하여 정확한 거리를 계산하고, 결과 큐에 추가한 다음, PQ를 사용하여 이전에 방문하지 않은 이웃 포인트까지의 거리를 계산한 뒤 검색 큐에 추가합니다. 검색 큐의 길이는 매개변수에 의해 제한됩니다.
step a의 캐시 미스 포인트를 처리하며, step c와 유사합니다.
검색 큐가 비어 있으면 검색이 종료되고, 결과 큐 topk가 반환됩니다.
요약
비교적 긴 작업이지만, 전반적으로 훌륭합니다. 논문과 코드 아이디어는 명확합니다: k-means를 통해 여러 개의 겹치는 버킷을 나눈 다음, 버킷을 나누어 맵 인덱스를 구축하고, 마지막으로 인덱스를 병합하는데, 이는 비교적 새로운 아이디어입니다. 메모리 기반 그래프 인덱스 Vamana의 경우, 본질적으로 트리밍 세분성을 제어할 수 있는 무작위 초기화 버전의 NSG입니다. 쿼리 시에는 cache + pipeline을 충분히 활용하여 io 시간의 일부를 가리고 QPS를 향상시킵니다. 그러나 논문에 따르면, 머신 조건이 특별히 뛰어나지 않더라도 학습 시간이 최대 5일이 걸리며, 사용성은 비교적 낮습니다. 향후 학습 최적화는 분명히 필요합니다. 코드 관점에서 보면, 품질이 비교적 높고 프로덕션 환경에서 직접 사용할 수 있습니다.
참고 문헌
[Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graphs. PVLDB, 12(5):461 – 474, 2019. doi: 10.14778/3303753.3303754.] (http://www.vldb.org/pvldb/vol12/p461-fu.pdf)
Cong Fu and Deng Cai. GitHub - ZJULearning/efanna: ANN 검색 및 KNN 그래프 구축을 위한 빠른 라이브러리.
5. Dmitry Baranchuk, Artem Babenko, and Yury Malkov. 십억 규모 근사 최근접 이웃을 위한 inverted indices 재고찰.
계속 읽기
Announcing the General Availability of Zilliz Cloud BYOC on Google Cloud Platform
Zilliz Cloud BYOC on GCP offers enterprise vector search with full data sovereignty and seamless integration.
Democratizing AI: Making Vector Search Powerful and Affordable
Zilliz democratizes AI vector search with Milvus 2.6 and Zilliz Cloud for powerful, affordable scalability, cutting costs in infrastructure, operations, and development.
AI Integration in Video Surveillance Tools: Transforming the Industry with Vector Databases
Discover how AI and vector databases are revolutionizing video surveillance with real-time analysis, faster threat detection, and intelligent search capabilities for enhanced security.