1. 개요

Navigable Small World Graph(NSW)는 대규모 벡터 데이터에서 가까운 이웃으로 조금씩 이동하는 local link와 탐색 거리를 줄이는 long-range link를 한 그래프 안에 함께 누적해 approximate nearest neighbor를 찾는 방식입니다. 정확한 nearest neighbor를 매번 전수 계산하지 않고, 충분히 가까운 후보를 빠르게 찾는 구조를 만드는 데 초점이 있습니다.

대규모 nearest neighbor search는 추천 시스템, 이미지 검색, 의미 기반 문서 검색 등에서 반복되는 문제입니다. PQ (Product Quantization) 계열이 이 문제를 벡터를 작게 압축하는 방향에서 풀었다면, NSW와 HNSW 계열은 그래프를 따라 빠르게 탐색하는 방향에서 풉니다. Approximate nearest neighbor algorithm based on navigable small world graphs 논문(Malkov et al., 2014)은 그 출발점에 해당합니다. 후속 알고리즘인 HNSW는 별도 글에서 다룹니다.

핵심 질문은 다음과 같습니다.

• Voronoi diagram, Delaunay graph 와 Navigable small world 개념
• NSW가 Delaunay graph 근사와 navigable small world 성질을 동시에 노리는 이유
• 새 점을 가까운 이웃과 연결하는 단순한 삽입 규칙이 왜 장거리 link까지 만들어내는지
• NSW 검색 알고리즘의 구조와 실험 결과
• NSW의 한계와 후속 개선 방향

2. 필수 개념

2.1. Voronoi Diagram

점 집합이 주어졌을 때, 각 점 $p$ 의 Voronoi cell 은 다른 어떤 점보다 $p$ 에 더 가까운 모든 위치의 집합입니다. 모든 cell의 모음을 Voronoi diagram 이라고 부릅니다. 평면을 점들이 자기 담당 구역으로 나눠 가진 모습이라고 생각하면 됩니다.

Voronoi diagram. query가 속한 cell의 주인이 곧 nearest neighbor입니다.

이 정의가 그대로 nearest neighbor 검색의 본질입니다. query $q$ 의 최근접 이웃은 $q$ 가 속한 cell의 주인입니다. 따라서 NN 검색은 결국 query가 어느 Voronoi cell 안에 들어가는지를 빠르게 찾는 문제로 바꿔볼 수 있습니다.

2.2. Delaunay Graph

Delaunay graph 는 Voronoi diagram의 dual 그래프입니다. 두 점의 Voronoi cell이 edge를 공유하면, graph에서는 그 두 점을 edge로 연결합니다. 같은 정보를 공간 분할과 그래프라는 다른 시각으로 표현한 것이므로, 한쪽을 알면 다른 쪽도 결정됩니다.

Voronoi와 Delaunay의 기하학적 구성 원리. 왼쪽은 Voronoi edge가 Delaunay edge의 수직이등분선이라는 관계, 오른쪽은 외접원이 비어 있다는 조건.

첫째, Voronoi edge는 두 점을 잇는 Delaunay edge의 수직이등분선 위에 놓입니다. 두 점 A, B에서 같은 거리에 있는 위치의 자취가 곧 A·B를 가르는 Voronoi 경계이고, 같은 거리 집합은 정확히 수직이등분선입니다. 둘째, Delaunay 삼각형의 외접원 안에는 다른 점이 들어가지 않습니다(empty circumscribed circle property). 이 조건이 Delaunay triangulation을 유일하게 결정합니다.

이 구조가 ANN에서 중요한 이유는 검색 성질 때문입니다. Delaunay graph 위에서 greedy search를 돌리면 어느 진입점에서 출발하든 정확한 최근접 이웃에 도달합니다. Delaunay graph가 모든 인접 cell을 edge로 연결하므로, 현재 점보다 query에 더 가까운 cell이 남아 있는 동안은 반드시 더 가까운 이웃으로 이동할 수 있습니다.

