ANN 알고리즘이란? HNSW, IVF, PQ, DiskANN

ANN 알고리즘 

Approximate Nearest Neighbor 근사 최근접 이웃

일반적인 검색이 벡터 100, 000개를 모두 비교해 정확하지만 시간이 오래걸린다면, 

ANN검색은 가까울 가능성이 높은 후보만 선택해 후보끼리만 비교해 가장 가까운 벡터를 선택해 빠르게 탐색한다.약간의 오차를 동반한다.

대표적인 ANN 인덱스 알고리즘에는 HNSW, IVF, PQ, DiskANN이 된다 .

HNSW, IVF, PQ, DiskANN은 직접 구현해서 사용하는 알고리즘이 아니라, Vector DB나 FAISS가 내부적으로 사용하는 인덱스(Index) 구조. 개발자는 "어떤 인덱스를 사용할지"만 선택하면 되고, 실제 그래프 생성이나 클러스터 분할은 라이브러리가 자동으로 수행한다.

 

 

 - HNSW(Hierarchical Navigable Small World): 그래프 기반으로 매우 빠른 검색을 제공하며, Chroma·Qdrant·Weaviate 등에서 널리 사용된다.

import faiss
import numpy as np

dimension = 768

# HNSW 인덱스 생성
index = faiss.IndexHNSWFlat(dimension, 32)

# 문서 벡터
vectors = np.random.rand(10000, dimension).astype("float32")

# 저장
index.add(vectors)

# 질문 벡터
query = np.random.rand(1, dimension).astype("float32")

# Top5 검색
distance, ids = index.search(query, 5)

print(ids)

 

 -  IVF(Inverted File Index): 벡터를 여러 클러스터로 나눈 뒤 관련 클러스터만 검색한다. FAISS에서 많이 사용된다.

import faiss
import numpy as np

dimension = 768

quantizer = faiss.IndexFlatL2(dimension)

# 100개의 클러스터
index = faiss.IndexIVFFlat(
    quantizer,
    dimension,
    100
)

vectors = np.random.rand(10000, dimension).astype("float32")

# 먼저 학습
index.train(vectors)

# 저장
index.add(vectors)

query = np.random.rand(1, dimension).astype("float32")

distance, ids = index.search(query, 5)

print(ids)

 

 -  PQ(Product Quantization): 벡터를 압축해 메모리를 크게 절약하며 초대규모 데이터셋에 적합하다.

dimension = 768

index = faiss.IndexPQ(
    dimension,
    64,
    8
)

vectors = np.random.rand(10000, dimension).astype("float32")

index.train(vectors)

index.add(vectors)

query = np.random.rand(1, dimension).astype("float32")

distance, ids = index.search(query, 5)

print(ids)

 -  DiskANN: SSD를 활용해 디스크 기반에서도 빠른 검색을 지원한다.

개발자가 일반적으로 직접 DiskANN 클래스를 사용하는 경우는 드물며, 해당 기능을 지원하는 데이터베이스나 검색 엔진이 내부적으로 활용한다