HNSW_PRQ

HNSW_PRQ는 계층적 탐색 가능한 작은 세계(HNSW) 그래프와 제품 잔여 정량화(PRQ)를 활용하여 인덱스 크기와 정확도 사이의 균형을 미세하게 조정할 수 있는 고급 벡터 인덱싱 방법을 제공합니다. PRQ는 추가 정보를 캡처하기 위해 잔여 정량화(RQ) 단계를 도입함으로써 기존의 제품 정량화(PQ)를 뛰어넘어 순수 PQ 기반 방식에 비해 정확도가 더 높거나 인덱스가 더 콤팩트해집니다. 그러나 추가 단계로 인해 인덱스 구축 및 검색 시 계산 오버헤드가 높아질 수 있습니다.

개요

HNSW_PRQ는 두 가지 색인 기술을 결합합니다: 빠른 그래프 기반 탐색을 위한 HSNW와 효율적인 벡터 압축을 위한 PRQ입니다.

HNSW

HNSW는 각 노드가 데이터 세트의 벡터에 해당하는 다층 그래프를 구성합니다. 이 그래프에서 노드는 유사성에 따라 연결되므로 데이터 공간을 빠르게 탐색할 수 있습니다. 계층적 구조를 통해 검색 알고리즘이 후보 이웃을 좁힐 수 있으므로 고차원 공간에서 검색 프로세스를 크게 가속화할 수 있습니다.

자세한 내용은 HNSW를 참조하세요.

PRQ

PRQ는 두 가지 상호 보완적인 기술을 결합한 다단계 벡터 압축 방식입니다: PQ와 RQ입니다. 먼저 고차원 벡터를 더 작은 하위 벡터로 분할한 다음(PQ를 통해) 나머지 차이를 정량화(RQ를 통해)함으로써 PRQ는 원본 데이터를 간결하면서도 정확하게 표현합니다.

다음 그림은 그 작동 방식을 보여줍니다.

Hnsw Prq

1. 제품 정량화(PQ)

   이 단계에서는 원본 벡터를 더 작은 하위 벡터로 나누고 각 하위 벡터를 학습된 코드북에서 가장 가까운 중심점에 매핑합니다. 이 매핑은 데이터 크기를 크게 줄이지만 각 하위 벡터가 단일 중심점으로 근사화되기 때문에 약간의 반올림 오류가 발생합니다. 자세한 내용은 IVF_PQ를 참조하세요.

2. 잔여 정량화(RQ)

   PQ 단계 이후, RQ는 추가 코드북을 사용하여 잔차(원본 벡터와 PQ 기반 근사치 사이의 차이)를 정량화합니다. 이 잔차는 일반적으로 훨씬 작기 때문에 저장 공간을 크게 늘리지 않고도 더 정밀하게 인코딩할 수 있습니다.

   nrq 매개변수는 이 잔차를 반복적으로 정량화할 횟수를 결정하여 압축 효율과 정확도 간의 균형을 미세 조정할 수 있습니다.

3. 최종 압축 표현

   RQ가 잔차의 정량화를 완료하면 PQ와 RQ의 정수 코드가 하나의 압축된 인덱스로 결합됩니다. RQ는 PQ만으로는 놓칠 수 있는 세밀한 디테일을 캡처함으로써 저장 공간을 크게 늘리지 않고도 정확도를 향상시킵니다. PQ와 RQ 간의 이러한 시너지가 바로 PRQ를 정의합니다.

HNSW + PRQ

HNSW와 PRQ를 결합한 HNSW_PRQ는 HNSW의 빠른 그래프 기반 검색을 유지하면서 PRQ의 다단계 압축을 활용합니다. 워크플로는 다음과 같습니다:

1. 데이터 압축: 각 벡터는 먼저 PQ를 통해 거친 표현으로 변환된 다음, 추가 세분화를 위해 RQ를 통해 잔여값을 정량화합니다. 그 결과 각 벡터를 나타내는 간결한 코드 세트가 생성됩니다.

2. 그래프 구성: 압축된 벡터(PQ 및 RQ 코드 모두 포함)는 HNSW 그래프를 구축하기 위한 기초를 형성합니다. 데이터가 압축된 형태로 저장되기 때문에 그래프에 필요한 메모리가 줄어들고 그래프 탐색 속도가 빨라집니다.

3. 후보 검색: 검색 중에 HNSW는 압축된 표현을 사용해 그래프를 탐색하고 후보 풀을 검색합니다. 이를 통해 고려해야 할 벡터의 수를 크게 줄일 수 있습니다.