Delaunay graph 위 greedy search 가 NN 에 도달하는 과정

Delaunay graph에서 왜 greedy search가 항상 nearest neighbor에 도달하는가?

1. 현재 노드 $p$ 의 cell 밖에 query $q$ 가 있다면, $q$ 는 다른 cell에 속합니다. Delaunay graph는 인접한 cell의 주인들을 edge로 연결하므로 $p$ 의 friend list에는 $q$ 에 더 가까운 이웃이 반드시 있습니다.
2. greedy가 멈추려면 모든 이웃이 query보다 멀어야 합니다. 이는 $q$ 가 $p$ 의 cell 안에 있을 때만 가능하고, 그때 $p$ 가 곧 $q$ 의 진짜 최근접 이웃입니다.

문제는 일반 metric space에서는 정확한 Delaunay graph를 만들 수 없다는 점입니다. 점 사이 거리만 알 뿐 좌표·차원을 몰라 외접원·수직이등분선 같은 기하학적 구성을 쓸 수 없고, 차원이 높아지면 평균 degree가 지수적으로 커질 수 있습니다. 그래서 NSW는 Delaunay graph를 직접 만드는 대신, 거리 정보만으로 Delaunay graph에 가까운 검색 성질을 만들려고 합니다.

2.3. Navigable Small World

Navigable small world(Kleinberg, 2000)는 다양한 거리 스케일의 link가 깔려 있어, greedy 방식으로도 임의의 두 노드 사이 경로를 polylog hop 안에 찾을 수 있는 네트워크입니다. 멀리 있을 때는 장거리 link로 크게 점프하고, 가까워진 뒤에는 단거리 link로 미세 조정합니다.

Navigable small world graph. greedy가 hub들을 거치며 큰 점프와 미세조정을 결합합니다.

Kleinberg가 강조한 포인트는 단순히 짧은 경로가 존재한다는 것과 지역 정보만 보고도 그 경로를 찾을 수 있다는 것이 다르다는 점입니다. NSW 논문은 이 navigability를 ANN graph 안에 만들고 싶어합니다. 다만 long-range link 분포를 명시적으로 설계하지 않고, 데이터 삽입 과정에서 자연스럽게 형성되도록 만드는 방법을 제시합니다.

3. 논문 정리

3.1. 논문 개요

논문이 등장한 시점, ANN 검색에는 다음과 같은 흐름이 있었습니다.

1. 공간 분할 기반 정확 검색: k-d tree·quad tree 같은 자료구조입니다. 저차원에서는 빠르지만 고차원에서는 worst-case가 brute-force에 가까워집니다.

2. Delaunay graph 기반 검색: Delaunay graph 위에서 greedy search와 backtracking을 수행하는 방식입니다. 검색 성질은 좋지만, 일반 metric space에서는 정확한 Delaunay graph 자체를 만들기 어렵습니다.

3. Permutation Index 계열: 기준점까지의 거리 순서를 이용해 객체를 표현하고 비교합니다. 일반 metric space·고차원에서 높은 정확도를 보였지만, 그래프 navigation 자체를 만드는 방식은 아닙니다.

4. NSW를 직접 구성하려는 시도: 격자나 유클리드 공간에서 navigable small world를 명시적으로 구성하려는 연구입니다. 다만 사전 정보나 특정 차원 구조에 의존합니다.

3.1.1. 왜 Delaunay graph를 포기하지 못하는가

Delaunay graph는 greedy search만으로 정확한 nearest neighbor에 도달할 수 있는 강력한 구조입니다. ANN graph가 이상적으로 닮고 싶은 대상에 가깝습니다. 하지만 이론적으로 좋은 구조라고 해서 실무적으로 만들 수 있는 것은 아닙니다. 일반 metric space에서는 좌표 대신 거리 함수만 주어지는 경우가 많고, 고차원에서는 Delaunay graph의 degree가 커져 저장과 탐색이 어려워집니다.

