🚀 완전 관리형 Milvus인 Zilliz Cloud를 무료로 체험해보세요—10배 더 빠른 성능을 경험하세요! 지금 체험하기>>

시작하기

Home
Blog
DiskANN, 수십억 규모의 데이터 세트에서 높은 리콜률과 높은 QPS를 제공하는 디스크 기반 ANNS 솔루션

DiskANN, 수십억 규모의 데이터 세트에서 높은 리콜률과 높은 QPS를 제공하는 디스크 기반 ANNS 솔루션

Engineering

September 24, 2021

Zilliz

질리즈의 R&D 엔지니어인 청밍 리는 동남대학교에서 컴퓨터 공학 석사 학위를 취득했습니다. 현재 그는 그래프 기반 및 양자화 기반 솔루션을 포함하여 고차원 데이터에 대한 ANNS 문제에 집중하고 있습니다.

"DiskANN: 단일 노드에서 빠르고 정확한 10억 개 포인트 최인접 이웃 검색"은 2019년에 NeurIPS에 게재된 논문입니다. 이 논문은 64GB의 RAM과 충분한 용량의 SSD만 갖춘 단일 머신으로 10억 개 규모의 데이터 세트에 대한 인덱스 구축과 검색을 수행하는 최첨단 방법을 소개합니다. 또한 대규모 데이터 세트에서 ANNS(근사 이웃 검색)의 세 가지 요구 사항인 높은 리콜, 낮은 지연 시간, 높은 밀도(단일 머신의 노드 수)를 충족합니다. 이 방법은 64GB RAM과 16코어 CPU를 갖춘 단일 머신을 사용하여 10억 개 규모의 데이터 세트 SIFT-1B에 그래프 기반 인덱스를 구축하며, 95% 이상의 리콜률@1로 5000 QPS(초당 쿼리 수)에 도달하고 평균 지연 시간은 3ms 미만으로 낮춥니다.

저자

수하스 자야람 수브라마냐: 전 Microsoft 인도 연구소의 직원, CMU 박사 과정 학생. 주요 연구 분야는 대규모 데이터를 위한 고성능 컴퓨팅과 머신 러닝 알고리즘입니다.

Devvrit: 텍사스 대학교 오스틴 캠퍼스 대학원 연구 조교. 이론적 컴퓨터 과학, 머신 러닝, 딥 러닝을 연구하고 있습니다.

로한 카데코디: 텍사스 대학교 박사 과정 학생. 그의 연구 방향은 시스템 및 스토리지이며, 주로 영구 스토리지, 파일 시스템 및 kV 스토리지를 포함합니다.

라비샨카르 크리샤스와미: Microsoft 인도 연구소의 수석 연구원. CMU 박사. 연구 방향은 그래프와 클러스터링을 기반으로 한 근사화 알고리즘입니다.

하르샤 바르단 심하드리: 마이크로소프트 인도 연구소 수석 연구원. CMU 박사. 과거에는 병렬 알고리즘과 런타임 시스템을 연구했습니다. 지금은 새로운 알고리즘을 개발하고 프로그래밍 모델을 작성하는 것이 주요 업무입니다.

동기

대부분의 주류 ANNS 알고리즘은 인덱스 구축 성능, 검색 성능, 리콜 사이에서 어느 정도 절충점을 찾습니다. HNSW 및 NSG와 같은 그래프 기반 알고리즘은 현재 검색 성능과 리콜 측면에서 최첨단 방식입니다. 메모리 상주 그래프 기반 색인 방식은 너무 많은 메모리를 차지하기 때문에 메모리 리소스가 제한된 단일 머신으로 대규모 데이터셋을 색인하고 검색하는 것은 상대적으로 어렵습니다.

많은 애플리케이션은 수십억 개의 대규모 데이터 세트에 대해 유클리드 거리 기반 ANNS의 빠른 응답을 필요로 합니다. 다음은 두 가지 주요 솔루션입니다:

역 인덱스 + 양자화: 데이터 세트를 M개의 파티션으로 클러스터링하고 PQ(제품 양자화)와 같은 양자화 체계를 사용해 데이터 세트를 압축하는 것입니다. 이 솔루션은 데이터 압축으로 인한 정밀도 손실로 인해 낮은 리콜을 생성합니다. 탑케이를 높이면 정확도는 향상되지만 그에 따라 QPS는 떨어집니다.
분할 및 색인: 데이터 세트를 여러 개의 분리된 샤드로 나누고 각 샤드에 대해 인메모리 색인을 구축합니다. 쿼리 요청이 들어오면 각 샤드의 인덱스에서 검색이 수행되고 병합 후 결과가 반환됩니다. 이 솔루션은 데이터 세트 규모가 과도하게 확장되므로 단일 머신의 메모리 리소스 제한으로 인해 더 많은 머신이 필요하게 되고, 이는 낮은 QPS로 이어집니다.

위에서 언급한 두 가지 솔루션은 모두 단일 머신의 메모리 제한으로 인해 한계가 있습니다. 이 백서에서는 이 문제를 해결하기 위해 SSD 상주 인덱싱 메커니즘의 설계를 제안합니다. SSD 상주 인덱싱의 과제는 무작위 디스크 액세스 횟수와 디스크 액세스 요청 횟수를 줄이는 것입니다.

기여

이 백서에서는 대규모 데이터 세트에 대한 검색을 효과적으로 지원할 수 있는 DiskANN이라는 SSD 상주 ANNS 체계를 제시합니다. 이 체계는 이 백서에서 제시된 그래프 기반 알고리즘을 기반으로 합니다: Vamana. 이 백서의 기여는 다음과 같습니다:

DiskANN은 64GB RAM이 장착된 단일 컴퓨터에서 100개 이상의 차원으로 구성된 10억 개의 대규모 데이터 세트를 색인하고 검색할 수 있으며, 5밀리초 미만의 지연 시간으로 95% 이상의 리콜률@1을 제공합니다.
디스크 액세스 횟수를 최소화하기 위해 NSG와 HNSW보다 검색 반경이 더 작은 새로운 그래프 기반 알고리즘인 Vamana가 제안되었습니다.
Vamana는 메모리에서 작동할 수 있으며 성능은 NSG 및 HNSW보다 느리지 않습니다.
대규모 데이터 세트의 겹치는 파티션에 구축된 작은 Vamana 인덱스는 연결성을 잃지 않고 하나의 그래프로 병합할 수 있습니다.
Vamana는 PQ와 같은 양자화 체계와 결합할 수 있습니다. 그래프 구조와 원본 데이터는 디스크에 저장되고 압축된 데이터는 메모리에 보관됩니다.

바마나

이 알고리즘은 NSG[2][4]의 아이디어와 유사합니다(NSG를 이해하지 못하는 분들은 참고자료 [2]를 참고하시고, 논문을 읽고 싶지 않으시다면 참고자료 [4]를 참고하시면 됩니다). 가장 큰 차이점은 트리밍 전략에 있습니다. 정확히 말하면, NSG의 트리밍 전략에 스위치 알파가 추가되었습니다. NSG 트리밍 전략의 주요 아이디어는 목표 점의 이웃을 가능한 한 다양하게 선택한다는 것입니다. 새 이웃이 목표 점보다 목표 점의 이웃에 더 가깝다면 이 점을 이웃 점 집합에 추가할 필요가 없습니다. 즉, 대상 포인트의 각 이웃에 대해 주변 반경 거리(대상 포인트, 이웃 포인트) 내에 다른 이웃 포인트가 있을 수 없습니다. 이 트리밍 전략은 그래프의 아웃도를 효과적으로 제어하며 비교적 급진적입니다. 인덱스의 메모리 공간을 줄이고 검색 속도를 향상시키지만 검색 정확도도 떨어뜨립니다. Vamana의 트리밍 전략은 파라미터 알파를 통해 트리밍의 규모를 자유롭게 제어하는 것입니다. 작동 원리는 트리밍 조건의 거리(이웃점, 후보점)에 파라미터 알파(1 이상)를 곱하는 것입니다. dist(목표 점, 특정 후보 점)가 확대된 기준 거리보다 클 때만 트리밍 전략이 채택되어 목표 점의 이웃 간 상호 제외 허용 오차가 증가합니다.

