HNSW

HNSW 인덱스는 고차원 부동 벡터를 검색할 때 성능을 향상시킬 수 있는 그래프 기반 인덱싱 알고리즘입니다. 뛰어난 검색 정확도와 짧은 지연 시간을 제공하는 반면, 계층적 그래프 구조를 유지하기 위해 높은 메모리 오버헤드를 필요로 합니다.

개요

계층적 탐색 가능한 작은 세계(HNSW) 알고리즘은 줌 레벨이 다른 지도와 같은 다층 그래프를 구축합니다. 하단 레이어에는 모든 데이터 포인트가 포함되며, 상위 레이어는 하단 레이어에서 샘플링된 데이터 포인트의 하위 집합으로 구성됩니다.

이 계층 구조에서 각 계층은 데이터 포인트를 나타내는 노드를 포함하며, 각 노드는 근접성을 나타내는 가장자리로 연결됩니다. 상위 레이어는 대상에 빠르게 근접할 수 있는 장거리 점프를 제공하고, 하위 레이어는 가장 정확한 결과를 얻기 위한 세분화된 검색을 가능하게 합니다.

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

1. 진입 지점: 검색은 그래프에서 미리 결정된 노드인 최상위 레이어의 고정된 진입점에서 시작됩니다.
2. 탐욕스러운 검색: 알고리즘은 쿼리 벡터에 더 이상 가까워질 수 없을 때까지 현재 레이어에서 가장 가까운 이웃으로 욕심스럽게 이동합니다. 상위 레이어는 탐색 목적으로 사용되며, 하위 레이어에서 더 세밀한 검색을 위한 잠재적 진입점을 찾기 위한 거친 필터 역할을 합니다.
3. 레이어 하강: 현재 레이어에서 로컬 최소값에 도달하면 알고리즘은 미리 설정된 연결을 사용하여 하위 레이어로 점프 다운하여 탐욕스러운 검색을 반복합니다.
4. 최종 다듬기: 이 프로세스는 최하위 레이어에 도달할 때까지 계속되며, 최종 세분화 단계에서는 가장 가까운 이웃을 식별합니다.

HNSW

HNSW의 성능은 그래프의 구조와 검색 동작을 모두 제어하는 몇 가지 주요 매개변수에 따라 달라집니다. 여기에는 다음이 포함됩니다:

• M: 계층 구조의 각 수준에서 각 노드가 그래프에서 가질 수 있는 최대 에지 또는 연결 수입니다. M 이 높을수록 그래프가 더 조밀해지고 검색에 탐색할 경로가 많아져 리콜과 정확도가 높아지지만, 추가 연결로 인해 메모리가 더 많이 소모되고 삽입 시간이 느려집니다. 위 이미지에서 볼 수 있듯이 M = 5는 HNSW 그래프의 각 노드가 최대 5개의 다른 노드에 직접 연결되어 있음을 나타냅니다. 이렇게 하면 노드가 다른 노드에 도달할 수 있는 경로가 여러 개 있는 적당한 밀도의 그래프 구조가 만들어집니다.
• efConstruction: 인덱스 구성 중에 고려되는 후보의 수입니다. efConstruction 이 높을수록 일반적으로 그래프 품질이 더 좋아지지만 구축하는 데 더 많은 시간이 필요합니다.
• ef: 검색 중에 평가되는 이웃의 수입니다. ef 을 늘리면 가장 가까운 이웃을 찾을 가능성은 높아지지만 검색 프로세스가 느려집니다.

필요에 맞게 이러한 설정을 조정하는 방법에 대한 자세한 내용은 색인 매개변수를 참조하세요.

색인 만들기

Milvus의 벡터 필드에 HNSW 인덱스를 구축하려면 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", # 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": 64, # Maximum number of neighbors each node can connect to in the graph
        "efConstruction": 100 # Number of candidate neighbors considered for connection during index construction
    } # Index building params
)