그래서 논문은 "정확한 Delaunay graph" 대신 "Delaunay graph의 검색 성질을 충분히 흉내내는 sparse graph"를 목표로 둡니다.

3.1.2. 왜 small world가 필요한가

Delaunay graph의 근사만으로는 local navigation 성질을 얻을 수 있지만, 시작점이 query에서 멀면 많은 hop이 필요할 수 있습니다. 대규모 데이터에서는 가까운 이웃으로 조금씩 이동하는 것만으로는 부족합니다. 멀리 있을 때 크게 건너뛰게 해주는 long-range link가 필요합니다.

Navigable small world의 역할이 여기서 나옵니다. long-range link가 있으면 greedy search가 처음에는 큰 폭으로 query에 가까워지고, 마지막에는 local link로 세밀하게 수렴합니다.

3.1.3. NSW의 자리: 근사 Delaunay + 자연 형성 small world

NSW는 두 요구를 하나의 그래프에 합치려고 합니다.

논문이 푸는 질문은 따라서 다음과 같이 구체화됩니다.

일반 metric space에서, 사전 정보 없이, 단순한 알고리즘으로 Delaunay graph 근사와 navigable small world graph를 동시에 만들 수 있는가?

3.2. Graph as Index

NSW는 그래프 $G(V,E)$ 를 인덱스로 사용합니다. 각 데이터 포인트가 vertex이고, edge로 연결된 이웃들은 서로의 friend list에 들어갑니다. 검색은 별도 트리나 해시 테이블을 타는 것이 아니라, 이 friend list를 따라 query에 가까워지는 방향으로 이동하는 방식입니다.

이때 그래프는 두 성질을 동시에 가져야 합니다.

• query 근처에서는 충분한 local link가 있어야 합니다. 그래야 false local minimum에 덜 빠집니다.
• query와 멀리 떨어져 있을 때는 long-range link가 있어야 합니다. 그래야 많은 노드를 하나씩 거치지 않습니다.

흥미로운 점은 NSW가 이 둘을 별도의 규칙으로 만들지 않는다는 것입니다. 하나의 단순한 삽입 규칙에서 short-range link와 long-range link가 동시에 형성됩니다.

NSW의 핵심은 "좋은 edge를 정교하게 설계한다"가 아닙니다. 새 데이터가 들어올 때 현재 그래프에서 가까운 이웃을 찾고 연결한 뒤, 그 연결을 시간이 지나도 보존하는 것입니다.

3.3. 삽입 규칙: 두 종류 link 의 동시 형성

삽입 규칙은 단순합니다. 새 원소가 들어오면 현재 구조에서 가장 가까운 $f$ 개 이웃을 찾아 양방향으로 연결합니다.

이 규칙은 아주 단순하지만 두 가지 효과를 동시에 만듭니다.

공간적 효과: 새 원소를 현재 시점의 가까운 이웃과 연결합니다. 이 edge는 처음 만들어질 때 local link입니다. 가까운 점들끼리 연결되므로 Delaunay graph의 인접 관계를 근사하는 방향으로 작동합니다.

시간적 효과: 데이터셋이 커지면 같은 edge 주변에 더 가까운 점들이 나중에 생깁니다. 그런데 NSW는 기존 edge를 지우거나 더 가까운 edge로 교체하지 않습니다. 그래서 처음에는 local link였던 edge가 시간이 지나며 상대적으로 long-range link가 됩니다.

이게 NSW의 가장 중요한 발상입니다. 오래된 link를 보존하는 것이 단순한 구현 편의가 아니라 small world navigation을 만드는 메커니즘입니다.

3.4. 단거리 link 가 Delaunay graph 를 근사하는 원리