Vamana의 인덱싱 프로세스는 비교적 간단합니다:

임의의 그래프를 초기화합니다;
NSG의 내비게이션 포인트와 유사한 시작점을 계산합니다. 먼저 글로벌 중심을 찾은 다음, 글로벌 중심과 가장 가까운 지점을 탐색 지점으로 찾습니다. Vamana와 NSG의 차이점은 NSG의 입력은 이미 가장 가까운 이웃 그래프이므로 사용자는 초기 이웃 그래프에서 직접 중심점에 대한 근사 이웃 검색을 수행할 수 있다는 점입니다. 그러나 Vamana는 임의의 최근접 이웃 그래프를 초기화하므로 사용자는 임의의 그래프에서 직접 근사치 검색을 수행할 수 없습니다. 후속 반복의 시작점으로 탐색 지점을 얻기 위해 전역 비교를 수행해야 합니다. 이 지점의 목적은 평균 검색 반경을 최소화하는 것입니다;
초기화된 무작위 이웃 그래프와 2단계에서 결정한 탐색 시작점을 기반으로 각 점에 대해 근사 이웃 탐색을 수행하고 탐색 경로의 모든 점을 후보 이웃으로 설정한 후 알파 = 1을 사용하여 에지 트리밍 전략을 실행합니다. NSG와 마찬가지로 탐색 시작점에서 시작하는 탐색 경로상의 모든 점을 후보 이웃 집합으로 선택하면 일부 긴 에지가 증가하여 효과적으로 탐색 반경을 줄일 수 있습니다.
알파를 1 이상으로 조정하고(논문에서는 1.2를 권장) 3단계를 반복합니다. 3단계는 임의의 가장 가까운 이웃 그래프를 기반으로 하지만, 첫 번째 반복 후에는 그래프의 품질이 떨어집니다. 따라서 리콜률에 매우 중요한 그래프 품질을 개선하기 위해 또 다른 반복이 필요합니다.

이 백서에서는 세 가지 그래프 인덱스, 즉 Vamana, NSG, HNSW를 비교합니다. 인덱싱 및 쿼리 성능 측면에서 Vamana와 NSG는 비교적 비슷하며, 둘 다 HNSW를 약간 앞섭니다. 데이터는 아래 실험 섹션을 참조하세요.

2.png

이 백서에서는 Vamana 인덱스의 구축 과정을 시각화하기 위해 200개의 2차원 포인트를 사용하여 두 차례의 반복을 시뮬레이션하는 그래프를 제공합니다. 첫 번째 행은 알파 = 1을 사용하여 가장자리를 다듬습니다. 트리밍 전략이 비교적 급진적이며 많은 수의 가장자리가 트리밍되는 것을 볼 수 있습니다. 알파 값을 높이고 트리밍 조건을 느슨하게 하면 많은 가장자리가 다시 추가되는 것을 알 수 있습니다. 최종 그래프에서는 상당히 긴 에지가 추가됩니다. 검색 반경을 효과적으로 줄일 수 있습니다.

DiskANN

메모리가 64GB에 불과한 개인용 컴퓨터로는 인덱스는 말할 것도 없고 10억 개의 원시 데이터도 저장할 수 없습니다. 앞으로 두 가지 과제가 있습니다: 1. 제한된 메모리 리소스로 이러한 대규모 데이터 세트를 어떻게 색인할 것인가? 2. 원본 데이터를 메모리에 로드할 수 없는 경우 검색 시 거리를 어떻게 계산할 것인가?

