HNSW 4장 카드뉴스

벡터 검색 분야에서 쓰이는 Hierarchical Navigable Small World(계층적 탐색 가능 소세계 그래프)의 약자로, 근사 최근접 이웃(ANN) 탐색에 쓰는 그래프 인덱스입니다. 벡터를 여러 층의 근접 그래프로 쌓고 위층에서 탐색 시작점을 좁혀 내려가는 구조이며, 원 논문은 로그 수준의 복잡도 확장을 보고했습니다 [1]. 정확도와 속도의 균형은 M, efConstruction, efSearch 값으로 조절합니다 [1]. 그래프와 벡터를 메모리에 올려 두는 방식이라 메모리 사용량이 큽니다 [7].

Hierarchical Navigable Small World는 계층으로 쌓은, 오갈 수 있는 좁은 세상 그래프라는 뜻입니다. 목적지를 찾을 때 고속도로로 대략의 방향을 잡고, 국도로 내려와 범위를 줄이고, 마지막에 골목에서 집 앞에 서는 것과 같아요. 위층 그래프는 성기게 연결돼 멀리 건너뛰고, 아래층으로 갈수록 촌촌해져 정밀하게 좁힙니다. 모든 벡터를 하나씩 다 비교하지 않고도 가까운 이웃을 찾아내는 방식입니다.

케이스 1: 원 논문 — HNSW를 제안하고 기존 ANN 라이브러리와 비교한 벤치마크 2016년 3월 arXiv에 공개되고 2018년 8월 v4로 갱신된 논문입니다 [1]. SIFT 100만 건(128차원), GloVe 120만 건(100차원), CoPhIR 200만 건(272차원) 등에서 NSW, FLANN, Annoy, FALCONN, FAISS와 비교했습니다 [1].