NSW의 short-range link는 "한 점의 Voronoi 이웃 집합"과 "그 점의 $f$ 개 최근접 이웃 집합"이 큰 교집합을 가진다는 관찰에 근거합니다. Voronoi 이웃은 cell이 인접한 점들이고, 인접한 cell의 주인들은 대체로 서로 가깝습니다. 따라서 가장 가까운 $f$ 개를 고르는 것은 Voronoi 이웃을 근사하는 것과 같습니다.

물론 이 근사는 완벽하지 않습니다. $f$ 가 너무 작으면 필요한 이웃을 놓치고, 너무 크면 그래프가 조밀해져 메모리와 탐색 비용이 올라갑니다. NSW는 이 trade-off를 받아들이고, 정확한 Delaunay graph 대신 sparse한 근사 graph를 만듭니다.

3.5. 장거리 link 가 자연적으로 형성되는 원리

NSW의 link evolution. 같은 A-B 링크가 데이터셋 성장에 따라 단거리에서 장거리로 변합니다.

데이터셋이 작을 때(T1) 삽입된 A-B link는 단거리입니다. 하지만 데이터셋이 커지면서(T3) A 주변에 더 가까운 점들이 생깁니다. 이때 NSW가 A-B link를 지우지 않으면, 같은 edge가 상대적으로 장거리 link로 바뀝니다.

이 일이 그래프 전체에서 반복되면 초기 노드들은 다양한 거리 스케일의 link를 누적합니다. 자연스럽게 degree가 높은 hub가 생기고, greedy search는 hub를 거치며 큰 점프와 미세조정을 결합합니다. 명시적으로 설계해야 했던 long-range link 분포가 삽입 순서의 무작위성에서 자동 형성되는 셈입니다.

3.6. Delaunay graph 와 NSW 를 깨뜨리지 않으려면

이 구조가 잘 작동하려면 두 조건이 중요합니다.

무작위 삽입 순서가 필요합니다. 가까운 점끼리 묶어서 순서대로 삽입하면 "오래된 link = 상대적으로 먼 link"라는 관계가 잘 생기지 않습니다. 데이터가 특정 영역에서 다른 영역으로 시간순 확장되는 경우도 같은 문제가 생길 수 있습니다.

오래된 link를 보존해야 합니다. "이제는 멀어 보이니 가까운 점으로 바꾸자"는 갱신을 하면 NSW의 핵심을 지우는 셈입니다. 멀어 보이는 link가 곧 small world navigation을 가능하게 하는 장거리 link입니다. 이것이 단순 k-NN graph와 NSW의 결정적인 차이입니다.

4. 논문 알고리즘

NSW의 search와 insertion은 사실상 같은 탐색 루틴을 공유합니다. 먼저 graph 위에서 query에 가까운 후보를 찾고, 삽입할 때는 새 원소를 query처럼 취급해 가까운 이웃들과 연결합니다.

4.1. Search Algorithm

2.2절에서 정확한 Delaunay graph 위 greedy search는 항상 nearest neighbor에 도달한다고 봤습니다. 하지만 NSW는 근사 그래프입니다. 따라서 현재 노드의 모든 이웃이 query보다 멀어 보이지만, 그래프 어딘가에는 더 가까운 점이 있는 false global minimum이 생길 수 있습니다.

가장 단순한 greedy search는 다음과 같습니다.

Greedy_Search(q: object, v_entry_point: object)
1   v_curr ← v_entry_point;
2   δ_min ← δ(q, v_curr); v_next ← NIL;
3   foreach v_friend ∈ v_curr.getFriends() do
4       δ_fr ← δ(q, v_friend)
5       if δ_fr < δ_min then
6           δ_min ← δ_fr;
7           v_next ← v_friend;
8   if v_next = NIL then return v_curr;
9   else return Greedy_Search(q, v_next);