이 논문은 다음과 같은 해결책을 제안했습니다:

첫 번째 과제의 경우, 먼저 k-평균을 사용하여 데이터를 k개의 클러스터로 나눈 다음 각 점을 가장 가까운 i개의 클러스터에 할당합니다. 일반적으로 숫자 i는 2이면 충분합니다. 각 클러스터에 대해 메모리 기반 Vamana 인덱스를 구축한 다음, 마지막으로 k개의 Vamana 인덱스를 하나로 병합합니다.
두 번째 과제는 원본 벡터에 인덱스를 구축하고 압축된 벡터를 쿼리하는 것입니다. 원본 벡터에 인덱스를 구축하면 그래프의 품질이 보장되고, 압축된 벡터는 메모리에 로드되어 세분화된 검색을 할 수 있습니다. 압축된 벡터로 검색하면 정확도가 떨어질 수 있지만 그래프의 품질이 충분히 높으면 일반적인 방향은 정확할 것입니다. 최종 거리 결과는 원본 벡터를 사용하여 계산됩니다.

DiskANN의 인덱스 레이아웃은 일반적인 그래프 인덱스와 유사합니다. 각 포인트의 이웃 집합과 원본 벡터 데이터가 함께 저장됩니다. 이렇게 하면 데이터의 로컬리티를 더 잘 활용할 수 있습니다.

앞서 언급했듯이 인덱스 데이터가 SSD에 저장되는 경우, 검색 지연을 줄이기 위해 디스크 액세스 횟수와 디스크 읽기 및 쓰기 요청을 최대한 줄여야 합니다. 따라서 DiskANN은 두 가지 최적화 전략을 제안합니다:

캐시 핫스팟: 메모리의 시작 지점에서 C 점프 내의 모든 지점을 캐시합니다. C의 값은 3~4개 이내로 설정하는 것이 좋습니다.
빔 검색: 간단히 말해, 이웃 정보를 미리 로드하는 것입니다. 점 p를 검색할 때 p의 이웃 점이 메모리에 없는 경우 디스크에서 불러와야 합니다. 소량의 SSD 랜덤 액세스 작업은 SSD 단일 섹터 액세스 작업과 거의 같은 시간이 걸리므로 액세스하지 않은 W개의 이웃 포인트 정보를 한 번에 로드할 수 있습니다. W는 너무 크거나 작게 설정할 수 없습니다. W가 크면 컴퓨팅 리소스와 SSD 대역폭이 낭비되고, 작으면 검색 지연이 증가합니다.

실험

실험은 세 그룹으로 구성됩니다:

메모리 기반 인덱스 간 비교: Vamana VS. NSG VS. HNSW

데이터 세트: SIFT1M(128개 차원), GIST1M(960개 차원), DEEP1M(96개 차원) 및 DEEP1B에서 무작위로 샘플링된 1M 데이터 세트.

인덱스 매개변수(모든 데이터 세트는 동일한 매개변수 세트를 사용함):

HNSW: M = 128, efc = 512.

Vamana: R = 70, L = 75, 알파 = 1.2.

NSG: R = 60, L = 70, C = 500.

검색 매개변수는 문서에 제공되지 않으며, 이는 색인 매개변수와 일치할 수 있습니다. 파라미터 선택의 경우, 논문에서 언급된 NSG의 파라미터는 더 나은 성능을 가진 그룹을 선택하기 위해 NSG의 GitHub 리포지토리에 나열된 파라미터를 기반으로 합니다. Vamana와 NSG는 비교적 유사하기 때문에 파라미터도 비슷하게 설정되어 있습니다. 그러나 HNSW 파라미터 선택의 이유는 제공되지 않습니다. HNSW의 파라미터 M이 상대적으로 크게 설정된 것으로 판단됩니다. 그래프 기반 인덱스의 외곽도가 같은 수준으로 설정되지 않으면 그래프 기반 인덱스 간의 비교가 설득력이 떨어질 수 있습니다.

