IVF_PQ

IVF_PQ 인덱스는 고차원 공간에서 대략적인 최접근 이웃 검색을 위한 양자화 기반 인덱싱 알고리즘입니다. 일부 그래프 기반 방법만큼 빠르지는 않지만 IVF_PQ는 메모리를 훨씬 적게 필요로 하므로 대규모 데이터 세트에 실용적인 선택입니다.

개요

IVF_PQ는 효율적인 벡터 검색과 검색을 위해 인덱싱과 압축을 결합한 하이브리드 접근 방식인 역파일과 제품 정량화의 약자입니다. 이는 두 가지 핵심 구성 요소를 활용합니다: 반전 파일(IVF) 과 제품 정량화(PQ)입니다.

IVF

IVF는 책에 색인을 만드는 것과 같습니다. 모든 페이지(이 경우에는 모든 벡터)를 스캔하는 대신 색인에서 특정 키워드(클러스터)를 조회하여 관련 페이지(벡터)를 빠르게 찾습니다. 이 시나리오에서는 벡터가 클러스터로 그룹화되고 알고리즘이 쿼리 벡터에 가까운 몇 개의 클러스터 내에서 검색합니다.

작동 방식은 다음과 같습니다:

1. 클러스터링: 벡터 데이터 세트는 k-평균과 같은 클러스터링 알고리즘을 사용하여 지정된 수의 클러스터로 나뉩니다. 각 클러스터에는 중심(클러스터의 대표 벡터)이 있습니다.
2. 할당: 각 벡터는 중심이 가장 가까운 클러스터에 할당됩니다.
3. 반전 인덱스: 각 클러스터 중심을 해당 클러스터에 할당된 벡터 목록에 매핑하는 인덱스가 생성됩니다.
4. 검색: 가장 가까운 이웃을 검색할 때 검색 알고리즘이 쿼리 벡터와 클러스터 중심을 비교하여 가장 가능성이 높은 클러스터를 선택합니다. 그런 다음 선택한 클러스터 내의 벡터로 검색 범위가 좁혀집니다.

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

PQ

제품 정량화(PQ) 는 고차원 벡터를 위한 압축 방법으로, 유사도 검색 작업을 빠르게 수행하면서 스토리지 요구 사항을 크게 줄여줍니다.

PQ 프로세스에는 다음과 같은 주요 단계가 포함됩니다:

PQ 프로세스-1

1. 차원 분해: 이 알고리즘은 각 고차원 벡터를 m 동일한 크기의 하위 벡터로 분해하는 것으로 시작됩니다. 이 분해는 원래의 D 차원 공간을 m 분리된 하위 공간으로 변환하며, 각 하위 공간은 D/m 차원을 포함합니다. m 매개변수는 분해의 세분성을 제어하며 압축률에 직접적인 영향을 줍니다.
2. 서브스페이스 코드북 생성: 각 하위 공간 내에서 알고리즘은 K-평균 클러스터링을 적용하여 대표 벡터(중심) 집합을 학습합니다. 이러한 중심은 집합적으로 해당 하위 공간에 대한 코드북을 형성합니다. 각 코드북의 중심 수는 매개변수 nbits 에 의해 결정되며, 각 코드북에는 2^n비트 중심이 포함됩니다. 예를 들어 nbits = 8 인 경우 각 코드북에는 256개의 중심이 포함됩니다. 각 중심에는 nbits 비트의 고유 인덱스가 할당됩니다.
3. 벡터 양자화: 원본 벡터의 각 하위 벡터에 대해 PQ는 특정 메트릭 유형을 사용하여 해당 하위 공간 내에서 가장 가까운 중심을 식별합니다. 이 프로세스는 각 하위 벡터를 코드북에서 가장 가까운 대표 벡터에 효과적으로 매핑합니다. 전체 하위 벡터 좌표를 저장하는 대신 일치하는 중심점의 인덱스만 유지됩니다.
4. 압축 표현: 최종 압축 표현은 각 하위 공간에서 하나씩, 총칭하여 PQ 코드라고 하는 m 인덱스로 구성됩니다. 이 인코딩은 저장 요구 사항을 D × 32비트 (32비트 부동소수점 숫자 가정)에서 m × n비트 비트로 줄여 벡터 거리를 근사화하는 기능을 유지하면서 상당한 압축을 달성합니다.

매개변수 조정 및 최적화에 대한 자세한 내용은 색인 매개변수를 참조하세요.

PQ를 사용한 거리 계산

쿼리 벡터로 유사도 검색을 수행할 때 PQ는 다음 단계를 통해 효율적인 거리 계산을 가능하게 합니다:

1. 쿼리 전처리

   1. 쿼리 벡터는 원래의 PQ 분해 구조와 일치하는 m 하위 벡터로 분해됩니다.
   2. 각 쿼리 하위 벡터와 해당 코드북(2^n비트 중심 포함)에 대해 모든 중심까지의 거리를 계산하고 저장합니다.
   3. 이렇게 하면 m 조회 테이블이 생성되며, 각 테이블에는 2^n비트 거리가 포함됩니다.

2. 거리 근사치

   PQ 코드로 표시되는 모든 데이터베이스 벡터의 경우 쿼리 벡터와의 대략적인 거리는 다음과 같이 계산됩니다:

   1. 각 m 하위 벡터에 대해 저장된 중심 인덱스를 사용하여 해당 조회 테이블에서 미리 계산된 거리를 검색합니다.
   2. 이러한 m 거리를 합산하여 특정 메트릭 유형(예: 유클리드 거리)에 따른 대략적인 거리를 구합니다.

