Elastic의 벡터 서치를 위한 HNSW와 다중 계층 기능

안녕하세요. BTC_기범입니다.

오늘은 Elastic에서 벡터 서치를 할 때 사용되는

Hierarchical Navigable Small World graphs(이하 HNSW)와

벡터 서치 성능을 높이는데 영향을 미치는

다중 계층 기능에 대해 알아보겠습니다.

---

HNSW (Hierarchical Navigable Small World graphs)

HNSW는 Elasticsearch 8.x 버전에서 도입된 고성능 벡터 검색 알고리즘입니다. 데이터 볼륨과 벡터 유사성 검색에서 차원이 증가하면서 발생하는 성능 문제를 해결하기 위해 고안되었습니다.

HNSW의 주요 특징은 다음과 같습니다.

• 계층적 그래프 구조: 데이터 포인트를 계층적 그래프로 구성하여, 유사한 벡터를 빠르게 찾을 수 있도록 합니다.
• 탐색 가능한 작은 세상 (Navigable Small World): 그래프 내에서 거리가 먼 노드(데이터 포인트) 사이에도 짧은 경로가 존재하여, 효율적인 검색이 가능합니다.
• 근사 nearest neighbor 검색: 정확한 nearest neighbor 검색은 아니지만, 매우 빠르게 근삿값을 찾아냄으로써 성능을 향상시킵니다.

HNSW의 장점

• 빠른 검색 속도: 높은 차원의 벡터 공간에서도 빠른 검색 속도를 제공합니다.
• 확장성: 대규모 데이터셋에서도 효율적으로 동작합니다.
• 메모리 효율성: 다른 알고리즘에 비해 메모리 사용량이 적습니다.

HNSW의 사용 사례

• 유사 이미지 검색: 이미지 특징 벡터를 사용하여 유사한 이미지를 검색합니다.
• 추천 시스템: 사용자 또는 아이템 임베딩을 기반으로 추천을 제공합니다.
• 이상 탐지: 정상 데이터와 다른 패턴을 가진 이상치를 탐지합니다.
• 텍스트 검색: 문서 임베딩을 사용하여 유사한 텍스트를 검색합니다.

다중 계층 기능

다중 계층 기능은 HNSW 알고리즘을 효과적으로 구현하기 위한 기반을 제공합니다. 다중 계층 기능은 여러 개의 인덱스 세그먼트를 계층적으로 구성하여 검색 성능을 향상시킵니다. 이를 통해 HNSW는 각 계층에서 효율적으로 벡터를 검색하고, 빠르게 결과를 찾을 수 있습니다.

다중 계층 기능 유무에 따른 HNSW 알고리즘 구현 차이

HNSW 알고리즘을 구현할 때, Lucene의 다중 계층 기능 유무는 검색 성능과 효율성에 큰 영향을 미칩니다.

다중 계층 기능이 없을 때

• 단일 인덱스 세그먼트: 모든 데이터 포인트가 하나의 인덱스 세그먼트에 저장됩니다.
• 검색 범위 제한: HNSW 그래프가 단일 세그먼트 내에서만 구성되므로, 검색 범위가 제한됩니다.
• 성능 저하: 데이터 양이 증가할수록 검색 성능이 저하됩니다. 특히, 높은 차원의 벡터 공간에서는 더욱 두드러집니다.

다중 계층 기능이 있을 때

• 계층적 인덱스 세그먼트: 데이터 포인트가 여러 계층의 인덱스 세그먼트로 나뉘어 저장됩니다.
• 효율적인 검색: HNSW 그래프가 각 계층에서 구성되어, 검색 범위가 확장되고 효율적인 탐색이 가능합니다.
• 성능 향상: 데이터 양이 증가해도 검색 성능이 유지됩니다. 다중 계층 구조를 통해 검색 범위를 효과적으로 좁힐 수 있기 때문입니다.

구체적인 차이점

1. 그래프 구성:
   • 단일 계층: HNSW 그래프가 단일 세그먼트 내에서만 구성됩니다.
   • 다중 계층: 각 계층마다 독립적인 HNSW 그래프가 구성됩니다. 상위 계층의 그래프는 하위 계층의 그래프를 연결하는 역할을 합니다.
2. 검색 과정:
   • 단일 계층: 검색은 단일 세그먼트 내에서만 이루어집니다.
   • 다중 계층: 검색은 상위 계층에서 시작하여, 유사한 벡터가 있는 하위 계층으로 점진적으로 이동합니다. 이를 통해 검색 범위를 효율적으로 좁힐 수 있습니다.
3. 성능:
   • 단일 계층: 데이터 양이 증가하면 검색 성능이 크게 저하됩니다.
   • 다중 계층: 데이터 양이 증가해도 검색 성능이 유지되거나 향상됩니다. 다중 계층 구조 덕분에 검색 범위가 효과적으로 좁혀지기 때문입니다.
     
     

---

오늘은 Elastic에서 벡터 서치를 할 때 사용되는

Hierarchical Navigable Small World graphs(이하 HNSW)와

벡터 서치 성능을 높이는데 영향을 미치는

다중 계층 기능에 대해 알아보았습니다.

Elastic을 벡터 DB로 사용한다면 한 번쯤 확인해 보면 좋은 내용인 것 같습니다.

다음에 또 봐요~!