위의 인덱싱 파라미터에 따라 Vamana, HNSW, NSG의 인덱싱 시간은 각각 129초, 219초, 480초입니다. NSG 인덱싱 시간에는 EFANN [3]으로 초기 이웃 그래프를 구성하는 시간이 포함됩니다.

리콜-QPS 곡선:

3.png

그림 3을 보면 세 가지 데이터 세트에서 Vamana의 성능이 NSG와 비슷하고 HNSW보다 약간 더 우수하다는 것을 알 수 있습니다.

검색 반경 비교:

그림 2.c를 보면, 동일한 리콜률에서 평균 검색 경로가 NSG와 HNSW에 비해 Vamana가 가장 짧다는 것을 알 수 있습니다.

일회성 구축 인덱스와 대규모 병합 인덱스 비교

데이터 세트: SIFT1B

일회성 구축 인덱스 매개변수: L = 50, R = 128, 알파 = 1.2. 1800G DDR3 머신에서 2일간 실행한 후, 피크 메모리는 약 1100G이고 평균 아웃도는 113.9입니다.

병합을 기반으로 한 인덱싱 절차:

kmeans를 사용하여 데이터 세트에서 40개의 클러스터를 훈련합니다;
각 포인트는 가장 가까운 2개의 클러스터로 분포됩니다;
각 클러스터에 대해 L = 50, R = 64, 알파 = 1.2의 Vamana 인덱스를 구축합니다;
각 클러스터의 인덱스를 병합합니다.

이 인덱스는 평균 편차가 92.1인 384GB의 인덱스를 생성했습니다. 이 인덱스는 64GB DDR4 머신에서 5일 동안 실행되었습니다.

비교 결과는 다음과 같습니다(그림 2a): 4.png

결론적으로:

일회성 구축 인덱스가 병합 기반 인덱스보다 훨씬 우수합니다;
병합 기반 인덱스도 우수합니다;
병합 기반 인덱싱 방식은 DEEP1B 데이터 세트에도 적용할 수 있습니다(그림 2b).

디스크 기반 인덱스: DiskANN VS. FAISS VS. IVF-OADC+G+P

IVFOADC+G+P는 참조 [5]에서 제안된 알고리즘입니다.

참고 문헌 [5]에서 IVFOADC+G+P가 FAISS보다 우수하다는 것이 입증되었기 때문에 이 백서에서는 DiskANN과 IVFOADC+G+P만 비교합니다. 또한 FAISS는 모든 플랫폼에서 지원되지 않는 GPU 리소스를 필요로 합니다.

IVF-OADC+G+P는 HNSW와 IVF-PQ의 조합으로 보입니다. HNSW를 사용하여 클러스터를 결정하고 대상 클러스터에 몇 가지 가지 치기 전략을 추가하여 검색을 수행합니다.

결과는 그림 2a와 같습니다. 그림에서 16과 32는 코드북 크기입니다. 데이터 세트는 OPQ로 정량화된 SIFT1B입니다.

코드 구현 세부 정보

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: 글로벌 인덱스의 최대 아웃도입니다.

L: 후보 세트 크기의 상한인 Vamana 인덱스의 파라미터 L입니다.

B: 쿼리 시 메모리 임계값입니다. PQ 코드북 크기를 GB 단위로 제어합니다.

M: 인덱스 구축 시 메모리 임계값입니다. 조각의 크기를 GB 단위로 결정합니다.

T: 스레드 수입니다.

인덱싱 프로세스(입력 함수: aux_utils.cpp::build_disk_index):

