UNG+: 대규모 벡터-라벨 환경에서의 라벨 탐색 그래프 개선 연구 = UNG+: Enhancing the Label Navigation Graph for High-Cardinality Labels

국문 초록 (Abstract)

최근 비정형 데이터에 대한 검색 수요가 증가함에 따라, 벡터 유사도 검색(vector similarity search)에 메타데이터 필터를 결합한 필터 기반 근사 최근접 이웃 탐색(filtered-ANNS)의 중요성이 커지고 있다. 그러나 filtered-ANNS를 현실적으로 평가하기 위해 필요한, 수천만 개 벡터와 수만 개 고카디널리티(high-cardinality) 라벨이 결합된 대규모 벡터--라벨 데이터셋은 부족한 상황이다. 그 결과 기존 filtered-ANNS 연구는 소규모 데이터셋 또는 SIFT·DEEP 벡터에 합성 라벨을 부여한 데이터셋에 기반해 성능을 검증하는 경우가 많았다.

본 논문에서는 먼저 공개 Stack Overflow 데이터를 기반으로, 약 1천만(10M) 개의 질문 임베딩과 약 6만 개 수준의 태그를 결합한 대규모 벡터--라벨 데이터셋(StackOverflow10M)을 구축한다. 각 질문의 제목과 본문을 벡터로 임베딩하고, 사람이 부여한 태그를 다중 라벨 필터로 사용함으로써 합성 라벨에 의존하지 않는 현실적인 filtered-ANNS 평가 환경을 제공한다. 이어서 기존 Unified Navigating Graph(UNG)를 확장하여, LNG 트리 하향 탐색 과정에서 발견되는 distant superset 라벨 그룹에 extra cross-group edge를 추가하는 \textbf{UNG+}를 제안하고, 브루트포스(brute-force) 구축 비용을 줄이기 위해 기존 벡터 그래프를 재활용하는 변형을 함께 제시한다.

실험 결과, SIFT10M과 DEEP10M에서는 동일 재현율(recall) 기준으로 UNG+가 평균 약 9.9\% 더 높은 처리량(throughput)을 보였고, StackOverflow10M에서는 동일 처리량 기준으로 재현율이 평균 약 4.5\% 향상되었다. 이는 제안 기법이 합성 라벨 및 실제 라벨 환경 모두에서, 고카디널리티 라벨을 갖는 대규모 벡터 데이터셋에 대해 보다 우수한 recall--QPS 트레이드오프를 제공함을 보여준다.

다국어 초록 (Multilingual Abstract)

Recent growth in the demand for searching unstructured data has increased the importance of filtered approximate nearest neighbor search (filtered-ANNS), which combines vector similarity search with metadata filtering. However, large-scale vector–label datasets that realistically reflect production conditions—tens of millions of vectors paired with tens of thousands of high-cardinality labels—remain scarce. As a result, prior filtered-ANNS studies have often validated performance using small-scale datasets or datasets created by assigning synthetic labels to SIFT/DEEP vectors.

This thesis constructs a large-scale vector--label dataset, StackOverflow10M, by combining approximately 10 million question embeddings with around 60 thousand tags from publicly available Stack Overflow data. The title and body of each question are embedded into vectors, and human-assigned tags serve as multi-label filters, providing a realistic filtered-ANNS evaluation setting without relying on synthetic labels. To improve Unified Navigating Graph (UNG), UNG+ adds extra cross-group edges to distant superset label groups discovered during the top-down traversal of the LNG tree. To reduce brute-force construction cost, a variant that reuses an existing vector graph is also introduced.

Experimental results show that, on SIFT10M and DEEP10M, UNG+ achieves on average about 9.9\% higher throughput at the same recall, and on StackOverflow10M, it improves recall by about 4.5\% on average at the same throughput. These results demonstrate that the proposed method provides a better recall--QPS trade-off for large-scale vector datasets with high-cardinality labels in both synthetic-label and real-label settings.

목차 (Table of Contents)

• 1 서론 1
• 1.1 연구 배경 1
• 1.2 문제 정의 및 연구 동기 2
• 1.3 연구 목적 및 기여 4
• 1.3.1 연구 범위 4
• 1.4 논문 구성 5
• 2 배경 및 관련 연구 7
• 2.1 벡터 검색(Vector Search)의 기본 개념 7
• 2.2 근사최근접탐색(Approximate Nearest Neighbor Search, ANNS) 의 정의와 특징 8
• 2.3 Filtered-ANNS의 정의 및 구성 요소 10
• 2.4 기존 ANNS 인덱싱 구조: Graph 기반 vs IVF 기반 12
• 2.4.1 Graph 기반 인덱스 12
• 2.4.2 IVF(Inverted File Index) 기반 인덱스 13
• 2.5 기존 filtered-ANNS 연구 동향 및 한계 14
• 2.5.1 나이브 접근법: pre-filtering, post-filtering, 인덱스 복제 14
• 2.5.2 그래프기반filtered-ANNS: Filtered-DiskANN, NHQ, ACORN 15
• 2.5.3 UNG: Label Navigating Graph와Unified Navigating Graph 16
• 2.5.4 벡터 수 증가에 따른 성능 한계 17
• 3 대규모 StackOverflow 벡터–라벨 데이터셋 구축 20
• 3.1 데이터 소스 및 수집 기준 21
• 3.2 텍스트 임베딩 및 태그 기반 라벨 정의 22
• 3.3 최종 데이터 통계 24
• 4 제안 기법: Extra Cross-Group Edge 기반 인덱스 품질 개선 28
• 4.1 기존 Unified Navigating Graph (UNG) 방식 개요 28
• 4.2 기존 UNG의 cross-group edge 구축 방식 29
• 4.2.1 Minimum superset 기반 cross-group edge 29
• 4.2.2 개념적 관점에서의 cross-group edge 구성 30
• 4.3 기존 방식의 문제점 31
• 4.3.1 라벨 집합 수 증가에 따른 그룹 분할 문제 31
• 4.3.2 Minimum superset 중심 cross-group edge의 한계 31
• 4.4 제안 기법: Extra Cross-Group Edge 32
• 4.4.1 Distant superset 라벨 집합의 정의 32
• 4.4.2 Extra cross-group edge 후보 선택 기준 33
• 4.5 UNG+ 인덱스 구성 알고리즘 34
• 4.5.1 UNG+ 전체 인덱스 구성 34
• 4.5.2 브루트포스 기반 extra cross-group edge 구축 알고리즘 34
• 4.5.3 그래프 인덱스 재활용 기반 extra cross-group edge 구축 알고리즘 35
• 4.6 빌드 시간 감소를 위한 그래프 인덱스 재활용 36
• 5 실험 및 평가 40
• 5.1 실험 환경 40
• 5.2 데이터셋 41
• 5.3 기본 성능 평가 42
• 5.4 벡터–라벨 정렬도에 따른 성능 차이 분석 43
• 5.4.1 벡터–라벨 정렬도 분석 43
• 5.4.2 Shortcut landing rate를 통한 shortcut 효과 측정 45
• 5.5 인덱스 빌드 시간 및 그래프 재활용 효과 46
• 5.5.1 인덱스 빌드 시간 비교 47
• 5.5.2 그래프 인덱스 재활용 시 성능 47
• 5.6 인덱스 크기 및 간선 수 증가에 따른 오버헤드 49
• 6 결론 52