IVF_RABITQCompatible with Milvus 2.6.x

IVF_RABITQ 인덱스는 FP32 벡터를 이진 표현으로 정량화하는 이진 양자화 기반 인덱싱 알고리즘입니다. 이 인덱스는 상대적으로 우수한 리콜률을 유지하면서 1대 32의 압축 비율로 뛰어난 저장 효율성을 제공합니다. 이 인덱스는 추가 스토리지 비용으로 더 높은 리콜을 달성하기 위한 선택적 세분화를 지원하므로 메모리가 제한된 시나리오에서 IVF_SQ8 및 IVF_FLAT을 대체할 수 있는 다용도 인덱스입니다.

개요

IVF_RABITQ는 효율적인 벡터 검색과 저장을 위해 두 가지 강력한 기술을 결합한 RaBitQ 양자화를 사용한 역파일(Inverted File)의 약자입니다.

IVF

반전 파일(IVF)은 K-평균 클러스터링을 사용하여 벡터 공간을 관리 가능한 영역으로 구성합니다. 각 클러스터는 중심점으로 표시되며, 중심점은 해당 클러스터 내의 벡터에 대한 기준점 역할을 합니다. 이 클러스터링 접근 방식은 쿼리 처리 중에 알고리즘이 가장 관련성이 높은 클러스터에만 집중할 수 있도록 하여 검색 공간을 줄여줍니다.

IVF 기술 세부 사항에 대해 자세히 알아보려면 IVF_FLAT을 참조하세요.

RaBitQ

RaBitQ는 이론적으로 보장된 최첨단 이진 양자화 방법으로, Jianyang Gao와 Cheng Long의 연구 논문 "RaBitQ: 근사 최접 이웃 검색을 위한 이론적 오차 한계를 가진 고차원 벡터 양자화"에 소개되어 있습니다.

RaBitQ는 몇 가지 혁신적인 개념을 소개합니다:

각도 정보 인코딩: 기존의 공간 인코딩과 달리, RaBitQ는 벡터 정규화를 통해 각도 정보를 인코딩합니다. IVF_RABITQ에서 데이터 벡터는 가장 가까운 IVF 중심점에 대해 정규화되어 양자화 프로세스의 정밀도를 향상시킵니다.

이론적 기반: 핵심 거리 근사화 공식은 다음과 같습니다:

$$\lVert \mathbf{o_r} - \mathbf{q_r} \rVert^2 \approx \lVert \mathbf{o_r} - \mathbf{c_o} \rVert^2 + \lVert \mathbf{q_r} - \mathbf{c_o} \rVert^2 - 2 \cdot C(\mathbf{o_r}, \mathbf{c_o}) \cdot \langle \tilde{\mathbf{o}}, \mathbf{q_r} - \mathbf{c_o} \rangle + C_1(\mathbf{o_r}, \mathbf{c_o})$$

Where:

• $or\mathbf{o_r}$ or 는 데이터 세트의 데이터 벡터입니다.
• $qr\mathbf{q_r}$ qr 는 쿼리 벡터입니다.
• $co\mathbf{c_o}$ co 는 $or\mathbf{o_r}$ o r 에 대한 가장 가까운 IVF 중심 벡터입니다.
• $C(\mathbf{o_r}, \mathbf{c_o})$ C$(\mathbf{o}$r, co ) 및 $C_1(\mathbf{o_r}, \mathbf{c_o)$ C ${}_{}(o$ r, c o ) 는 미리 계산된 상수입니다.
• $o~\tilde{\mathbf{o}}$ ~ 는 인덱스에 저장된 양자화된 이진 벡터입니다.
• $\tilde{\mathbf{o}}, \mathbf{q_r} - \mathbf{c_o}$ \$rangle$ o ~$,$ q${}_{}-$ c${}_{}⟩는$ 도트 곱 연산을 나타냅니다.

계산 효율성: $o~\tilde{\mathbf{o}}$ ~의 이진 특성으로 인해 거리 계산이 매우 빨라지며, 특히 인텔 아이스 레이크+ 또는 AMD Zen 4+ 프로세서의 전용 AVX-512 VPOPCNTDQ 명령어가 있는 최신 CPU 아키텍처의 이점을 누릴 수 있습니다.

알고리즘 개선: RaBitQ는 FastScan 접근 방식 및 랜덤 로테이션과 같은 기존 기술과 효과적으로 통합되어 성능을 향상시킵니다.

IVF + RaBitQ

IVF_RABITQ 인덱스는 IVF의 효율적인 클러스터링과 RaBitQ의 고급 바이너리 양자화를 결합합니다:

1. 거친 필터링: IVF는 벡터 공간을 클러스터로 분할하여 가장 관련성이 높은 클러스터 영역에 집중함으로써 검색 범위를 크게 줄입니다.

2. 이진 양자화: 각 클러스터 내에서 RaBitQ는 이론적 보장을 통해 필수적인 거리 관계를 보존하면서 벡터를 이진 표현으로 압축합니다.

3. 선택적 세분화: 이 옵션을 활성화하면 인덱스는 더 높은 정밀도 형식(SQ6, SQ8, FP16, BF16 또는 FP32)을 사용해 추가로 정제된 데이터를 저장하여 저장 공간을 늘리는 대신 리콜률을 향상시킵니다.

Milvus는 다음과 같은 FAISS 팩토리 스트링을 사용하여 IVF_RABITQ를 구현합니다:

• 정제 포함: "RR({dim}),IVF{nlist},RaBitQ,Refine({refine_index})"
• 정제 없음: "RR({dim}),IVF{nlist},RaBitQ"

인덱스 구축

Milvus의 벡터 필드에 IVF_RABITQ 인덱스를 구축하려면 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_RABITQ", # 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": 1024, # Number of clusters for the index
        "refine": True, # Enable refinement for higher recall
        "refine_type": "SQ8" # Refinement data format
    } # Index building params
)