4. (선택 사항) 결과 구체화: 다음 매개변수를 기반으로 초기 후보 결과를 세분화하여 정확도를 높일 수 있습니다:

   • refine: 이 세분화 단계의 활성화 여부를 제어합니다. true 로 설정하면 시스템은 더 정밀한 표현 또는 압축되지 않은 표현을 사용하여 거리를 다시 계산합니다.

   • refine_type: 세분화 중에 사용되는 데이터의 정밀도 수준을 지정합니다(예: SQ6, SQ8, BF16). FP32 와 같이 정밀도가 높을수록 더 정확한 결과를 얻을 수 있지만 더 많은 메모리가 필요합니다. 이는 원본 압축 데이터의 정밀도를 sq_type.

   • refine_k: 배율 인자로 작용합니다. 예를 들어 상위 k가 100이고 refine_k 이 2인 경우 시스템은 상위 200개 후보의 순위를 다시 매기고 가장 좋은 100개를 반환하여 전반적인 정확도를 높입니다.

전체 매개변수 목록과 유효한 값은 색인 매개변수를 참조하세요.

색인 만들기

Milvus의 벡터 필드에 HNSW_PRQ 인덱스를 구축하려면 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="HNSW_PRQ", # 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": 30, # Maximum number of neighbors each node can connect to in the graph
        "efConstruction": 360, # Number of candidate neighbors considered for connection during index construction
        "m": 384, 
        "nbits": 8,
        "nrq": 1,
        "refine": true, # Whether to enable the refinement step
        "refine_type": "SQ8" # Precision level of data used for refinement
    } # Index building params
)

이 구성에서는

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

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

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

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

인덱스에서 검색

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