pq-process-1

IVF + PQ

IVF_PQ 인덱스는 검색 속도를 높이기 위해 IVF와 PQ의 강점을 결합한 인덱스입니다. 이 프로세스는 두 단계로 작동합니다:

1. IVF를사용한 거친 필터링: IVF는 벡터 공간을 클러스터로 분할하여 검색 범위를 줄입니다. 이 알고리즘은 전체 데이터 세트를 평가하는 대신 쿼리 벡터에 가장 가까운 클러스터에만 집중합니다.
2. PQ와의 세분화된 비교: 선택한 클러스터 내에서 PQ는 압축 및 양자화된 벡터 표현을 사용해 대략적인 거리를 빠르게 계산합니다.

IVF_PQ 인덱스의 성능은 IVF와 PQ 알고리즘을 모두 제어하는 매개변수에 의해 크게 영향을 받습니다. 주어진 데이터 세트와 애플리케이션에 대해 최적의 결과를 얻으려면 이러한 매개변수를 조정하는 것이 중요합니다. 이러한 매개변수에 대한 자세한 정보와 조정 방법은 인덱스 매개변수에서 확인할 수 있습니다.

인덱스 구축

Milvus의 벡터 필드에 IVF_PQ 인덱스를 구축하려면 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_PQ", # 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={
        "m": 4, # Number of sub-vectors to split eahc vector into
    } # Index building params
)

이 구성에서는

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

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

• params: 인덱스 구축을 위한 추가 구성 옵션입니다.

  • m: 벡터를 분할할 하위 벡터의 수입니다.

  IVF_PQ 인덱스에 사용할 수 있는 구축 매개변수에 대해 자세히 알아보려면 인덱스 구축 매개변수를 참조하세요.

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

인덱스에서 검색

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

search_params = {
    "params": {
        "nprobe": 10, # Number of clusters to search
    }
}

res = MilvusClient.search(
    collection_name="your_collection_name", # Collection 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: 색인에서 검색을 위한 추가 구성 옵션.

  • nprobe: 검색할 클러스터 수입니다.

  IVF_PQ 인덱스에 사용할 수 있는 검색 매개변수에 대해 자세히 알아보려면 인덱스별 검색 매개변수를 참조하세요.

인덱스 매개변수

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

인덱스 구축 매개변수

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

	파라미터	설명	값 범위	조정 제안
IVF	nlist	인덱스 구축 중에 k-평균 알고리즘을 사용하여 생성할 클러스터의 수입니다.	유형: 정수 범위: [1, 65536] 기본값입니다: 128	nlist 값이 클수록 더 세분화된 클러스터를 생성하여 회상률이 향상되지만 인덱스 구축 시간이 늘어납니다. 데이터 세트 크기와 사용 가능한 리소스에 따라 최적화하세요. 대부분의 경우 이 범위 내에서 값을 설정하는 것이 좋습니다: [32, 4096].
PQ	m	양자화 프로세스 중에 각 고차원 벡터를 나눌 하위 벡터(양자화에 사용)의 수입니다.	유형: 정수 범위: [1, 65536] 기본값입니다: None	m 값이 클수록 정확도가 향상될 수 있지만 계산 복잡성과 메모리 사용량도 증가합니다. m 는 적절한 분해를 보장하기 위해 벡터 차원(D)의 제수여야 합니다. 일반적으로 권장되는 값은 m = D/2입니다. 대부분의 경우 이 범위 내에서 값을 설정하는 것이 좋습니다: [D/8, D].
	nbits	각 하위 벡터의 중심 인덱스를 압축된 형태로 표현하는 데 사용되는 비트 수입니다. 각 코드북의 크기를 직접 결정하며, 각 코드북에는 2^n비트의 중심이 포함됩니다. 예를 들어 nbits 을 8로 설정하면 각 하위 벡터는 8비트 중심 인덱스로 표시됩니다. 따라서 해당 하위 벡터의 코드북에는 2^8(256)개의 가능한 중심이 있습니다.	유형: 정수 범위: [1, 64] 기본값입니다: 8	nbits 값이 클수록 코드북이 커져 원본 벡터를 더 정확하게 표현할 수 있습니다. 하지만 각 인덱스를 저장하는 데 더 많은 비트를 사용하므로 압축률이 떨어집니다. 대부분의 경우 이 범위 내에서 값을 설정하는 것이 좋습니다: [1, 16].

인덱스별 검색 매개변수

다음 표에는 인덱스에서 검색할 때 search_params.params 에서 구성할 수 있는 파라미터가 나와 있습니다.

	파라미터	설명	값 범위	조정 제안
IVF	nprobe	후보를 검색할 클러스터 수입니다.	유형: 정수 범위: [1, nlist] 기본값입니다: 8	값이 클수록 더 많은 클러스터를 검색할 수 있으므로 검색 범위가 확장되어 검색 회수율이 향상되지만 쿼리 대기 시간이 늘어납니다. 속도와 정확도의 균형을 맞추려면 nprobe 을 nlist 에 비례하여 설정합니다. 대부분의 경우 이 범위 내에서 값을 설정하는 것이 좋습니다: [1, nlist].