index_prefix_path에 따라 다양한 출력 파일 이름을 생성합니다.
매개변수 확인.
data_file.bin의 메타를 읽어 n과 dim을 구합니다. B와 n에 따라 PQ의 코드북 서브스페이스 번호 m을 결정합니다.
GENERATE_PQ_PIVOTS: p = 1500000/n의 샘플링 속도를 사용하여 PQ 훈련 세트의 중심점을 균일하게 샘플링하여 PQ를 전체적으로 훈련합니다.
GENERATE_PQ_DATA_From_피벗: 글로벌 PQ 코드북을 생성하고, 중심점과 코드북을 별도로 저장합니다.
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부터 반복합니다:
  - 1단계의 훈련 세트에 대해 num_parts-means++를 수행합니다;
  - 0.01의 샘플링 속도를 사용하여 테스트 집합을 전체적으로 균일하게 샘플링하고 테스트 집합을 가장 가까운 2개의 클러스터로 나눕니다;
  - 각 클러스터의 포인트 수를 세고 이를 샘플링 비율로 나누어 각 클러스터의 포인트 수를 추정합니다;
  - 3단계에서 가장 큰 클러스터에 필요한 메모리를 Vamana 인덱스 크기에 따라 추정하고, 매개변수 M을 초과하지 않으면 3단계로 이동하고, 그렇지 않으면 num_parts ++ 2단계로 돌아갑니다;
- 원본 데이터 세트를 num_parts 그룹 파일로 나누고, 각 파일 그룹에는 조각화된 데이터 파일과 조각화된 데이터에 해당하는 ID 파일이 포함됩니다.
a단계의 모든 조각에 대해 별도로 Vamana 인덱스를 생성하고 디스크에 저장합니다;
merge_shards: num_parts 샤드 Vamana를 전역 인덱스에 병합합니다:
- num_parts 조각의 ID 파일을 idmap으로 읽습니다. 이 idmap은 fragment->id의 정방향 매핑을 설정하는 것과 동일합니다;
- idmap에 따라 id-> 조각의 역매핑을 설정하고 각 벡터가 어떤 두 개의 조각에 속하는지 파악합니다;
- 1GB 캐시가 있는 리더를 사용해 num_parts 슬라이스 Vamana 인덱스를 열고, 1GB 캐시가 있는 쓰기기를 사용해 병합할 준비가 된 출력 파일을 엽니다;
- 검색할 때 사용할 중심점 파일에 Vamana 인덱스의 num_parts 탐색 포인트를 배치합니다;
- 작은 것부터 큰 것까지 ID에 따라 병합을 시작하고, 역 매핑에 따라 각 조각에서 각 원본 벡터의 이웃 포인트 세트를 차례로 읽고, 중복 제거, 셔플, 잘라내어 출력 파일에 씁니다. 슬라이싱은 원래 전 세계적으로 정렬되었고 이제 병합도 정렬되었으므로 최종 플러시된 인덱스의 ID와 원본 데이터의 ID는 일대일 대응입니다.
- 조각 파일, 조각 인덱스, 조각 ID 파일을 포함한 임시 파일을 삭제합니다.

create_disk_layout: 6단계에서 생성된 글로벌 인덱스에는 간결한 인접성 테이블만 있습니다. 이 단계는 인덱스를 정렬하는 것입니다. 인접성 테이블과 원본 데이터가 함께 저장됩니다. 검색할 때 정확한 거리 계산을 위해 인접성 테이블을 로드하고 원본 벡터를 함께 읽습니다. 기본 크기가 4096인 SECTOR라는 개념도 있습니다. 각 SECTOR에는 4096개 / node_size의 벡터 정보만 포함됩니다. node_size = 단일 벡터 크기 + 단일 노드 인접 테이블 크기.
마지막으로 150000 / n의 전역 균일 샘플링을 수행하여 저장하고 검색 시 워밍업에 사용합니다.

검색

검색 매개변수는 10가지가 있습니다:

index_type: 옵션에는 인덱스 작성 시 첫 번째 매개변수 data_type과 유사한 Float/int8/uint8이 포함됩니다.
index_prefix_path: 인덱스 매개변수 index_prefix_path를 참조하세요.
num_nodes_to_cache: 캐시 핫스팟의 수입니다.
num_threads: 검색 스레드 수입니다.
빔폭: 프리로드 포인트 수의 상한. 0으로 설정된 경우 시스템에서 결정합니다.
query_file.bin: 쿼리 세트 파일.
truthset.bin: 결과 집합 파일, "null"은 결과 집합이 제공되지 않고 프로그램에서 자체적으로 계산한다는 의미입니다;
K: topk;
결과_출력_접두사: 검색 결과를 저장할 경로;
L*: 검색 매개변수 목록. 여러 값을 추가할 수 있습니다. 각 L에 대해 다른 L로 검색하는 동안 통계 정보가 제공됩니다.

검색 프로세스:

관련 데이터 로드: 쿼리 세트, PQ 중심점 데이터, 코드북 데이터, 검색 시작점 및 기타 데이터를 로드하고 인덱스 메타를 읽습니다.
인덱싱 중에 샘플링된 데이터 세트를 사용하여 cached_beam_search를 수행하고, 각 포인트의 액세스 횟수를 계산한 후 액세스 빈도가 가장 높은 num_nodes_to_cache 포인트를 캐시에 로드합니다.
기본적으로 WARMUP 작업이 수행됩니다. 2단계와 마찬가지로 이 샘플 데이터 세트도 cached_beam_search를 수행하는 데 사용됩니다.
주어진 파라미터 L의 개수에 따라 각 L은 쿼리 세트로 다시 cached_beam_search를 수행하여 리콜률, QPS 등의 통계가 출력됩니다. 워밍업 과정과 통계 핫스팟 데이터는 쿼리 시간에 포함되지 않습니다.

캐시된 빔 검색에 대해:

후보 시작점에서 쿼리 지점에 가장 가까운 후보를 찾습니다. 여기에는 PQ 거리가 사용되며 시작 지점이 검색 대기열에 추가됩니다.
검색을 시작합니다:

검색 대기열에서 빔 폭 + 방문하지 않은 포인트 2개 이하입니다. 이러한 지점이 캐시에 있는 경우 캐시 히트 대기열에 추가합니다. 히트되지 않은 경우 미스 대기열에 추가합니다. 미스 큐의 크기가 beam_width를 초과하지 않는지 확인하세요.
미스 큐에 있는 지점에 비동기 디스크 액세스 요청을 보냅니다.
캐시에 도달한 지점에 대해 원본 데이터와 쿼리 데이터를 사용하여 정확한 거리를 계산하고 결과 대기열에 추가한 다음 PQ를 사용하여 검색 대기열에 추가하기 전에 방문하지 않은 이웃 지점까지의 거리를 계산합니다. 검색 대기열의 길이는 매개변수에 의해 제한됩니다.
캐시된 미스 포인트를 C단계와 유사하게 A단계에서 처리합니다.
검색 큐가 비어 있으면 검색이 종료되고 결과 큐의 최상위 값이 반환됩니다.

요약

비교적 긴 작업이지만 전반적으로 훌륭합니다. 논문과 코드의 아이디어는 명확합니다. k-평균을 통해 여러 개의 겹치는 버킷을 나눈 다음 버킷을 나누어 맵 인덱스를 만들고 마지막으로 인덱스를 병합하는 것은 비교적 새로운 아이디어입니다. 메모리 기반 그래프 인덱스 Vamana의 경우, 기본적으로 트리밍 세분성을 제어할 수 있는 무작위로 초기화된 NSG 버전입니다. 쿼리할 때 캐시 + 파이프라인을 최대한 활용하고, io 시간의 일부를 커버하며, QPS를 개선합니다. 하지만 논문에 따르면 머신 상태가 특별하지 않더라도 학습 시간이 최대 5일이 걸리고, 사용성이 상대적으로 낮다고 합니다. 향후 훈련에 대한 최적화가 반드시 필요합니다. 코드 관점에서 보면 상대적으로 품질이 높고 프로덕션 환경에서 바로 사용할 수 있습니다.