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에서 출발해 삽입 규칙, 실험, 한계까지, 이 리뷰가 짚는 것은 다섯 가지다.

• 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가 장거리 link로 크게 점프한 뒤 단거리 link로 미세조정한다.

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

3. 논문 정리

3.1. 논문 개요

논문이 나온 2014년 무렵, 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가 곧 long-range link가 되고, 이 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를 누적하고, greedy search는 장거리 link로 크게 점프한 뒤 단거리 link로 미세조정한다. 명시적으로 설계해야 했던 long-range link 분포가 삽입 순서의 무작위성에서 자동으로 형성되는 셈이다.

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

이 구조가 잘 작동하려면 두 조건이 지켜져야 한다.

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

오래된 link를 보존해야 한다. "이제는 멀어 보이니 가까운 점으로 바꾸자"는 갱신을 하는 순간 small world navigation을 만들던 장거리 link가 사라진다. 매 시점 최근접 이웃만 유지하는 단순 k-NN graph에는 그래서 단거리 link만 남고, 오래된 link를 남겨두는 NSW에는 장거리 link가 쌓인다.

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(friend list를 이미 읽은 노드 집합)을 검색 전체에서 공유해, 같은 노드를 다시 확장하지 않는다. 무작위 진입점만은 이 검사 없이 candidates에 들어간다.

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(최적 차원 영역)가 관찰되며, 위치는 데이터셋 크기에 따라 약간 이동한다. 논문은 이 이동을 고차원에서 greedy 경로가 짧아지는 효과로 추정한다.

5.5. CoPHiR 데이터셋 성능

실험에는 CoPHiR 컬렉션에서 추출한 1000만 개 subset(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%로 충분했다.

강점과 약점은 결국 navigable small world가 충분히 형성되느냐에서 갈린다. 1000만 개 CoPHiR처럼 그래프가 풍부하게 만들어지는 큰 데이터셋에서는 NSW가 앞서고, $10^4$ 개에 d=1024처럼 데이터가 작고 차원이 아주 높은 조건에서는 permutation 계열이 낫다.

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