[Vector Search] HNSW 인덱스

#데이터베이스

HNSW(Hierarchical navigable small world)는 벡터 데이터베이스의 인덱스 구현에 사용되는 대표적인 그래프 기반 데이터 구조 중 하나다.
2016년에 나왔다.

특징

다른 벡터 인덱스 구조도 마찬가지지만, 기본적으로 근사치(ANN) 검색을 위한 구조라서, 결과가 정확할 수 없다.
속도를 위해서 정확도를 희생한 구조다.
정확도는 구현체에 따라 다르지만 대체로 70~90% 정도를 오간다.

검색시의 시간복잡도는 O(log N), 공간복잡도는 O(N Log N) 정도다.

역사적으로는, Navigable Small World이란 그래프 단위에 Skip list를 비롯한 아이디어를 첨가해서 발전시킨 것이라고 할 수 있다.

NSW (Navigable Small World)

HNSW에 대해서 이해하려면 그 이전 단계인 NSW(Navigable Small World)에 대해서도 짚고 넘어갈 필요가 있다.
일단 이름에 들어있는 Small World라는 용어 자체는 기술과 연관이 없는 것이었다.

.png?type=w800) 그냥 인간들끼리의 인간관계를 따라가다보면, 보통 대부분은 거의 연결되어있다는 사회 이론이었다.

데이터 수준에서도 사실 비슷하다.
노드끼리 이래저래 연결을 해놓으면, 실제로도 유의미한 탐색 속도를 보일 수 있었다.

그림으로 표현하면 이렇다.

NSW에서 탐색을 할때는 entrypoint라고 하는 특수한 노드에서부터 시작한다.
entrypoint가 일반적인 Tree의 root와 비슷하다고 보면 된다.

entrypoint에서부터 시작해서, 엣지를 따라 검색 벡터와 가장 비슷한 노드를 찾아서 들어가게 된다.
그리고 타고 타고 들어가다가 엣지에 더 비슷한게 없다면 그게 가장 비슷한 벡터라 판단하고 위치에서 종료한다.
이 종료 지점을 local minimum이라고 부르며, 이러한 탐색 접근법을 greedy routing이라고 부른다.

단점

하지만, 모든 노드가 서로 연결되어있는 것은 아니기 때문에, 탐색을 중단했다고 하더라도 그게 가장 비슷한 벡터라는 보장은 없다. 확률적으로 비슷할 확률이 높은 것이고, 근사치에 불과하다.

게다가 일반적인 NSW 구현에서는 데이터가 커질수록 종료 지점, local minimum이 실제 값과 동떨어져있을 확률이 높다. local minimum이 애매한 지점에서 잡혀서 너무 일찍 종료되는 것을 early stopping이라고 한다.

entrypoint를 여러 지점으로 잡아서 뺑뺑이를 많이 돌리면 나아질 수도 있지만, 한계는 존재한다.
그래서 일반적인 벡터 인덱스에서는 NSW을 사용하지 않고, 개선된 버전인 HNSW을 사용한다.

Skip List

HNSW는 Skip List의 확률 기반 계층 관리 방법론을 응용해서 early stopping과 같은 저조한 정확도 문제를 개선한다. Skip List에 대한 내용은 별도 포스트를 참조한다.
https://blog.naver.com/sssang97/223801577003
다만 이건 아이디어만 활용한거고 직접적인 관련이 있는건 아니다

HNSW의 기본 구조

HNSW는 NSW와 접근방식이 크게 다르지는 않다.
다만 Hierarchical(계층형)이라는 이름이 붙은 것처럼, 각각의 그래프를 계층으로 분리해서 관리하는 것이다.

.png?type=w800) 다만 저 노드가 할당될 계층(layer)는 딱히 정해진 규칙 없이 랜덤으로 정해진다.

그리고 높은 계층에 노드가 할당될 확률은 갈수록 낮아진다. 그러니까 계층 2에 할당될 확률이 계층 0에 할당될 확률보다 훨씬 낮은 것이다.
이를 통해 계층이 낮아질수록 데이터가 많아지는, Tree와 비슷한 형태로 데이터가 분포되도록 유도한다.

이러한 구조 때문에 항상 검색 entrypoint는 최상위 계층에만 잡고 시작한다.
최상위 계층에서 비슷한게 있으면 이동하고, 비슷한게 없어서 local minimum에 도달하면, 그 하위 계층에 있으면 내려간다. 이 과정을 반복해서 최하위 계층에서 local minimum에 도달하면 그게 검색의 끝이다.

이런 균형잡힌 탐색 구조 덕분에 좀 더 고르게 검색을 할 수 있고, 정확도를 NSW보다는 높일 수 있다.

HNSW 관련 용어

HNSW 구현체에서는 공통적으로 사용하는 용어들이 있다.
인덱스 생성시에는 보통 다음 2가지 옵션이 존재한다.

M(Minimum): 각 노드가 가질 수 있는 이웃(엣지)의 수. 늘어날 수록 정확도가 올라가는 대신 메모리 사용량이 늘고 속도가 떨어진다.
ef_construction: 그래프 생성시, 현재 노드를 기준으로 참고용으로 큐에 쌓아둘 이웃 노드의 개수. 이게 늘어날 수록 인덱스 구성이 늘어나는 대신 정확도가 늘어날 수 있다.

검색시에는 보통 다음 2가지 옵션이 존재한다.

K: 가져올 데이터 개수
ef: 검색시에 현재 노드에서 고려할 이웃 노드의 수. 보통 k보다는 최소한 1.5배 정도로 크게 잡아야 한다.

필터 가능한 인덱스

일반적으로 벡터 인덱스는 사전 필터링을 적용하기 어렵다고 알려져있지만, 변형을 좀 가하면 불완전하게나마 구현이 가능하긴 하다.
그래서 elasticsearch, qdrant, milvus 등 상당수의 HNSW 기반 데이터베이스들은 벡터 유사도 검색에 필터링을 거는 것을 지원한다.

자세한 내용은 qdrant에 대해 정리한 글을 참조한다.
https://blog.naver.com/sssang97/223845582216

사용 사례

pgvector, elasticsearch, qdrant, milvus 등 많은 벡터 데이터베이스가 HNSW을 기본 벡터 인덱스로 제공한다.

참조
https://velog.io/@eenzeenee/neural-search-HNSW-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%84%A4%EB%AA%85
https://en.m.wikipedia.org/wiki/Hierarchical_navigable_small_world
https://qdrant.tech/articles/vector-search-filtering/
https://qdrant.tech/documentation/concepts/indexing/
https://pangyoalto.com/faiss-1-hnsw/
https://jerry-ai.com/30
https://www.pinecone.io/learn/series/faiss/hnsw/