기술 요약: ANNLib – 효율적인 근사 최근접 이웃 탐색을 위한 개발 프레임워크

1. 문제 정의

근사 최근접 이웃 탐색(Approximate Nearest Neighbor Search, ANNS)은 고차원 벡터 공간에서의 효율적인 검색을 가능하게 하는 현대 딥러닝 파이프라인의 핵심 구성 요소입니다. 그동안 상당한 연구가 ANNS 시스템의 기능 확장(예: 동적 업데이트, 필터링 또는 히스토리 스냅샷 지원) 또는 성능 극대화(처리량 및 재현율) 중 하나에 집중되어 왔으나, 최소한의 프로그래밍 노력으로 이 두 가지를 모두 성공적으로 달성하는 시스템은 드물었습니다.

현재의 솔루션들은 다음과 같은 이분법적 문제에 직면해 있습니다:

• 기능이 풍부한 벡터 데이터베이스(예: Milvus, Weaviate)는 사용 편의성을 우선시하지만, 특화된 알고리즘에 비해 성능이 떨어지는 경우가 많습니다.
• 성능 최적화 시스템(예: DiskANN, ParlayANN)은 높은 처리량을 제공하지만, 고도로 최적화된 단일 구조(monolithic)의 코드베이스로 구성되어 있어 새로운 기능이나 애플리케이션별 제약 조건에 적응하기 어렵습니다.

개발자들은 성능과 유연성 사이에서 선택을 강요받으며, 기존의 고성능 엔진 위에 필터링된 검색이나 동적 삭제와 같은 고급 기능을 구현하기 위해 광범적인 코드 재작성이 필요한 상황입니다.

2. 방법론: ANNLib 프레임워크

저자들은 그래프 기반 ANNS 시스템의 알고리즘 로직과 데이터 구조 구성 요소를 분리하도록 설계된 C++ 헤더 전용 라이브러리인 ANNLib를 제안합니다. 이 프레임워크를 통해 개발자는 미리 구축되고 깊이 최적화된 모듈들을 조합하여 고성능 ANNS 시스템을 구성할 수 있습니다.

2.1 핵심 설계 원칙

• 결합 해제 및 모듈화(Decoupling and Modularity): ANNLib은 시스템을 두 개의 독립적인 핵심 구성 요소인 **알고리즘(Algorithms)**과 **데이터 구조(Data Structures)**로 분리합니다.
  • 알고리즘: 인덱스 구축 및 쿼리 로직을 제공합니다. ANNLib은 기본 알고리즘(Vamana, HNSW, HCNNG)과 고급 기능(배치 삽입, 삭제, 필터링 검색, 스냅샷)을 위한 알고리즘 모듈을 포함합니다.
  • 데이터 구조: 기저 그래프 표현을 관리합니다. ANNLib은 그래프를 읽고 수정하기 위한 통합 인터페이스를 제공하며, 다양한 컨테이너 유형(예: 정적 워크로드를 위한 Nested Arrays, 스냅샷을 위한 Functional Trees, 그리고 새로운 Chrono Prefix Array)을 지원합니다.
• 공통 로직 추상화: 프레임워크는 공통적인 그래프 연산(특히 이웃 수집 및 가지치기)을 제네릭 인터페이스(collect 및 prune)로 추상화합니다. 개발자는 공유된 병렬화 및 순회 로직을 재사용하면서, 자신의 특정 알고리즘만이 가진 고유한 로직만을 구현하면 됩니다.
• Edge Agent 패턴: 데이터 구조의 세부 사항을 알고리즘 개발자에게 노출하지 않으면서 다양한 데이터 구조를 지원하기 위해, ANNLib은 "Edge Agent"를 도입합니다. 이 중간 구조는 정점(vertex)의 엣지(edge)에 대한 뷰(view) 역할을 하며, 이를 통해 컨테이너는 자신만의 최적화(예: 트리의 경우 copy-on-write, nested arrays의 경우 직접 배열 접근)를 적용하면서도 알고리즘에는 균일한 인터페이스를 제공할 수 있습니다.

2.2 주요 기술 구현

• 필터링 검색(Filtered Search): Stitched-vamana(레이블별로 구축된 서브 그래프 병합) 및 Filtered-vamana(특정 레이블을 가진 후보를 보존하기 위해 가지치기 조건을 완화)를 통해 구현되었습니다. 두 방식 모두 핵심 빔 탐색(beam search) 로직을 변경하지 않고 이웃 필터링 조건(f_nbhs)을 커스터마이징함으로써 달성됩니다.
• 동적 업데이트 (삭제): FreshDiskANN 방식을 기반으로, ANNLib은 삭제된 지점을 표시하는 단계(상태 배열 및 빠른 경로 체크를 위한 "tombstone" 로직 사용)와 그래프 연결성을 복구하기 위해 이웃을 정리(consolidation)하는 2단계 프로세스를 구현합니다.
• 역사적 스냅샷(Historical Snapshots): 프레임워크는 인덱스의 과거 상태를 쿼리하는 것을 지원합니다. 이를 위해 두 가지 데이터 구조를 도입합니다:
  • Functional Tree (CPAM): 버전을 보존하기 위해 copy-on-write (CoW)를 사용합니다.
  • Chrono Prefix Array: ANNS 그래프를 위해 특별히 설계된 새로운 구조로, 접두사(prefix)를 공유함으로써 시간 경과에 따른 엣지 버전을 압축합니다. 이는 전체 트리 복사에 비해 메모리 오버헤드를 크게 줄여 엣지 중복을 방지합니다.