K-NN 검색은 이 단순 greedy를 두 가지 방식으로 보완합니다. 첫째, top-k 후보가 더 이상 개선되지 않을 때까지 후보 집합을 확장합니다. 둘째, false global minimum을 완화하기 위해 서로 다른 무작위 진입점에서 $m$ 번 검색합니다. 다만 visitedSet을 공유해 같은 노드를 중복 평가하지 않습니다.

K-NNSearch(q: object, m: integer, k: integer)
1   TreeSet[object] tempRes, candidates, visitedSet, result
2   for (i ← 0; i < m; i++) do:
3       put random entry point in candidates
4       tempRes ← null
5       repeat:
6           get element c closest from candidates to q
7           remove c from candidates
8           if c is further than k-th element from result then break repeat
9           for every element e from friends of c do:
10              if e is not in visitedSet then add e to visitedSet, candidates, tempRes
11      end repeat
12      add objects from tempRes to result
13  end for
14  return best k elements from result

m=3 multi-search. 서로 다른 진입점에서 시작한 3번의 검색이 visitedSet을 공유합니다.

정확도는 검색 시점에 조절합니다. recall이 필요하면 $m$ 을 키우고, 속도가 더 중요하면 $m$ 을 줄입니다. 이 점은 인덱스를 다시 만들지 않고도 검색 품질과 속도를 조절할 수 있다는 뜻입니다.

4.2. Insertion Algorithm

삽입은 더 단순합니다. 새 원소를 query처럼 보고, 현재 graph에서 가까운 $f$ 개 이웃을 찾은 뒤 양방향으로 연결합니다.

Nearest_Neighbor_Insert(new_object: object, f: integer, w: integer)
1   SET[object]: neighbors ← K-NNSearch(new_object, w, f);
2   for (i ← 0; i < f; i++) do
3       neighbors[i].connect(new_object);
4       new_object.connect(neighbors[i]);

Insertion의 3단계. (1) 새 원소 도착 (2) K-NNSearch로 가까운 f개 찾기 (3) 양방향 연결.

이 구조의 장점은 구현 단순성입니다.

• 사전 정보 불필요: 좌표·차원·분포를 몰라도 거리 함수만 있으면 됩니다.
• 점진적(incremental): 데이터가 하나씩 들어와도 인덱스를 계속 확장할 수 있습니다.
• 자연스러운 병렬화: 지역 정보만 사용하므로 동기화 부담이 작습니다.
• 분산 가능성: friend list만 따라가면 검색되므로 graph를 분산 저장하기 쉽습니다.

4.3. 파라미터의 의미

논문에서 중요한 파라미터는 $f$, $w$, $m$ 입니다.

파라미터 $w$ 는 삽입 시 검색 정확도를 결정하며, 논문은 삽입 recall 0.95~0.99 수준을 권장합니다. 데이터셋이 커질수록 필요한 $w$ 는 logarithmic 하게 증가합니다.

5. 논문 실험 결과

논문은 synthetic 데이터와 실제 이미지 feature 데이터셋에서 NSW가 navigable small world 성질을 실제로 보이는지, 그리고 기존 ANN 알고리즘 대비 거리 계산을 얼마나 줄이는지 확인합니다.

5.1. Small World Navigation 성질

NSW graph 위 greedy search의 평균 hop 수를 데이터셋 크기에 대해 측정했습니다($k=10, w=20, f=3d$).

Average hop count for different dimensionality Euclidean data (k=10, w=20)

hop 수는 데이터셋 크기에 대해 로그적으로 증가합니다. 이는 NSW가 navigable small world 성질을 가진다는 핵심 근거입니다. 차원이 커질수록 의존성이 약해지는데, 논문은 greedy search가 long-range link를 만나면 query에 가까운 방향만 선택하므로 검색이 quasi 1차원적으로 동작하기 때문이라고 설명합니다.

5.2. 분산 / 병렬 처리

