인덱싱은 데이터를 효율적으로 구성하는 과정으로, 대규모 데이터셋에서 시간이 많이 걸리는 쿼리를 크게 가속화하여 유사성 검색을 효과적으로 만드는 주요한 역할을 한다.

ANNS vector indexes

Mivus는 대부분 ANNS(Approximate Nearest Neighbors Search) 알고리즘을 이용하는 인덱스 방법을 지원한다. ANNS 방법으로 정확성이 조금 낮더라도 검색 속도를 개선할 수 있다.

ANNS 벡터 index는 구현방법에 따라 크게 tree-based, graph-based, hash-based, quantization-based의 4가지 유형으로 분류할 수 있다.

Indexes supported in Milvus

Milvus는 벡터 임베딩 타입에 따라 다양한 index type을 지원한다. 벡터 임베딩 타입은 Dense vector (floating-point embeddings), binary embeddings, sparse embeddings로 나뉜다. 이 중 블로거는 Dense vector 타입만을 정리하였다.

These types of indexes include FLAT, IVF_FLAT, IVF_PQ, IVF_SQ8, HNSW, and SCANN for CPU-based ANN searches.

Supported index	Classification	Scenario
FLAT	N/A	• Relatively small dataset • Requires a 100% recall rate
IVF_FLAT	Quantization-based index	• High-speed query • Requires a recall rate as high as possible
IVF_SQ8	Quantization-based index	• High-speed query • Limited memory resources • Accepts minor compromise in recall rate
IVF_PQ	Quantization-based index	• Very high-speed query Limited memory resources Accepts substantial compromise in recall rate
HNSW	Graph-based index	• Very high-speed query • Requires a recall rate as high as possible • Large memory resources
SCANN	Quantization-based index	• Very high-speed query • Requires a recall rate as high as possible • Large memory resources

FLAT

• 완벽한 정확도가 필요한 작은 데이터셋(수백만 규모)에 적합
• 벡터를 압축하지 않으며 정확한 검색 결과를 보장하는 유일한 인덱스 방법 ⇒ 다른 인덱스의 정답 데이터로 활용할 수 있음
• 각각의 쿼리는 데이터셋 내 모든 벡터를 비교 ⇒ 이로 인해 높은 정확도를 보장하지만 처리 속도가 느려 대규모 데이터셋에는 적합하지 않음
• 별도의 매개 변수 설정이 필요없고 데이터 학습 과정 없이 사용 가능함
• search parameters

  Parameter	Description	Range
  metric_type	[Optional] The chosen distance metric.	See Supported Metrics.

IVF_FLAT

• 벡터 데이터를 nlist 클러스터 단위로 나누고, target 입력 벡터와 각 클러스터 중심 사이의 거리를 비교함.
• 시스템이 설정한 nprobe 수에 따라, 질의할 클러스터 수가 결정됨 → 가장 유사한 클러스터 내 벡터들만 비교하여 유사도 검색 결과를 반환함 → 질의 시간을 크게 단축시킴.
• nprobe를 조정하여 주어진 상황에서 정확도와 속도 간의 최적 균형을 찾을 수 있음. IVF_FLAT performance test에 따르면, target 입력 벡터 수(nq)와 검색할 클러스터 수(nprobe)가 증가할수록 질의 시간이 급격히 증가함.
• IVF_FLAT은 가장 기본적인 IVF 인덱스로, embedding vector를 압축하거나 훼손하지 않음
• Index building parameters

  Parameter	Description	Range	Default Value
  nlist	Number of cluster units	[1, 65536]	128

• Search parameters
  • common search

    Parameter	Description	Range	Default Value
    nprobe	Number of units to query	[1, nlist]	8

  • range search

    Parameter	Description	Range	Default Value
    max_empty_result_buckets	Maximum number of buckets not returning any search results.This is a range-search parameter and terminates the search process whilst the number of consecutive empty buckets reaches the specified value.Increasing this value can improve recall rate at the cost of increased search time.	[1, 65535]	2

IVF_SQ8

• IVF_FLAT은 압축을 수행하지 않기에 생성된 인덱스 파일 크기는 원본 벡터 데이터 크기와 거의 동일함. 예를 들어 원본 1B SIFT 데이터셋이 476GB라면, IVF_FLAT 인덱스 파일은 약간 작아진 470GB 정도 → 모든 인덱스 파일을 메모리에 로드하려면, 470GB의 저장 공간이 필요함.
  
• IVF_FLAT은 많은 자원을 차지하기에 디스크, CPU, GPU 메모리의 자원이 제한적일 경우, IVF_SQ8이 IVF_FLAT보다 더 좋은 선택이 될 것
• 이 인덱스 타입은 Scalar Quantization(SQ)를 통해 각 FLOAT(4바이트)를 UINT8(1바이트)로 변환 가능 → 디스크, CPU, GPU 메모리 소비를 70–75% 절감할 수 있음.
• 예를 들어 1B SIFT 데이터셋의 경우, IVF_SQ8 인덱스 파일은 단 140GB의 저장 공간만 요구함.
• 파라미터는 IVF_FLAT의 파라미터와 동일

IVF_PQ

