CONDA: A Connectivity-Aware Dynamic Index for Approximate Nearest Neighbor Search over Evolving Data

Paper: Darae Lee; Min-Soo Kim (2026). "CONDA: A Connectivity-Aware Dynamic Index for Approximate Nearest Neighbor Search over Evolving Data". Proceedings of the VLDB Endowment, 19(11), 3357–3370. PDF · DOI

쇼핑 검색이나 문서 검색은 질의와 가까운 항목을 찾기 위해 문장·이미지를 벡터로 바꿔 비교할 수 있습니다. 모든 항목을 매번 비교하지 않고 후보를 좁히는 여러 방법이 있으며, 그래프 기반 근사 최근접 이웃 검색(ANN)은 간선을 따라 가까운 후보를 찾습니다. 데이터가 계속 추가되고 삭제되면, 처음 만든 그래프 경로만으로는 가까운 항목에 닿기 어려워질 수 있습니다. CONDA는 그래프의 실제 연결을 살펴 간선을 고르고 삭제 후 남는 참조를 검색 중 정리하는 동적 벡터 인덱스입니다.

H+ Embedding은 벡터 표현을, Hierarchical BM25는 어휘 검색에서 방문할 범위를 다룹니다. CONDA 논문은 벡터 그래프의 연결 갱신을 다룹니다.

1. 벡터 그래프에서 ‘연결’은 무엇인가요?

각 벡터를 노드로 놓고, 검색 중 서로 이동할 수 있는 관계를 간선으로 저장합니다. 한 노드에서 나가는 간선 수는 out-degree, 들어오는 간선 수는 in-degree라고 합니다. 논문은 나가는 간선 수를 R로 제한합니다. 간선을 너무 많이 남기지 않으면서 좋은 검색 경로를 갖추는 것이 문제입니다.

가지치기(pruning)는 후보 이웃 중 일부를 골라 직접 연결을 저장하고 나머지를 생략하는 과정입니다. p에서 가까운 후보 v를 빼도 되는지 판단할 때, 선택한 이웃 u를 거쳐 p→u→v로 실제 이동할 수 있는지가 중요합니다. 거리만 보면 우회로처럼 보여도 u에서 v로 가는 간선이 없으면 그래프에는 그 길이 없습니다.

2. CRNG는 후보 안의 두 홉 경로를 살핍니다

CONDA의 CRNG는 검색에서 찾은 후보를 p와의 거리순으로 살펴봅니다. 이미 선택한 u와 후보 v 사이에 실제 u→v 간선이 있고, p에서 u를 거쳐 v로 갈수록 v까지의 거리가 줄어들면 p→v를 생략할 수 있습니다. 이 조건을 만족하는 경로가 없으면 p에서 v로 가는 간선을 직접 남깁니다.

두 홉은 중간 노드 하나를 거치는 경로입니다. 논문의 Lemma 4.1은 제공된 후보 집합에서 앞쪽 일부 후보가 직접 연결되거나 선택된 이웃을 통해 두 홉 안에 닿는 상황을 설명합니다. 범위는 검색이 찾아 준 후보와 한 번의 가지치기 과정입니다. 그래프 전체에서 모든 실제 최근접 이웃을 찾거나, 이후 모든 갱신 뒤에도 연결이 계속 유지된다는 뜻은 아닙니다.

3. 삽입 때는 양방향 후보를 보강합니다

새 벡터 p를 넣으면 먼저 그래프 검색으로 가까운 후보를 모으고 CRNG로 p의 outgoing 이웃을 고릅니다. 기존 이웃의 목록에도 p를 incoming 후보로 더해, 반대 방향의 접근 경로도 보강합니다. 목록의 out-degree가 상한 R을 넘으면 논문은 MRNG 방식으로 다시 가지치기합니다. p가 기존 이웃의 목록에서 빠진 경우에는 그 이웃이 앞서 가렸던 후보도 추가로 고려합니다. 이 확장은 원래 검색 후보 중 상위 β 비율로 제한하며 기본값은 0.25입니다.

그림 9. Lee와 Kim(2026), PDF p. 7(인쇄 쪽수 3363). 삽입의 outgoing 이웃 선택과 incoming 연결 보강, 삭제 주변의 재연결과 검색 중 정리를 보여 줍니다.

4. 삭제 뒤의 오래된 간선은 나중에 정리합니다

삭제할 노드 주변에서 대체 연결을 찾고, 검색으로 발견한 일부 incoming 이웃에서 삭제 노드로 가는 간선을 제거합니다. 가까운 대체 후보를 연결하고 목록이 길이 제한을 넘으면 다시 가지치기합니다. 논문은 삭제된 위치를 free pool에 돌려 새 벡터 삽입에서 재사용하는 방법도 설명합니다.