NSW는 연결만으로 표현되는 독립 객체들의 graph라 분산이 쉽습니다. 4-node cluster($d=1$)에서 core 수에 거의 선형적인 throughput 확장을 보였고, $d=10$ 조건에서 첫 1000개를 직렬 삽입한 뒤 16-thread 병렬 삽입을 해도 정확도 저하가 없었습니다. 즉 추가 동기화 로직 없이 대규모 병렬 삽입이 가능합니다.

5.3. 검색 복잡도 스케일링

recall 0.999 고정, 데이터셋 크기를 키우며 평가한 점의 비율을 측정($d=3 \sim 50, k=10$, 20,000 query)했습니다.

Average fraction of visited elements (0.999 recall) vs dataset size

데이터셋이 커질수록 평가 비율은 오히려 줄고, log-log plot에서는 직선(power-law decay)에 가까워집니다. 고정 정확도에서 전체 데이터 중 평가해야 하는 비율이 점점 작아진다는 의미입니다.

Distance calculations and m for 0.999 recall vs dataset size (d=20)

거리 계산 횟수는 $C \log^2(n)$ 으로 증가합니다. 두 $\log$ 중 하나는 평균 hop 수($\log n$), 다른 하나는 필요한 multi-search 횟수 $m$($\log n$)에서 옵니다.

5.4. 차원 스케일링

약 2200만 개 데이터로 차원별 평가 비율을 측정(recall 0.999, $k=10$)했습니다.

Average fraction of visited elements for ~22M elements

곡선에서 plateau(최적 차원 영역)가 관찰됩니다. 차원이 너무 작으면 small world navigation 효과가 약하고, 너무 크면 차원의 저주가 시작됩니다. 그 사이에 안정적으로 좋은 영역이 존재하며, 위치는 데이터셋 크기에 따라 약간 이동합니다.

5.5. CoPHiR 데이터셋 성능

CoPHiR는 1000만 개 실제 이미지의 208차원 feature 벡터 데이터셋입니다($k=30$, L1, 10만 query). 실험은 16-thread로 약 2시간 소요됐습니다.

Average fraction of visited vs recall error for 10M 208-dim CoPHiR

recall 0.999에서 데이터의 0.031%만 평가하면 됩니다. 그런데도 brute-force와 거의 같은 정확도입니다.

5.6. 다른 알고리즘과의 비교

Permutation Index 계열 두 알고리즘과 비교합니다 — NAPP(Neighborhood Approximation), OP(Ordering Permutation).

Average fraction of visited vs recall error for 10M CoPHiR

CoPHiR(10M, 208d)에서 NAPP(K=7) 대비 NSW는 recall 0.999에서 100배 이상 적은 거리 계산을 씁니다. 다만 데이터 수가 작고($10^4$) 차원이 매우 높은(d=1024) 경우, NSW는 recall 0.9에 약 65%를 평가해야 했고 OP는 42%로 가능했습니다.

이 비교가 보여주는 것은 분명합니다. NSW의 강점은 큰 데이터셋과 navigable small world가 잘 형성되는 조건에서 두드러집니다. 반대로 데이터가 작거나 차원이 지나치게 높아 graph navigation의 이점이 약해지는 조건에서는 다른 방식이 나을 수 있습니다.

6. NSW 의 한계와 개선 방향

NSW는 아이디어가 단순하고 강력하지만, 그 단순함 때문에 생기는 한계도 분명합니다.

6.1. 한계

6.1.1. 무작위 삽입 순서에 의존

NSW의 long-range link는 삽입 순서에서 자연스럽게 생깁니다. 따라서 삽입 순서가 무작위에 가깝다는 가정이 중요합니다. 데이터가 시간순으로 특정 영역에서 다른 영역으로 확장되거나, 가까운 점들이 묶여서 들어오면 "오래된 link가 장거리 link가 된다"는 성질이 약해집니다.

6.1.2. 삭제와 동적 갱신에 약함