search_params = {
    "params": {
        "ef": 10, # Parameter controlling query time/accuracy trade-off
        "refine_k": 1 # The 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 에서 구성할 수 있는 매개변수가 나열되어 있습니다.

	파라미터	설명	값 범위	조정 제안
HNSW	M	나가는 에지와 들어오는 에지를 모두 포함하여 그래프에서 각 노드가 가질 수 있는 최대 연결(또는 에지) 수입니다. 이 매개변수는 인덱스 구성과 검색 모두에 직접적인 영향을 줍니다.	유형: 정수 범위: [2, 2048] 기본값: 30 (노드당 최대 30개의 나가는 에지와 30개의 들어오는 에지)	M 이 클수록 일반적으로 정확도는 높아지지만 메모리 오버헤드가 증가하고 인덱스 구축과 검색 속도가 모두 느려집니다. 차원이 높거나 높은 리콜이 중요한 데이터 세트의 경우 M 을 늘리는 것을 고려하세요. 메모리 사용량과 검색 속도가 주요 관심사인 경우 M 을 줄이는 것을 고려하세요. 대부분의 경우, 이 범위 내에서 값을 설정하는 것이 좋습니다: [5, 100].
	efConstruction	인덱스 구성 중에 연결을 위해 고려되는 후보 이웃의 수. 새 요소마다 더 많은 후보 풀이 평가되지만 실제로 설정되는 최대 연결 수는 여전히 M 으로 제한됩니다.	유형: 정수 범위: [1, int_max] 기본값입니다: 360	efConstruction 이 높을수록 일반적으로 더 많은 잠재적 연결이 탐색되므로 더 정확한 인덱스가 생성됩니다. 하지만 색인 시간이 길어지고 색인 구축 중 메모리 사용량이 증가 합니다. 특히 색인 시간이 덜 중요한 시나리오에서는 정확도를 높이려면 efConstruction 을 늘리는 것이 좋습니다. 리소스 제약이 우려되는 경우 인덱스 구축 속도를 높이려면 efConstruction 을 줄이는 것을 고려하세요. 대부분의 경우 이 범위 내에서 값을 설정하는 것이 좋습니다: [50, 500].
PRQ	m	양자화 프로세스 중에 각 고차원 벡터를 나눌 하위 벡터(양자화에 사용)의 수입니다.	유형: 정수 범위: [1, 65536] 기본값입니다: None	m 값이 클수록 정확도가 향상될 수 있지만 계산 복잡성과 메모리 사용량이 증가합니다. m 은 적절한 분해를 보장하기 위해 벡터 차원(D)의 제수여야 합니다. 일반적으로 권장되는 값은 m = D/2입니다. 대부분의 경우 이 범위 내에서 값을 설정하는 것이 좋습니다: [D/8, D].
	nbits	각 하위 벡터의 중심 인덱스를 압축된 형태로 표현하는 데 사용되는 비트 수입니다. 각 코드북의 크기를 직접 결정합니다. 각 코드북에는 2n비트의 중심이 포함됩니다. 예를 들어 nbits 을 8로 설정하면 각 하위 벡터는 8비트 중심 인덱스로 표시됩니다. 따라서 해당 하위 벡터에 대해 코드북에28개 (256개)의 가능한 중심이 허용됩니다.	유형: 정수 범위: [1, 24] 기본값입니다: 8	nbits 값이 클수록 코드북의 크기가 커져 원본 벡터를 더 정확하게 표현할 수 있습니다. 하지만 각 인덱스를 저장하는 데 더 많은 비트를 사용하므로 압축률이 떨어집니다. 대부분의 경우 이 범위 내에서 값을 설정하는 것이 좋습니다: [1, 16].
	nrq	RQ 단계에서 사용되는 잔여 서브퀀티저의 수를 제어합니다. 서브퀀타이저가 많을수록 압축률이 높아지지만 정보 손실이 더 많이 발생할 수 있습니다.	유형: 정수 범위: [1, 16] 기본값입니다: 2	nrq 값이 클수록 잔여 하위 양자화 단계가 추가되어 원본 벡터를 더 정밀하게 재구성할 수 있습니다. 하지만 더 많은 서브퀀타이저를 저장하고 계산해야 하므로 인덱스 크기가 커지고 계산 오버헤드가 커집니다.
	refine	검색 중에 세분화 단계를 적용할지 여부를 제어하는 부울 플래그입니다. 세분화에는 쿼리 벡터와 후보 사이의 정확한 거리를 계산하여 초기 결과의 순위를 다시 매기는 작업이 포함됩니다.	유형: 부울 범위: [true, false] 기본값입니다: false	높은 정확도가 필수적이며 약간 느린 검색 시간을 용인할 수 있는 경우 true 로 설정합니다. 속도가 우선이고 약간의 정확도 저하를 감수할 수 있는 경우 false 을 사용합니다.
	refine_type	세분화 과정에서 사용되는 데이터의 정밀도를 결정합니다. 이 정밀도는 압축 벡터( m 및 nbits 매개변수에 의해 설정된 대로)보다 높아야 합니다.	Type: 문자열 범위:[ SQ6, SQ8, BF16, FP16, FP32 ]입니다. 기본값: None	더 높은 메모리 비용으로 정밀도를 최대화하려면 FP32, 더 나은 압축을 위해서는 SQ6/SQ8 을 사용하세요. BF16 과 FP16 은 균형 잡힌 대안을 제공합니다.

인덱스별 검색 매개변수

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

	파라미터	설명	값 범위	조정 제안
HNSW	ef	가장 가까운 이웃을 검색하는 동안 검색 범위를 제어합니다. 얼마나 많은 노드를 방문하고 잠재적인 가장 가까운 이웃으로 평가할지 결정합니다. 이 매개변수는 검색 프로세스에만 영향을 미치며 그래프의 맨 아래 레이어에만 적용됩니다.	유형: 정수 범위: [1, int_max] 기본값: limit (반환할 가장 가까운 이웃 TopK)	ef 이 클수록 일반적으로 더 많은 잠재적 이웃을 고려하므로 검색 정확도가 높아 집니다. 그러나 검색 시간도 증가합니다. 높은 회상률을 달성하는 것이 중요하고 검색 속도가 덜 중요한 경우에는 ef 을 늘리는 것이 좋습니다. 특히 약간의 정확도 감소를 감수할 수 있는 시나리오에서는 ef 을 줄여 검색 속도를 우선시하는 것이 좋습니다. 대부분의 경우 이 범위 내에서 값을 설정하는 것이 좋습니다: [K, 10K].
PRQ	refine_k	요청된 상위 K 결과와 비교하여 구체화(순위 재조정) 단계에서 추가로 검토할 후보자 수를 제어하는 배율입니다.	유형: 실수 범위: [1, float_max) 기본값: 1	refine_k 값이 클수록 검색 회수율과 정확도가 향상되지만 검색 시간과 리소스 사용량도 증가합니다. 값이 1이면 구체화 프로세스에서 초기 상위 K 결과만 고려한다는 의미입니다.