A Layered Approximate Search Approach over Clustering for Scalable Vector Databases

벡터 데이터베이스는 최신의 문맥적 정보를 제공함으로써 대형 언어 모델(Large Language Model, LLM)을 강화하는 검색 기반 생성(Retrieval-Augmented Generation, RAG) 시스템의 핵심 구성 요소이다. RAG는 응답 품질을 향상시키고 환각(hallucination) 문제를 완화하지만, 대규모 벡터 데이터베이스에서의 유사도 검색은 여전히 병목으로 남아 있다. 기존의 역파일 인덱스(Inverted File Index, IVF)는 메모리에 중심점(centroid)만 저장하여 메모리 사용량을 줄이지만, 모든 중심점을 대상으로 한 완전 탐색 방식으로 인해 확장성이 제한되고 질의 시간이 증가한다. 본 연구에서는 중심점을 계층적 그래프로 구성하고, Hierarchical Navigable Small World (HNSW) 네트워크를 활용하여 근접 클러스터를 근사적으로 탐색하는 계층적 근사 검색(Layered Approximate Search, LAS) 인덱싱 기법을 제안한다. LAS는 관련 클러스터를 효율적으로 식별함으로써 비교 연산과 메모리 접근 횟수를 크게 줄인다. FAISS(Facebook AI Similarity Search)에 구현하여 SIFT(Scale-Invariant Feature Transform) 데이터셋으로 평가한 결과, LAS는 IVF와 동일한 정확도를 유지하면서 비교 횟수를 1.5% 수준으로 감소시켰다.