NSW는 오래된 link를 보존해야 small world 성질이 유지됩니다. 그런데 실제 시스템에서는 삭제, 업데이트, 재삽입이 발생합니다. 노드를 삭제하면 그 노드가 제공하던 long-range shortcut도 함께 사라지고, 이를 어떻게 복구할지 명확하지 않습니다.

6.1.3. 작은 데이터셋 + 매우 고차원에서 불리

CoPHiR처럼 큰 데이터셋에서는 강점이 뚜렷했지만, $10^4$ 개 규모에 d=1024인 조건에서는 OP보다 뒤처졌습니다(65% 평가 vs 42% 평가). 데이터가 충분히 크지 않으면 small world 구조가 풍부하게 형성되기 어렵고, 차원이 지나치게 높으면 거리 자체의 구분력이 약해집니다.

6.1.4. 적용 범위가 경험적으로 남아 있음

논문은 일반 metric space에서 동작하는 접근을 제안하지만, 어떤 데이터 분포에서 안정적으로 잘 되는지에 대한 이론적 경계는 명확하지 않습니다. 따라서 실무에서는 데이터셋 크기, 차원, 거리 함수, 삽입 순서에 따라 별도 검증이 필요합니다.

6.2. 개선 방향

6.2.1. neighbor selection을 더 정교하게 만들기

NSW의 삽입은 가까운 $f$ 개 이웃을 고르는 방식입니다. 이 방식은 단순하지만, 후보들 사이의 거리나 방향 다양성을 고려하지 않습니다. 가까운 이웃만 많이 고르면 비슷한 방향의 edge가 중복될 수 있습니다. 같은 friend 수를 쓰더라도 더 다양한 방향의 이웃을 고르면 graph 품질을 높일 수 있습니다.

6.2.2. small world 형성을 자연 발생에만 맡기지 않기

NSW는 long-range link 형성을 삽입 순서에 맡깁니다. 더 안정적인 구조를 만들려면 거리 스케일별 link를 명시적으로 관리하거나, 계층적 구조를 도입하는 방향을 생각할 수 있습니다. 후속 HNSW가 바로 이 질문을 더 발전시킨 알고리즘입니다.

6.2.3. multi-search 관리 비용 줄이기

검색 시 visitedSet, 후보 우선순위 큐, top-k 결과 집합을 계속 관리해야 합니다. recall을 높이려고 $m$ 을 키우면 이 관리 비용도 함께 늘어납니다. 같은 정확도에서 더 적은 entry point를 쓰거나, 후보 확장 순서를 더 효율적으로 잡는 것이 개선 포인트가 됩니다.

정리하면, NSW는 "단순한 삽입 규칙으로 좋은 graph가 자연스럽게 생긴다"는 점이 강점입니다. 동시에 그 자연 형성에 의존하기 때문에 삽입 순서, 삭제, 동적 업데이트에는 구조적으로 취약합니다.

7. 마무리

NSW는 Delaunay graph의 검색 정확성과 navigable small world의 검색 효율성을 하나의 graph 안에 담으려는 알고리즘입니다. 새 점을 현재 graph의 가까운 이웃들과 연결하는 단순한 규칙으로 local link를 만들고, 그 link를 오래 보존함으로써 시간이 지나면 long-range link까지 자연스럽게 얻습니다.

이 관점은 이후 그래프 기반 ANN 알고리즘의 중요한 출발점이 됩니다. 특히 HNSW를 이해하려면 NSW가 먼저 해결하려고 한 문제가 무엇이었는지, 그리고 무엇이 부족했는지를 이해하는 것이 좋습니다. HNSW의 계층 구조는 결국 NSW가 가진 "장거리 navigation을 더 안정적으로 만들고 싶다"는 문제의식 위에 올라갑니다.

8. 참고문헌

• Approximate nearest neighbor algorithm based on navigable small world graphsdoi.org
• The small-world phenomenon: an algorithmic perspectivedoi.org