Small World Graph

유사한 노드끼리만 엣지를 생성한 그래프

Navigable

여러 Small World를 엣지로 연결해주어 서로 탐색이 가능하다.

벡터를 그래프의 node로 표현하고 인접한 벡터를 edge로 연결

Layer를 여러 개 만들어 계층적으로 탐색을 진행 ⇒ search 속도 향상

Layer 0에 모든 노드가 존재, 최상위 Layer로 갈수록 개수가 적음 (랜덤 샘플링)

작동 방식

1. 최상위 Layer에서 임의의 노드에서 시작
2. 현재 Layer에서 타겟 노드와 가장 가까운 노드로 이동
3. 현재 Layer에서 더 가까워 질 수 없다면 하위 Layer로 이동
4. 타겟 노드에 도착할 때까지 2)와 3) 반복
5. ~ 4)를 진행할 때 방문했던(traverse) 노드들만 후보로 하여 NN을 탐색

대표 라이브러리: nmslib, faiss