2.3 애플리케이션 예시

논문은 ANNLib 상에서 최소한의 코드로 네 가지 애플리케이션을 구축함으로써 프레임워크의 유연성을 입증합니다:

1. 일반 ANNS: Vamana 또는 HNSW를 사용하는 표준 정적 검색.
2. 완전 동적 업데이트: 배치 삽론 및 삭제 지원.
3. 필터링 검색: Stitched-vamana 및 Filtered-vamana 구현.
4. 스냅샷을 포함한 스트리밍: 시간적 쿼리를 위해 인덱스의 역사적 버전을 유지 관리.

3. 실험 결과

저자들은 여러 데이터셋(BIGANN, DEEP, OpenAI, Cohere, MARCO, YFCC)과 시나리오에 걸쳐 ANNLib을 최신 베이스라인(ParlayANN, DiskANN, Milvus, Weaviate)과 비교 평가했습니다.

• 삽입 성능: ANNLib의 Vamana 구현은 ParlayANN 대비 평균 1.58배의 속도 향상을 달了했으며, 특정 배치에서는 최대 8.11배 더 빠릅습니다. HNSW 성능은 ParlayHNSW와 대등했습니다(0.99–1.34배 속도 향상). 이러한 이득은 카피 생략(copy elision)과 최적화된 인터페이스 덕분입니다.
• 쿼리 처리량 (일반 검색): ANNLib은 경쟁력 있는 QPS-재현율(QPS-recall) 트레이드오프를 달성했습니다. BIGANN과 같은 대규모 데이터셋에서 성능은 ParlayANN과 일치했습니다. 소규모 데이터셋에서는 높은 재현율에서 유사한 QPS로 수렴했으나, ParlayANN이 보유한 특화된 저재현율 최적화 기능은 부족했습니다.
• 필터링 검색: ANNLib은 거의 모든 경우에서 단일 구조 솔루션(DiskANN, Milvus, Weaviate)보다 우수한 QPS-재현율 곡선을 보여주었으며, 이는 모듈형 설계가 성능을 희생하지 않음을 입증합니다.
• 삭제: ANNLib의 정리(consolidation) 단계는 인덱스 재현율을 재구축 수준에 가깝게 복구했으나, 영향을 받은 지점의 수에 비례하는 계산 비용이 발생했습니다.
• 스냅샷: Chrono Prefix Array는 엣지를 완전히 중복 생성하는 단순 연대순 리스트 방식에 비해 메모리 사용량을 최대 **70.4%**까지 줄였습니다. 스냅샷 기능을 활성화하면 (구조에 따라 1.22배에서 3.32배까지) 빌드 시간이 증가했지만, 대규모 동적 데이터셋에서 메모리 효율성 이득은 매우 컸습니다.

4. 주요 기여

1. 모듈형 프레임워크: ANNLib은 그래프 기반 ANNS를 위해 알고리즘 로직과 데이터 구조 구현을 성공적으로 분리하여 유연한 구성을 가능하게 하는 최초의 프로그래밍 프레임워크를 제공합니다.
2. 통합 추상화: 제네릭 collect/prune 인터페이스와 Edge Agent 패턴의 도입은 다양한 알고리즘과 데이터 구조가 원활하게 상호 운용될 수 있도록 합니다.
3. 새로운 데이터 구조: Chrono Prefix Array의 제안은 동적 그래프의 역사적 스냅샷을 유지하기 위한 공간 효율적인 솔루션을 제공하며, 기존 스냅샷 메커니즘의 특정 병목 현상을 해결합니다.
4. 유연성 및 성능 검증: 논문은 복잡한 기능(필터링, 삭제, 스냅샷)을 최소한의 코드로 구현하면서도 특화된 단일 구조 시스템과 대등하거나 더 나은 성능을 달성할 수 있음을 검증합니다.

5. 의의 및 주장

본 논문은 ANNLib이 고성능 연구 프로토타입과 유연한 프로덕션급 시스템 사이의 간극을 메운다고 주장합니다. 최적화된 구성 요소를 "플러그 앤 플레이" 방식으로 사용할 수 있게 함으로써, ANNLib은 효율성을 저해하지 않으면서도 정교한 ANNS 시스템을 구축하는 데 필요한 엔지니어링 노력을 줄여줍니다.

저자들은 자신들의 설계가 하이브리드 시스템(예: 동적으로 변화하는 데이터셋의 역사적 스냅샷에 대해 필터링 쿼리 수행)을 구축할 수 있게 하며, 이는 기존의 단일 구조 프레임워크에서는 구현하기 어려운 작업임을 강조합니다. 코드 공개는 ANNS 영역에서의 추가적인 연구와 애플리케이션 개발을 촉진하는 것을 목표로 합니다.