IVF_SQ8

IVF_SQ8 인덱스는 대규모 유사도 검색 문제를 다루기 위한 양자화 기반(quantization-based) 인덱싱 알고리즘이에요. 벡터를 전부 비교하는 완전 탐색 방식(exhaustive search)보다 훨씬 작은 메모리로 더 빠른 검색을 달성해요.

출처: Milvus 문서

본문

개요 (Overview)

IVF_SQ8 인덱스는 두 가지 핵심 구성 요소 위에 만들어져요:

• Inverted File (IVF): 데이터를 클러스터로 정리해서 검색 알고리즘이 가장 관련 있는 벡터 부분집합에만 집중할 수 있게 해요.
• Scalar Quantization (SQ8): 벡터를 더 컴팩트한 형태로 압축해 메모리 사용량을 크게 줄이면서도 빠른 유사도 계산에 충분한 정밀도를 유지해요.

IVF

IVF는 책에 색인을 만드는 것과 비슷해요. 모든 페이지(여기서는 모든 벡터)를 훑는 대신, 색인에서 특정 키워드(클러스터)를 찾아 관련 페이지(벡터)를 빠르게 찾아내는 방식이에요. 우리 시나리오에서는 벡터를 클러스터로 묶고, 알고리즘이 쿼리 벡터와 가까운 몇 개 클러스터 안에서만 검색해요.

동작 방식은 다음과 같아요:

• 클러스터링 (Clustering): k-means 같은 클러스터링 알고리즘으로 벡터 데이터셋을 지정된 수의 클러스터로 나눠요. 각 클러스터에는 중심(centroid, 클러스터를 대표하는 벡터)이 있어요.
• 할당 (Assignment): 각 벡터를 자신과 가장 가까운 중심을 가진 클러스터에 할당해요.
• 역인덱스 (Inverted Index): 각 클러스터 중심을 그 클러스터에 할당된 벡터 목록에 매핑하는 인덱스를 만들어요.
• 검색 (Search): 최근접 이웃을 검색할 때 검색 알고리즘이 쿼리 벡터와 클러스터 중심을 비교해 가장 유망한 클러스터를 선택해요. 그다음 선택된 클러스터 안의 벡터들로 검색 범위를 좁혀요.

기술적 세부 사항은 IVF_FLAT을 참고하세요.

SQ8

Scalar Quantization (SQ)은 고차원 벡터의 값을 더 작고 컴팩트한 표현으로 대체해 크기를 줄이는 기법이에요. SQ8 변형은 각 차원 값을 저장할 때 일반적인 32비트 부동소수점 대신 8비트 정수를 사용해요. 이렇게 하면 데이터 저장에 필요한 메모리 양이 크게 줄어들어요.

SQ8 동작 방식은 다음과 같아요:

• 범위 파악 (Range Identification): 먼저 벡터 안의 최솟값과 최댓값을 찾아요. 이 범위가 양자화의 경계를 정의해요.

• 정규화 (Normalization): 다음 공식으로 벡터 값을 0과 1 사이 범위로 정규화해요:

  normalized_value = (value - min) / (max - min)

  이렇게 하면 모든 값이 표준화된 범위 안에 비례적으로 매핑되어 압축 준비가 돼요.

• 8비트 압축 (8-Bit Compression): 정규화된 값에 255(8비트 정수의 최댓값)를 곱하고 가장 가까운 정수로 반올림해요. 이렇게 각 값을 8비트 표현으로 효과적으로 압축해요.

예를 들어 차원 값이 1.2이고 최솟값이 -1.7, 최댓값이 2.3이라고 해 볼게요. 아래 그림은 SQ8이 float32 값을 int8 정수로 변환하는 방식을 보여줘요.

IVF + SQ8

IVF_SQ8 인덱스는 IVF와 SQ8을 결합해 유사도 검색을 효율적으로 수행해요:

• IVF가 검색 범위를 좁혀요: 데이터셋이 클러스터로 나뉘고, 쿼리가 들어오면 IVF가 먼저 쿼리를 클러스터 중심과 비교해 가장 관련 있는 클러스터를 선택해요.
• SQ8이 거리 계산을 빠르게 해요: 선택된 클러스터 안에서 SQ8이 벡터를 8비트 정수로 압축해 메모리 사용을 줄이고 거리 계산을 가속화해요.

IVF로 검색 범위를 좁히고 SQ8으로 계산을 빠르게 함으로써, IVF_SQ8은 빠른 검색 시간과 메모리 효율을 모두 얻어요.

인덱스 만들기 (Build index)

Milvus에서 벡터 필드에 IVF_SQ8 인덱스를 만들려면 add_index() 메서드를 사용해 index_type, metric_type, 그리고 인덱스의 추가 파라미터를 지정해요.

from pymilvus import MilvusClient

# Prepare index building params
index_params = MilvusClient.prepare_index_params()

index_params.add_index(
    field_name="your_vector_field_name", # Name of the vector field to be indexed
    index_type="IVF_SQ8", # Type of the index to create
    index_name="vector_index", # Name of the index to create
    metric_type="L2", # Metric type used to measure similarity
    params={
        "nlist": 64, # Number of clusters to create using the k-means algorithm during index building
    } # Index building params
)

이 구성에서:

• index_type: 만들 인덱스의 타입이에요. 여기서는 IVF_SQ8로 설정해요.
• metric_type: 벡터 사이의 거리를 계산하는 방식이에요. COSINE, L2, IP 값을 지원해요. 자세한 내용은 Metric Types를 참고하세요.
• params: 인덱스를 만들 때의 추가 구성 옵션이에요.

nlist: 인덱스 구축 중 k-means 알고리즘으로 만들 클러스터 수예요.

IVF_SQ8 인덱스에서 사용할 수 있는 다른 구축 파라미터는 Index building params를 참고하세요.

인덱스 파라미터를 구성한 뒤에는 create_index() 메서드를 직접 쓰거나 create_collection 메서드에 인덱스 파라미터를 넘겨 인덱스를 만들 수 있어요. 자세한 내용은 Create Collection을 참고하세요.

인덱스에서 검색하기 (Search on index)

인덱스를 만들고 엔터티를 삽입하면 인덱스에서 유사도 검색을 수행할 수 있어요.

search_params = {
    "params": {
        "nprobe": 8, # Number of clusters to search for candidates
    }
}

res = MilvusClient.search(
    collection_name="your_collection_name", # Collection name
    anns_field="vector_field", # Vector field name
    data=[[0.1, 0.2, 0.3, 0.4, 0.5]],  # Query vector
    limit=10,  # TopK results to return
    search_params=search_params
)

이 구성에서:

• params: 인덱스에서 검색할 때의 추가 구성 옵션이에요.

nprobe: 후보를 검색할 클러스터 수예요.

IVF_SQ8 인덱스에서 사용할 수 있는 검색 파라미터는 Index-specific search params를 참고하세요.

인덱스 파라미터 (Index params)

이 섹션은 인덱스를 만들고 검색할 때 사용하는 파라미터를 정리한 개요예요.

인덱스 구축 파라미터 (Index building params)

인덱스를 만들 때 params에서 설정할 수 있는 파라미터는 다음과 같아요.

인덱스별 검색 파라미터 (Index-specific search params)

인덱스에서 검색할 때 search_params.params에서 설정할 수 있는 파라미터는 다음과 같아요.

더 알아보기 (Learn more)

• IVF_FLAT — IVF 기술 세부 사항
• Metric Types — 지원되는 거리 메트릭
• Create Collection — 컬렉션 생성 흐름