삭제된 노드를 가리키는 stale edge는 오래된 간선 참조입니다. CONDA는 그래프 전체를 즉시 훑지 않습니다. 삭제 표시를 남긴 다음, 이후 검색이 해당 노드를 만났을 때 현재 목록에서 간선을 지웁니다. 따라서 지연 삭제는 정리 비용을 없애는 대신 이후 검색과 가지치기 시점으로 나눕니다.

5. 검색 결과는 recall과 QPS를 함께 봅니다

논문은 MS Turing, MS SpaceV, Wikipedia, BIGANN, Text-to-Image의 1M(백만) 규모 자료를 평가합니다. SW는 sliding window(슬라이딩 윈도) workload이고, EX는 expiration (만료 기반 갱신) workload입니다. 여기서 churn은 삽입과 삭제로 교체되는 데이터 비율입니다. SW 조건은 시점마다 2% churn, EX는 평균 4% churn입니다. Recall@k는 실제로 가까운 정답 k개 중 검색 결과가 찾은 비율이고, QPS는 초당 질의 수입니다. Figure 11은 다섯 데이터셋에서 SW·EX 조건의 Recall@10과 QPS 관계를 나타냅니다.

그림 11. Lee와 Kim(2026), PDF p. 9(인쇄 쪽수 3365). 다섯 데이터셋의 SW·EX 조건에서 Recall@10과 QPS를 표시합니다. 검색 속도는 같은 자료와 recall 수준을 기준으로 비교합니다.

논문은 SW·EX 평균 Recall이 FreshVamana보다 각각 9.7%·9.2%, IPVamana보다 4.6%·4.0% 높다고 보고합니다. Wikipedia1M/SW의 FreshVamana 대비 24.5%는 상대 개선율이며 24.5%p 증가가 아닙니다. MS Turing 10M clustered setting에서 Recall 0.80을 맞춘 검색 QPS는 FreshVamana, IPVamana, Wolverine+, Wolverine++ 대비 1.56배, 1.42배, 1.57배, 1.47배입니다. 이 QPS는 같은 recall의 검색 처리량이지 업데이트 속도가 아닙니다.

6. 업데이트 시간은 검색 QPS와 다른 값입니다

Table 3은 MS Turing 10M·30M clustered setting의 전체 업데이트 시간을 초 단위로 보고합니다. 이 값은 검색 Recall을 맞춘 비교가 아닙니다.

데이터 크기	FreshVamana	IPVamana	Wolverine+	Wolverine++	CONDA
10M	213.0초	296.2초	238.0초	135.2초	260.3초
30M	1148.0초	1391.2초	1322.7초	528.8초	1025.4초

10M과 30M 모두 Wolverine++의 표기 업데이트 시간이 가장 짧습니다. 30M에서는 CONDA의 총 업데이트 시간이 FreshVamana보다 짧습니다. 논문은 Wolverine++의 더 빠른 업데이트와 더 낮은 검색 품질을 함께 보고합니다. 초록의 업데이트 처리량 1.90배와 결론의 평균 업데이트 시간 20.5% 감소는 서로 다른 집계값입니다. 처리량과 평균 시간은 서로 바꾸어 읽지 않습니다.

7. 동시 실행과 논문이 밝힌 한계

동시 실행 실험은 MS SpaceV 100M에서 6시간 동안 삽입·삭제·검색을 각각 5개 스레드로 수행합니다. p99는 검색 지연의 99백분위 값으로, 요청 100개 가운데 99개가 이 값 이하의 지연을 보이는 수준입니다. Figure 17은 p99와 Recall@1을 시간에 따라 보여 줍니다. 일반 실험의 주 지표 Recall@10과 달리 이 그림은 Recall@1이며, 곡선의 recall은 실험 시간 동안 감소합니다.

그림 17. Lee와 Kim(2026), PDF p. 10(인쇄 쪽수 3366). MS SpaceV 100M에서 6시간 동시 갱신·검색 중 p99 지연과 Recall@1을 나타냅니다.

저자들은 지역 검색이 일부 incoming 이웃을 놓칠 수 있고, 그러면 stale edge가 남아 장기 검색 성능에 영향을 줄 수 있다고 밝힙니다. 제한된 비용의 복구 방법과 디스크 상주 인덱스 확장은 후속 과제로 제시합니다.

참고문헌

Lee, D., & Kim, M.-S. (2026). CONDA: A connectivity-aware dynamic index for approximate nearest neighbor search over evolving data. Proceedings of the VLDB Endowment, 19(11), 3357–3370. https://doi.org/10.14778/3836663.3836694