• PQ(Product Quantization)는 원본 고차원 벡터 공간을 m개의 저차원 벡터 공간의 Cartesian products으로 분해함. 그리고 분해된 저차원 벡터 공간들을 양자화함.
• 이를 통해 모든 차원을 계산해서 target 벡터와 클러스터를 거리를 구하는 대신, 더 작아진 차원의 벡터로 거리를 계산할 수 있게 됨 → 시간 복잡도와 공간 복잡도를 크게 줄임.
• 이때 quantizing the product of vectors을 수행하기 전에, IVF 인덱싱 클러스터링을 수행함. 💡 즉 양자화하기 전에 온전한 embedding 값들로 클러스터링을 하는 것인데, 이러면 클러스터링할 때는 성능의 저하가 없다. 양쟈화를 했다길래 양자하된 벡터들로 클러스터링을 할 줄 알았는데, 클러스터링은 양자화하기 전 벡터들로 하였다고 해서 좋은 방법이라고 생각하여 기록
• 결과적으로 인덱스 파일은 IVF_SQ8보다 더 작으나, 벡터 검색 시 정확도 손실을 초래함
• Index building parameters

  Parameter	Description	Range
  nlist	Number of cluster units	[1, 65536]
  m	Number of factors of product quantization	dim mod m == 0
  nbits	[Optional] Number of bits in which each low-dimensional vector is stored.	[1, 64] (8 by default)

• Search parameters IVF_FLAT의 파라미터와 일치
  

SCANN

• ScaNN(Scalable Nearest Neighbors)는 벡터 클러스터링과 Product Quantization 측면에서 IVF_PQ와 유사함.
• 하지만, Product Quantization 구현 세부사항과 효율적인 계산을 위한 SIMD(Single-Instruction/Multi-data) 활용에서 차이가 있음.
• SIMD란 (by chatGPT) 컴퓨터 프로세싱 아키텍처의 한 형태로, 하나의 명령어를 여러 데이터에 동시에 적용하여 병렬 처리를 수행하는 방식. 이는 특히 벡터 및 행렬 연산과 같이 동일한 작업을 대량의 데이터에 반복적으로 수행해야 하는 상황에서 매우 효율적.

  주요 특징:

  1. 동시성: 여러 데이터 요소를 병렬로 처리하여 성능을 크게 향상시킴.

  2. 적용 분야: 그래픽 처리, 신호 처리, 머신 러닝, 벡터 연산 등 대규모 데이터 병렬 처리가 필요한 작업에 사용됨.

  3. 하드웨어 지원: 현대 CPU 및 GPU에는 SIMD 연산을 지원하는 명령어 세트(예: Intel의 SSE/AVX, ARM의 NEON)가 내장되어 있음.

     작동 원리:

  • 같은 작업을 여러 데이터 요소에 동시에 수행하려면, 데이터를 특정 크기(예: 128비트, 256비트)로 묶은 벡터 레지스터에 로드함.

  • 하나의 명령어로 묶인 데이터 요소들에 병렬 계산을 적용.

    예시:

  • 일반적 방식: 4개의 숫자 배열에 대해 각각 덧셈 연산을 수행하려면 4번의 연산이 필요함.

  • SIMD 방식: 한 번의 명령으로 4개의 숫자 배열에 대해 동시에 연산을 수행함.

• Index building parameters : Unlike IVF_PQ, default values apply to m and nbits for optimized performance.

  Parameter	Description	Range
  nlist	Number of cluster units	[1, 65536]
  with_raw_data	Whether to include the raw data in the index	True or False. Defaults to True.

• Search parameters
  • Common search

    Parameter	Description	Range	Default value
    nprobe	Number of units to query	[1, nlist]
    reorder_k	Number of candidate units to query	[top_k, ∞]	top_k

  • range search IVF_FLAT의 파라미터와 일치
    

HNSW

• HNSW(Hierarchical Navigable Small World Graph)는 그래프 기반 인덱싱 알고리즘으로, 특정 규칙에 따라 image에 대한 다층 내비게이션 구조를 생성함.
• 이 구조에서 상위 계층은 더 sparse하고 노드 간 거리가 멀며, 하위 계층은 더 dense하고 노드 간 거리가 가까움.
• 탐색은 최상위 계층에서 시작해, 이 계층에서 대상과 가장 가까운 노드를 찾은 후 다음 계층으로 내려가 탐색을 반복함. 이를 여러번 반복하여 대상 위치에 빠르게 접근 가능.
• 성능 향상을 위해, HNSW는 각 계층에서 노드의 최대 연결 수를 M으로 제한함. 또한 efConstruction(인덱스 생성 시) 또는 ef(대상 탐색 시)를 사용해 탐색 범위를 지정할 수 있음.
• Index building parameters

  Parameter	Description	Range
  M	M defines tha maximum number of outgoing connections in the graph. Higher M leads to higher accuracy/run_time at fixed ef/efConstruction.	[2, 2048]
  efConstruction	ef_construction controls index search speed/build speed tradeoff. Increasing the efConstruction parameter may enhance index quality, but it also tends to lengthen the indexing time.	[1, int_max]

• Search parameters

  Parameter	Description	Range
  ef	Parameter controlling query time/accuracy trade-off. Higher ef leads to more accurate but slower search.	[top_k, int_max]

참고자료

• https://milvus.io/docs/index.md?tab=floating