Vector DB의 Indexing 이란?

 

 

Vector DB 인덱싱 개요

 

벡터 데이터베이스 인덱싱(Vector Database Indexing)은 고차원의 데이터를 효율적으로 관리하고 검색하기 위해 사용되는 기술입니다. 이 기술의 주된 목표는 검색 정확도와 검색 속도 사이의 최적의 균형(trade-off)을 찾는 것입니다. 인덱싱은 데이터를 구조화된 인덱스에 저장함으로써, 추후에 이루어지는 검색이 더 빠르고 정확하게 이루어질 수 있도록 합니다.

 

기술의 필요성

대용량의 데이터셋 내에서 특정 데이터를 빠르게 찾아내는 것은 매우 중요한 문제입니다. 특히, 이미지, 비디오, 오디오와 같은 멀티미디어 데이터들이나, 사용자의 선호도를 반영한 추천 시스템 등에서 사용되는 고차원 벡터들은 전통적인 데이터베이스 인덱스 기법으로는 효율적으로 관리하기 어렵습니다. 이러한 고차원 데이터를 효과적으로 처리하기 위해 벡터 인덱싱 기술이 필요합니다.

 

ANN(Approximate Nearest Neighbors) 검색과 KNN(K-Nearest Neighbors)

벡터 DB 인덱싱에서는 KNN 대신 ANN 방식을 주로 사용합니다. KNN 검색은 가장 가까운 K개의 데이터 포인트를 정확하게 찾아내는 반면, ANN 검색은 "근사적으로" 가까운 이웃을 찾아내는 방식입니다. ANN은 KNN에 비해 더 빠른 검색 속도를 제공하며, 대규모 데이터셋에서는 ANN이 더 효율적입니다.

 

벡터 임베딩 저장 구조 (Indexing Structures)

벡터 임베딩을 저장하는 방법에는 여러 가지 구조가 있으며, 각 구조는 특정 상황에서의 검색 성능과 저장 효율성에서 장단점을 가집니다. 다음은 주요 인덱스 구조들의 설명입니다:

 

1. 해시 인덱스 (Hash Index)

해시 인덱스는 해시 테이블을 사용하여 데이터를 저장합니다. 각 벡터는 해시 함수에 의해 계산된 키를 기반으로 인덱스 됩니다. (고차원->저 차원)

장점 : 속도가 빠르다

단점 : 검색 정확도가 좋지 않다.

 

 

Query -> 임베딩 -> hash function -> hash bucket -> result

 

2. 트리 인덱스 (Tree Index)

Binary search tree 구조를 사용해서 고차원 벡터공간에서 검색 속도 향상을 하고 유사한 벡터들이 같은 서브트리에 속하도록 하는 구조다. 검색 시 해시버킷과 유사하게 Query 가 속하는 서브트리 노드에 존재하는 다른 벡터 간 거리만 계산해서 최적화한다.

 

장점 : 속도가 매우 빠르다

단점 : 고차원 벡터에 대해서는 검색 정확도가 좋지 않다.

 

annoy

벡터스페이스의 임베딩들이 선을 나누고 나누고 나누고 다차원에서 시각화 한 모습 hyperplane(쪼개 진영역) 유사한 벡터를 찾는 것

 

3. 역파일 인덱스 (Inverted File Index)

역파일 인덱스는 전통적인 텍스트 검색에 사용되는 방법으로, 각 토큰(혹은 특성)에 대한 문서의 리스트를 저장합니다. 벡터 데이터에 적용할 때는 각 차원의 특정 범위를 토큰으로 취급하고 해당 범위에 속하는 벡터의 리스트를 매핑합니다. 이 방식은 희소 벡터에 특히 효과적입니다.(보로노이 다이어그램 기반 N개의 공간으로 나누어서 서칭스페이스를 줄이는 효과)

 

장점 : 검색 속도가 매우 빠름

단점 : 공간을 형성하는 벡터가 많을수록 공간 나누는 작업의 속도가 느려짐

 

 

4. 그래프 인덱스 (Graph Index)

그래프 인덱스는 벡터를 노드로 간주하고, 유사한 벡터들 사이에 에지를 생성합니다. 검색 시에는 시작 노드로부터 그래프를 탐색하여 근접 이웃을 찾습니다. 이 구조는 복잡한 유사성 패턴을 잘 나타낼 수 있지만(edge connection), 대규모 데이터셋에서는 높은 연산 비용이 발생할 수 있습니다. 현시점 Goat.. Graph DB 도 있음

 

HNSW

장점 : 검색 속도가 빠르고 검색 성능도 빠르다

단점 : 검색 그래프를 구성하는 방식에 따라 검색 성능 의존적이다(파라미터 튜닝 필요)

 

계층별로 hierarch 하게 밀도가 가장 낮은 계층부터 시작해서, 다음 계층으로 이동하고 밀도가 높아지면 또, 다음 계층으로 넘어가서 최종적으로 쿼리 벡터노드와 가장 가까운 이웃을 찾을 때까지 탐색을 한다.

 

벡터 임베딩 저장 형태 (Compression)

벡터 임베딩을 어떻게 압축하여 저장할 것인가에 대한 접근 방법도 중요합니다. 다음은 두 가지 주요 압축 방법입니다:

 

1. Flat

'Flat' 저장 방식은 벡터를 그대로, 아무런 압축 없이 저장하는 방식입니다. 이 방식의 가장 큰 장점은 데이터의 정확도를 100% 유지할 수 있다는 점입니다. 하지만, 매우 큰 저장 공간을 요구하며, 대규모 데이터셋에서는 실용적이지 않을 수 있습니다. (데이터가 방대하지 않은 측면에서는 유리할 수 있다, knn-fullsearch, Brute-force 한 거리계산)

 

2. Quantized

'Quantized' 저장 방식은 벡터를 소수의 대표 값만을 사용하여 근사적으로 저장하는 방식입니다. 이 방법은 저장 공간을 크게 절약할 수 있으며, 연산 속도도 향상됩니다. 주요 방법으로는 벡터 양자화(Vector Quantization)가 있으며, 이는 벡터의 각 차원을 일정한 간격으로 분할하여 인덱스화합니다. 손실 압축 방식이므로 일부 정보는 손실되지만, 전체적인 유사성은 잘 보존됩니다.

 

Float -> int

Scalar Quantization / Product Quantization으로 사용이 된다.