Vector Clustering for Disk-based HNSW = 디스크 기반 HNSW를 위한 벡터 클러스터링

국문 초록 (Abstract)

디스크 기반 벡터 검색은 대규모 검색 증강 생성 시스템을 효율적으로 운영하기 위한 필수적인 기술이 되었다. 그래프 기반 근사 최근접 이웃 인덱스인 HNSW는 디스크 환경에서 실행될 경우 낮은 지역성과 과도한 랜덤 I/O로 인해 성능이 크게 저하된다. pgvector와 같은 디스크 기반 HNSW는 대규모 메모리 버퍼를 할당하더라도 낮은 버퍼 캐시 적중률로 인해 페이지 I/O가 주요 성능 병목으로 작용한다.

본 논문에서는 이러한 I/O 병목이 물리적인 페이지 배치 방식에서 기인함을 분석하고, HNSW 알고리즘이나 DBMS 구조를 변경하지 않으면서 지역성을 개선하는 세 가지 기법을 제안한다. 첫째, Locality-Preserving Page Layout (LP-Layout)은 검색 과정에서 함께 접근되는 HNSW 노드들을 동일하거나 인접한 페이지에 배치한다. 둘째, Locality-Aware Insertion (LP-Insert)은 동적 업데이트 상황에서도 공간적 지역성을 유지할 수 있도록, 새로 삽입되는 노드를 해당 그래프 이웃과 정렬된 페이지에 배치한다. 셋째, Binary Quantization (BQ)은 페이지당 저장 가능한 노드 수를 증가시키는 저장 최적화 기법으로, 앞선 지역성 최적화 효과를 증폭시킨다.

제안한 기법들은 pgvector에 구현되어 여러 데이터셋과 다양한 인덱스 크기에 대해 평가되었다. 실험 결과, 동적 삽입 환경에서도 검색 정확도를 안정적으로 유지하면서 버퍼 캐시 적중률을 최대 3.23배까지 향상시킬 수 있음을 확인하였다. 이러한 결과는, 저장 계층 수준의 지역성 최적화를 통해 기존 HNSW 검색 로직을 변경하지 않고도 업데이트 친화적인 고성능 디스크 기반 HNSW 검색을 구현할 수 있음을 보여준다.

다국어 초록 (Multilingual Abstract)

Disk-based vector search is essential for scalable and efficient retrieval-augmented generation systems. Although the graph-based ANN index HNSW supports dynamic insertions and deletions, its performance degrades significantly on disk due to poor locality and excessive random I/O. In database-integrated disk-based HNSW systems such as pgvector, page I/O becomes the primary performance bottleneck despite large memory buffers.

This paper analyzes how this I/O bottleneck originates from physical page layout and proposes three locality-preserving techniques without modifying the HNSW algorithm or DBMS architecture. (1) Locality-Preserving Page Layout colocates frequently co-accessed nodes, (2) Locality-Aware Insertion preserves locality under dynamic updates, and (3) Binary Quantization increases page density to amplify locality benefits.

We implement these techniques in pgvector and evaluate them across multiple datasets and index sizes. Results show up to a 3.23× improvement in buffer cache hit ratio while maintaining stable search accuracy under dynamic insertions. This demonstrates that storage-level locality optimization enables update-friendly, high-performance disk-based HNSW search.

목차 (Table of Contents)

• Abstract i
• Contents ii
• List of Figures iv
• List of Tables v
• 1 Introduction 1
• 2 Background 4
• 2.1 HNSW-based index in VectorDB 4
• 2.2 I/O Inefficiencies of HNSW Index on SSDs 7
• 3 Proposed Framework 11
• 3.1 Framework Overview 11
• 3.2 LP-Layout: Locality-Preserving Page Layout 12
• 3.3 LP-Insert: Locality-Aware Insertion 14
• 3.4 BQ: Binary Quantization 16
• 4 Experimental Setup 18
• 5 Evaluation 20
• 6 Related Work 27
• 7 Conclusion 29
• 요약 35