이 구성에서는

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

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

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

  • M: 각 노드가 연결할 수 있는 최대 이웃 수입니다.
  • efConstruction: 인덱스 구축 시 연결을 위해 고려되는 후보 이웃의 수입니다.

  HNSW 인덱스에 사용할 수 있는 더 많은 구축 파라미터에 대해 알아보려면 인덱스 구축 파라미터를 참조하세요.

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

인덱스에서 검색

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

search_params = {
    "params": {
        "ef": 10, # Number of neighbors to consider during the 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=10,  # TopK results to return
    search_params=search_params
)

이 구성에서는

• params: 색인에서 검색을 위한 추가 구성 옵션.

  • ef: 검색 시 고려할 이웃의 수입니다.

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

색인 매개변수

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

인덱스 구축 매개변수

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

파라미터	설명	값 범위	조정 제안
M	나가는 에지와 들어오는 에지를 모두 포함하여 각 노드가 그래프에서 가질 수 있는 최대 연결(또는 에지) 수입니다. 이 매개변수는 인덱스 구성과 검색 모두에 직접적인 영향을 줍니다.	유형: 정수 범위: [2, 2048] 기본값: 30 (노드당 최대 30개의 나가는 에지와 30개의 들어오는 에지)	M 값이 클수록 일반적으로 정확도는 높아지지만 메모리 오버헤드가 증가하고 인덱스 구축과 검색 속도가 느려집니다. 차원이 높은 데이터 세트나 높은 리콜이 중요한 경우 M 값을 늘리는 것을 고려하세요. 메모리 사용량과 검색 속도가 주요 관심사인 경우 M 을 낮추는 것이 좋습니다. 대부분의 경우, 이 범위 내에서 값을 설정하는 것이 좋습니다: [5, 100].
efConstruction	인덱스 구성 중에 연결을 위해 고려되는 후보 이웃의 수입니다. 새 요소마다 더 많은 후보 풀이 평가되지만 실제로 설정되는 최대 연결 수는 여전히 M 으로 제한됩니다.	유형: 유형: 정수 범위: [1, int_max] 기본값입니다: 360	efConstruction 이 높을수록 일반적으로 더 많은 잠재적 연결이 탐색되므로 더 정확한 인덱스가 생성됩니다. 그러나 이 경우 인덱싱 시간이 길어지고 구성 중에 메모리 사용량이 증가합니다. 특히 인덱싱 시간이 덜 중요한 시나리오에서는 정확도를 높이려면 efConstruction 을 늘리는 것이 좋습니다. 리소스 제약이 우려되는 경우 인덱스 구축 속도를 높이려면 efConstruction 을 줄이는 것을 고려하세요. 대부분의 경우 이 범위 내에서 값을 설정하는 것이 좋습니다: [50, 500].

인덱스별 검색 매개변수

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

파라미터	설명	값 범위	조정 제안
ef	가장 가까운 이웃 검색 중 검색 범위를 제어합니다. 얼마나 많은 노드를 방문하고 잠재적인 가장 가까운 이웃으로 평가할지 결정합니다. 이 매개변수는 검색 프로세스에만 영향을 미치며 그래프의 맨 아래 레이어에만 적용됩니다.	유형: 정수 범위: [1, int_max] 기본값: limit (반환할 가장 가까운 이웃 TopK)	ef 이 클수록 일반적으로 더 많은 잠재적 이웃을 고려하므로 검색 정확도가 높아 집니다. 그러나 검색 시간도 늘어납니다. 높은 회상률을 달성하는 것이 중요하고 검색 속도는 크게 신경 쓰지 않는 경우 ef 을 늘리는 것을 고려하세요. 특히 약간의 정확도 감소를 감수할 수 있는 시나리오에서는 ef 을 줄여 검색 속도를 우선시하는 것이 좋습니다. 대부분의 경우 이 범위 내에서 값을 설정하는 것이 좋습니다: [K, 10K].