이 구성에서는

• index_type: 빌드할 인덱스 유형입니다. 이 예에서는 값을 IVF_RABITQ 로 설정합니다.

• metric_type: 벡터 간의 거리를 계산하는 데 사용되는 메서드입니다. 지원되는 값은 COSINE, L2, IP 입니다. 자세한 내용은 메트릭 유형을 참조하세요.

• params: 인덱스 구축을 위한 추가 구성 옵션입니다. 자세한 내용은 인덱스 구축 파라미터를 참조하세요.

인덱스 파라미터가 구성되면 create_index() 메서드를 직접 사용하거나 create_collection 메서드에서 인덱스 파라미터를 전달하여 인덱스를 만들 수 있습니다. 자세한 내용은 컬렉션 만들기를 참조하세요.

인덱스에서 검색

인덱스가 구축되고 엔티티가 삽입되면 인덱스에서 유사도 검색을 수행할 수 있습니다.

search_params = {
    "params": {
        "nprobe": 128, # Number of clusters to search
        "rbq_query_bits": 0, # Query vector quantization bits
        "refine_k": 1 # Refinement magnification factor
    }
}

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=3, # TopK results to return
    search_params=search_params
)

이 구성에서는

• params: 인덱스에서 검색을 위한 추가 구성 옵션입니다. 자세한 내용은 인덱스별 검색 매개변수를 참조하세요.

인덱스 매개변수

이 섹션에서는 인덱스를 구축하고 인덱스에서 검색을 수행하는 데 사용되는 매개변수에 대한 개요를 제공합니다.

인덱스 구축 매개변수

다음 표에는 인덱스 구축 시 params 에서 구성할 수 있는 매개변수가 나열되어 있습니다.

	파라미터	설명	값 범위	조정 제안
IVF	nlist	인덱스 구축 중에 k-평균 알고리즘을 사용하여 생성할 클러스터의 수입니다. 중심점으로 표시되는 각 클러스터는 벡터 목록을 저장합니다. 이 매개변수를 늘리면 각 클러스터의 벡터 수가 줄어들어 더 작고 집중적인 파티션이 만들어집니다.	유형: 정수 범위: [1, 65536] 기본값입니다: 128	nlist 값이 클수록 더 세분화된 클러스터를 생성하여 회상률이 향상되지만 인덱스 구축 시간이 늘어납니다. 데이터 세트 크기와 사용 가능한 리소스에 따라 최적화하세요. 대부분의 경우 이 범위 내에서 값을 설정하는 것이 좋습니다: [32, 4096].
RaBitQ	refine	정제 프로세스를 활성화하고 정제된 데이터를 저장합니다.	유형: 부울 범위: [true, false] 기본값입니다: false	0.9 이상의 리콜률이 필요한 경우 true 로 설정합니다. 세분화를 활성화하면 정확도는 향상되지만 저장소 요구 사항과 인덱스 구축 시간이 늘어납니다.
	refine_type	refine 을 활성화할 때 세분화에 사용되는 데이터 표현을 정의합니다.	유형: 문자열 범위: [SQ6, SQ8, FP16, BF16, FP32]입니다. 기본값입니다: None	나열된 값은 정확도와 리소스 사용량 간의 균형이 잘 잡힌 SQ8 을 시작점으로 권장하며, 정확도 증가, QPS 감소, 스토리지 크기 증가 순으로 표시됩니다.

색인별 검색 매개변수

다음 표에는 색인에서 검색할 때 search_params.params 에서 구성할 수 있는 매개변수가 나열되어 있습니다.

	파라미터	설명	값 범위	조정 제안
IVF	nprobe	후보를 검색할 클러스터의 수입니다. 값이 클수록 더 많은 클러스터를 검색할 수 있으므로 검색 범위가 확장되어 회상률이 향상되지만 쿼리 대기 시간이 늘어납니다.	유형: 정수 범위: [1, nlist] 기본값입니다: 8	이 값을 높이면 검색 회수율은 향상되지만 검색 속도가 느려질 수 있습니다. 속도와 정확도의 균형을 맞추려면 nprobe 을 nlist 에 비례하여 설정하세요. 대부분의 경우 이 범위 내에서 값을 설정하는 것이 좋습니다: [1, nlist].
RaBitQ	rbq_query_bits	쿼리 벡터의 추가 스칼라 양자화 적용 여부를 설정합니다. 0 로 설정하면 쿼리가 양자화 없이 사용됩니다. 1, 8] 이내의 값으로 설정하면 쿼리가 n비트 스칼라 양자화를 사용하여 전처리됩니다.	유형: 정수 범위: [0, 8] 기본값입니다: 0	기본값인 0 값은 최대 리콜률을 제공하지만 가장 느린 성능을 제공합니다. 0 , 8, 6 값은 비슷한 리콜률을 제공하며 6 이 가장 빠르므로 테스트하는 것이 좋습니다. 리콜 요구 사항을 높이려면 더 작은 값을 사용합니다.
	refine_k	정제 프로세스는 더 높은 품질의 정량화를 사용하여 IVF_RABITQ를 사용하여 선택한 후보 풀의 refine_k 배 더 큰 풀에서 필요한 수의 가장 가까운 이웃을 선택합니다.	유형: Float 범위: [1, float_max) 기본값입니다: 1	refine_k 값이 높을수록 QPS는 감소하지만 리콜률은 증가합니다. 1 으로 시작하여 2, 3, 4, 5 값을 테스트하여 데이터 집합에 대한 QPS와 리콜 사이의 최적의 절충점을 찾으세요.