neighbor search Query와 거리가 가까운 데이터 벡터를 찾아 관련성 높은 결과 제공 Ex. multimedia search, web search Exact K-NN Search Query를 전체 n개 벡터와 비교하여 정확한 K개 nearest neighbors 탐색 대규모 데이터에서는 높은 computation cost와 query latency 발생
for Billion-scale Graph Based DiskANN은 당시 billion-scale ANNS의 state-of-the-art 작은 RAM과 저렴한 SSD를 활용하면서 높은 recall과 낮은 latency 유지 (Hybrid ANNS) Inverted Index Based Vector space를 여러 posting lists로 분할 Ex. Inverted Index: [posting lists: vector1, vector2 ... ] Vectors를 PQ로 압축하여 posting lists 전체를 RAM에 저장 Limitation Lossy compression의 거리 오차로 recall@1 약 60% Recall 개선을 위해 10～100배 많은 candidates를 반환하면 reranking cost와 latency 증가
줄이면서 높은 recall 유지 Hierarchical Balanced Clustering Posting list 길이를 제한하고 균형화 Clustering complexity 및 index build cost 감소 Closure Multi-cluster Assignment + RNG Boundary vector를 가까운 여러 posting list에 선택적으로 복제 RNG로 인접 list 간 중복을 줄이면서 boundary recall 향상 Query-aware Dynamic Pruning Query-centroid 거리에 따라 불필요한 posting list를 동적으로 제거 높은 recall을 유지하면서 SSD I/O와 query latency 감소
Limitation 긴 posting list는 여러 번의 disk read가 필요 Average posting length를 줄이려면 posting list 수 N을 늘려야 함 Large N-partition clustering Limitation list 크기 불균형 → 특정 query의 SSD read 증가 → Latency 증가 Average posting length뿐 아니라 list 간 length 균형도 중요 높은 clustering cost(index build cost) 발생
Balanced Clustering Multi-constraint Balanced Clustering Cluster 내부 거리 최소화 (K-Means) 전체 데이터 X 각 posting list의 크기가 평균에 가까워짐 |X|개 데이터 벡터 각 벡터는 m차원 C: Centroid 행렬 N개 centroid 각 vector의 centroid Vector–centroid distance 각 list length와 average list length 간 차이 centroid도 m차원 H: Cluster assignment 행렬 Clustering quality와 posting-list length balance를 함께 최적화 but, billion-scale에서 여전히 list 수 N 매우 큼 → index build cost 지나치게 증가 |X|개 행 cluster 갯수 N개 열
Balanced Clustering Hierarchical Balanced Clustering 전체 데이터를 N개 cluster로 한 번에 분할하지 않음 매 단계에서 작은 수 k개의 cluster로 balanced partition 각 posting list가 제한된 크기 이하가 될 때까지 반복 Cluster 수: 1 → k → k2 → ⋯ → N 계층 깊이(분할 횟수) logkN → 시간복잡도: Effect Posting list 길이를 제한하고 균형화 list당 disk accesses 감소 Billion-scale index build cost 감소
Balanced Clustering Representative vector 각 centroid를 centroid와 가장 가까운 실제 벡터로 교체 Posting list 선택에 사용 실제 데이터이므로 nearest-neighbor candidate가 될 수 있음 Effect Navigation computation을 candidate evaluation에 재활용 불필요한 distance computation 감소
Balanced Clustering Memory SPTAG Index N개의 posting-list representatives를 대상으로 RAM에 SPTAG 구축 Space Partition Tree: Query와 가까운 graph search 시작점 탐색 Relative Neighborhood Graph: 시작점 주변을 탐색하여 가까운 representatives 탐색 Effect 최대 K개의 posting-list candidates를 sub-millisecond 수준으로 반환
Index Building 1.Hierarchical Balanced Clustering 전체 데이터를 작은 k-way clustering으로 반복 분할 최종 posting lists와 각 list의 centroid 생성 2.Representative Selection 각 centroid에 가장 가까운 실제 데이터 vector를 representative로 선택 3.Memory SPTAG Index Construction 모든 posting-list representatives를 대상으로 RAM에 SPTAG index 구축
Multi-cluster Assignment + RNG Multi-cluster Assignment 각 vector를 가까운 여러 clusters에 중복 배정 Posting size가 증가하면서 앞서 제한한 list length가 다시 증가 Disk reads 증가와 query latency 발생 Closure Multi-cluster Assignment 여러 centroids까지의 거리가 비슷한 boundary vector만 선택적으로 복제 Hierarchical clustering의 final clustering step에서 적용 Effect Posting capacity 증가를 제한하면서 boundary recall 향상 복제된 가까운 posting list 중 하나만 검색해도 해당 vector를 발견할 수 있음
Multi-cluster Assignment + RNG Problem |X1| = |X2| = 100, |X1 ∩ X2| = 70 |X1 ∪ X2| = 130 SSD에서 200개의 vector를 읽어도 unique candidates는 130개 여러 posting lists를 읽어도 unique candidates는 충분히 증가하지 않음 중복 벡터를 읽는 데 high-cost disk reads 사용 RNG Rule Dist(cij, x) > Dist(cij-1,cij)를 만족하면 cluster ij를 skip 가까우면서 서로 다른 방향의 clusters를 선택 Effect 가까운 posting list 간 similarity와 duplicated vectors 감소 동일한 disk reads로 더 많은 unique candidates 확인
Index Building 1.Hierarchical Balanced Clustering 전체 데이터를 작은 k-way clustering으로 반복 분할 최종 posting lists와 각 list의 centroid 생성 2.Representative Selection 각 centroid에 가장 가까운 실제 데이터 vector를 representative로 선택 3.Memory SPTAG Index Construction 모든 posting-list representatives를 대상으로 RAM에 SPTAG index 구축 4.Posting-list Expansion Final clustering에서 계산한 centroids를 기준으로 boundary vector 식별 및 복제 5.Index Placement RAM: Representative vectors, SPTAG index SSD: 확장된 full-precision posting lists
Difficulty Query마다 필요한 posting list 수가 다름 Easy Query: 가장 가까운 centroid가 뚜렷 Difficult Query: 여러 centroid까지의 거리가 비슷 모든 query에서 동일한 K개 list를 검색하면 K가 작을 때: Difficult Query → Recall 저하 K가 클 때: Easy Query → Latency 증가
Dynamic Pruning Query-aware Dynamic Pruning Memory SPTAG에서 가까운 posting-list 후보를 최대 K개 탐색 가장 가까운 representative와의 거리를 기준으로, 상대적으로 거리가 비슷한 list만 SSD에서 읽음 Effect Query별 SSD read를 효율적으로 적용하여 높은 recall을 유지하면서 query latency 감소 Easy query: 적은 posting list 검색 Difficult query: 많은 posting list 검색
Query Search 1.Candidate Posting-list Search Query를 RAM의 SPTAG index에서 검색 가까운 representative를 기준으로 최대 K개의 posting-list 후보 탐색 2.Query-aware Dynamic Pruning 가장 가까운 representative와 상대적으로 비슷한 거리에 있는 list만 선택 실제 검색할 posting-list 수 Kq를 query별로 동적으로 결정 3.Posting-list Loading 선택한 Kq개의 posting lists만 SSD에서 RAM으로 로드 4.Fine-grained Search 불러온 posting lists의 full-precision vectors와 query 사이의 거리 계산 전체 candidate 중 가까운 top-k vectors를 최종 결과로 반환
SPANN을 여러 machines로 확장하여 super large-scale vector search 지원 Inverted index의 partial search를 machine-level partial dispatch로 확장 Query와 가까운 partitions를 보유한 일부 machines만 검색 Hot-spot Machine Problem Data size가 균등해도 query workload가 균등한 것은 아님 자주 검색되는 vector-space 영역이 특정 machine에 배치되면 query access가 집중되는 hot spot 발생 따라서 machine 간 Data size와 Query workload 두 가지 모두 균형화해야 함
SPANN Small-partition Construction Multi-constraint balanced clustering으로 partition별 vector 수를 균형화 Closure assignment로 partial dispatch 과정의 boundary recall 보완 Machine 수 M보다 많은 small partitions 생성 Historical Query Access Estimation Query history를 이용하여 각 small partition의 access workload 파악 Best-fit Bin Packing 여러 small partitions를 M개의 large bins로 조합 → 각 large bin을 하나의 machine에 배치 Effect Machine 간 data size와 historical query workload 균형화
SPANN과 state-of-the-art all-in-memory ANNS 성능 비교 Latency뿐 아니라 memory cost까지 포함한 성능 검증 Result SPANN은 SSD I/O로 latency가 상대적으로 높지만, 낮은 memory cost를 바탕으로 가장 높은 serving capacity 달성
SPANN의 각 기법이 검색 성능에 미치는 영향 분석 Centroid 증가로 posting lists가 작아지면서 검색 성능 향상 Posting-list length balance가 inverted index의 recall-latency 성능에 중요 Multiple replicas가 boundary vector의 recall probability 높임 Query 별로 불필요한 posting lists 제거
& 4.3.2) Distributed SPANN의 workload reduction 및 scalability 검증 Machine 수를 늘리면서 data size와 query workload를 분산 높은 recall을 유지하면서 query latency 단축 Machine 수가 증가할수록 machine당 query access 감소 32개 machines 중 query당 평균 6.3개만 검색 Closure assignment로 저장 vector 수는 약 20% 증가하지만, query workload는 크게 감소 Result Machine 간 workload를 균형화하고 query당 검색할 machine 수를 제한 높은 recall과 낮은 serving cost를 유지하면서 distributed scalability 확보
index methodology를 따르는 memory-disk hybrid ANNS system RAM: Representative vectors, SPTAG index SSD: 확장된 full-precision posting lists Results Billion-scale 데이터셋에서 recall, latency, memory cost 측면의 state-of-the-art 성능 달성 Distributed search에서도 query당 검색할 머신 수를 제한하여 우수한 scalability 확보 높은 효율성과 낮은 serving cost로 초대규모 vector search 지원
분할 I/O ...so that it can be loaded into memory in only a few disk reads 일반적인 SSD 시스템에서의 의미 저장 시스템은 데이터를 일정한 page/block 단위로 관리·접근 하나의 posting list가 여러 page에 걸쳐 저장되면, 메모리에 적재하기 위해 여러 page read 필요 따라서 posting list가 클수록 리스트 하나를 load하는 데 필요한 read 수 증가 필요한 Page Read 수 ≈ ⌈Posting List 크기 / Page 크기⌉ SPANN 구현에서의 의미 SPANN은 posting list를 4KB software page 단위로 관리 8KB posting list → 2개의 page read 12KB posting list → 3개의 page read 여기서 여러 disk read는 하나의 긴 posting list가 여러 page로 나뉘어 읽힌다는 의미 설계 결론 N 증가 → 평균 posting list 길이 감소 → 리스트당 필요한 page read 수 감소 → SSD 접근 부담 감소 따라서 SPANN은 posting list의 최대 길이를 제한하고, 리스트 간 크기도 균형 있게 유지
수 N 결정 N의 의미 전체 posting list의 수 RAM에 저장되는 representative vector의 수 SPTAG head index가 색인하는 vector의 수 N은 무엇으로 결정하는가? 전체 데이터 중 representative로 사용할 비율 Ratio를 설정 N ≈ 전체 vector 수 × Ratio N이 증가하면 평균 posting list 길이는 감소하지만, representative와 SPTAG head index의 메모리 사용량은 증가 따라서 posting list 최대 크기, RAM 예산, SSD 접근 비용, recall을 함께 고려해 조정 논문 실험 설정 SIFT1M: Ratio 4%, 8%, 16%, 20% 비교 → 16% 이후 성능 향상이 거의 포화 그러나 Ratio는 보편적인 고정값이 아니라, posting list 길이와 RAM head index 비용 사이의 trade-off를 조절하는 파라미터
Partition Tree And Graph) Microsoft에서 개발한 대규모 벡터 검색을 위한 메모리 기반 ANN 라이브러리 공간 분할 Tree와 Neighborhood Graph를 결합한 탐색 구조 Tree에서 유망한 탐색 시작점(seed)을 찾고, Graph를 따라 가까운 벡터 탐색 SPTAG의 두 가지 조합 SPTAG-KDT: KD-tree + Relative Neighborhood Graph SPTAG-BKT: Balanced K-means Tree + Relative Neighborhood Graph SPANN에서의 사용 SPANN은 representative vector에 대해 SPTAG-BKT index를 구축 원본 billion-scale vector 전체가 아니라, RAM에 저장된 representative만 색인 Query 처리 시 SPTAG를 이용해 유망한 representative와 posting list를 선택
1.Balanced K-means Tree 구축 a.Representative vector를 여러 cluster로 균형 있게 분할 b.각 cluster를 다시 재귀적으로 분할 c.각 tree node에 cluster 중심과 child node 정보 저장 d.일정 개수 이하의 vector가 남으면 leaf node로 종료 e.BKT는 query가 가까운 영역을 빠르게 찾을 수 있도록 탐색 공간을 계층적으로 정리 2.Relative Neighborhood Graph 구축 a.각 representative를 graph node로 사용 b.가까운 representative를 연결해 초기 KNN graph 구성 c.RNG 규칙으로 불필요하거나 중복되는 edge 제거 d.탐색에 유용한 이웃 연결만 남겨 graph 정제 e.Tree partition이 달라도 가까운 representative 간 연결 가능 Index Building 결과 BKT: representative 공간을 계층적으로 분할 RNG graph: representative 간 탐색 경로 구성
1.BKT 탐색 a.Query를 BKT의 root node에서 시작 b.Query와 각 child cluster의 중심 비교 c.가까운 child node를 우선적으로 탐색 d.탐색한 leaf에서 RNG graph 탐색을 시작할 seed representative 선택 2.RNG graph 탐색 a.BKT에서 선택한 seed representative에서 graph 탐색 시작 b.Seed의 graph 이웃과 query의 거리를 계산 c.가장 유망한 후보를 중심으로 graph를 반복 탐색 d.graph edge를 따라 다른 영역의 representative까지 이동 가능 Search 결과 SPTAG가 유망한 representative 후보 반환 SPANN은 해당 representative가 가리키는 posting list 선택 선택된 posting list를 SSD에서 읽고 세부 vector search 수행
발생시키는 메모리 비용 SPTAG head index에는 다음 정보 저장 Representative vector RNG graph의 이웃 정보 BKT tree 구조 Tree와 graph를 관리하기 위한 metadata 따라서 representative vector만 저장하는 것보다 RAM 사용량이 증가 추가 오버헤드는 vector 차원·자료형·이웃 수·tree 설정에 따라 달라짐 SPTAG 자체는 메모리를 줄이는 구조가 아니라, 추가 메모리로 대표값 탐색 비용을 줄이는 구조 SPANN의 핵심 Trade-off N 증가 → Posting List 길이 감소 → SSD I/O 감소 N 증가 → Representative 수 증가 → Head Index 메모리 증가 → Head Search 계산량 증가 SPTAG는 메모리 비용을 제거하는 기술이 아니라, 추가 RAM을 사용해 N 증가로 발생한 Head Search 비용을 완화하는 설계
단위로 데이터를 읽기 때문에, 긴 posting list는 여러 page read로 나누어 적재될 수 있다. SPANN은 posting list를 4KB software page 단위로 관리하므로, 리스트가 길어질수록 필요한 read 수와 query latency가 증가한다. Posting list 수 N은 RAM 용량의 일정 비율로 직접 정하기보다, 전체 벡터 중 representative로 사용할 비율인 Ratio를 중심으로 결정된다. SIFT1M 실험에서는 Ratio 0.16 이후 성능 향상이 거의 포화되었으며, billion-scale 실험에서는 DiskANN과 전체 메모리 사용량을 맞추기 위해 데이터셋 별 Ratio를 조정했다. SPTAG는 N 증가로 발생하는 representative exhaustive search 비용을 줄이기 위한 ANN 기반 head index다. 일부 representative만 탐색하므로 속도는 빨라질 수 있지만, representative routing의 recall이 낮아질 수 있다. SPTAG의 graph와 tree를 구축하면 representative만 저장하는 경우보다 RAM 사용량은 증가한다. 논문은 SPTAG의 구성 요소별 메모리 breakdown을 별도로 제시하지 않았으며, 추가 메모리로 representative 탐색 시간을 줄여, SSD I/O를 줄이는 trade-off를 선택한 것으로 볼 수 있다.
nawkwoo
sazimai
institutdelelevage
datascientistsociety
xspa2012
fkske
s_mizuki_nlp
gpeyre
ontheslope
polipoli
mickey_0226
.png){kind=avatar}
satai
davidcarrasco
addyosmani
marcoroth
mkilby
badams
uxyall
thirion
frankvandijk
dougneiner
chriscoyier
szymonslowik
mza
