1. Overview

Navigable Small World Graph (NSW) is an approach that finds approximate nearest neighbors by accumulating, in a single graph, local links that move step by step toward nearby neighbors and long-range links that shrink the search distance over large-scale vector data. Instead of exhaustively computing the exact nearest neighbor every time, the focus is on building a structure that quickly finds candidates that are close enough.

Large-scale nearest neighbor search is a recurring problem in recommender systems, image search, semantic document retrieval, and more. Where the PQ (Product Quantization) family attacks this problem by compressing vectors into a small form, the NSW and HNSW family attacks it by navigating quickly along a graph. The Approximate nearest neighbor algorithm based on navigable small world graphs paper (Malkov et al., 2014) is the starting point of that line. The follow-up algorithm HNSW is covered in a separate post.

The key questions are as follows.

• The concepts of Voronoi diagram, Delaunay graph, and Navigable small world
• Why NSW aims for a Delaunay graph approximation and the navigable small world property at the same time
• Why a simple insertion rule that connects a new point to its nearby neighbors ends up creating long-range links as well
• The structure of the NSW search algorithm and the experimental results
• The limitations of NSW and directions for follow-up improvements

2. Essential Concepts

2.1. Voronoi Diagram

Given a set of points, the Voronoi cell of each point $p$ is the set of all locations that are closer to $p$ than to any other point. The collection of all cells is called the Voronoi diagram. Think of it as the plane divided up among the points, each claiming its own territory.

Voronoi diagram. The owner of the cell containing the query is the nearest neighbor.

This definition is exactly the essence of nearest neighbor search. The nearest neighbor of a query $q$ is the owner of the cell that $q$ falls into. So NN search can be reframed as the problem of quickly finding which Voronoi cell the query lands in.

2.2. Delaunay Graph

The Delaunay graph is the dual graph of the Voronoi diagram. If the Voronoi cells of two points share an edge, the graph connects those two points with an edge. It is the same information expressed from two different viewpoints — space partitioning and graph — so knowing one determines the other.

The geometric construction principles of Voronoi and Delaunay. Left: the relationship where a Voronoi edge is the perpendicular bisector of a Delaunay edge; right: the condition that the circumscribed circle is empty.

First, a Voronoi edge lies on the perpendicular bisector of the Delaunay edge connecting two points. The locus of positions equidistant from two points A and B is precisely the Voronoi boundary separating A and B, and that equidistant set is exactly the perpendicular bisector. Second, no other point falls inside the circumscribed circle of a Delaunay triangle (empty circumscribed circle property). This condition uniquely determines the Delaunay triangulation.

The reason this structure matters for ANN is its search property. Running greedy search on a Delaunay graph reaches the exact nearest neighbor no matter which entry point you start from. Because the Delaunay graph connects every pair of adjacent cells with an edge, as long as there remains a cell closer to the query than the current point, you can always move to a closer neighbor.

The process by which greedy search on a Delaunay graph reaches the NN

Why does greedy search on a Delaunay graph always reach the nearest neighbor?

1. If the query $q$ lies outside the cell of the current node $p$, then $q$ belongs to another cell. Since the Delaunay graph connects the owners of adjacent cells with edges, the friend list of $p$ is guaranteed to contain a neighbor closer to $q$.
2. For greedy to stop, every neighbor must be farther from the query. That is only possible when $q$ lies inside the cell of $p$, and at that point $p$ is exactly the true nearest neighbor of $q$.

The problem is that in a general metric space you cannot build the exact Delaunay graph. You only know pairwise distances — without coordinates or dimensionality you cannot use geometric constructions like circumscribed circles or perpendicular bisectors, and as dimensionality grows the average degree can blow up exponentially. So instead of building the Delaunay graph directly, NSW tries to produce search properties close to the Delaunay graph using distance information alone.

2.3. Navigable Small World

A Navigable small world (Kleinberg, 2000) is a network in which links across a variety of distance scales are laid out, so that even a greedy strategy can find a path between any two nodes within polylog hops. When far away, it jumps far using long-range links; once close, it fine-tunes with short-range links.

Navigable small world graph. Greedy passes through hubs, combining big jumps with fine adjustments.

The point Kleinberg emphasized is that a short path exists is not the same as the path can be found using only local information. The NSW paper wants to build this navigability into an ANN graph. Rather than explicitly designing the long-range link distribution, however, it presents a way for it to form naturally during data insertion.

3. Paper Walkthrough

3.1. Paper Overview

At the time the paper appeared, ANN search had the following major threads.

1. Exact search based on space partitioning: data structures like the k-d tree and quad tree. Fast in low dimensions, but in high dimensions the worst case approaches brute-force.

2. Delaunay-graph-based search: performing greedy search with backtracking on a Delaunay graph. The search properties are good, but in a general metric space the exact Delaunay graph itself is hard to build.

3. The Permutation Index family: representing and comparing objects using the order of distances to reference points. It showed high accuracy in general metric spaces and high dimensions, but it is not an approach that builds graph navigation itself.

4. Attempts to construct an NSW directly: research that explicitly constructs a navigable small world on lattices or in Euclidean space. However, these depend on prior information or specific dimensional structure.

3.1.1. Why the Delaunay graph cannot be given up

The Delaunay graph is a powerful structure in which greedy search alone reaches the exact nearest neighbor. It is close to the ideal that an ANN graph would like to resemble. But a structure being theoretically good does not mean it can be built in practice. In a general metric space you are often given only a distance function instead of coordinates, and in high dimensions the degree of the Delaunay graph grows, making storage and traversal difficult.

So instead of the "exact Delaunay graph", the paper sets its goal as a "sparse graph that mimics the search properties of the Delaunay graph well enough".

3.1.2. Why a small world is needed

An approximation of the Delaunay graph alone gives you local navigation, but if the starting point is far from the query, many hops may be needed. At large scale, moving step by step toward nearby neighbors is not enough. You need long-range links that let you leap far when you are far away.

This is where the role of the navigable small world comes in. With long-range links, greedy search first closes in on the query in large strides, and at the end converges precisely via local links.

3.1.3. NSW's position: approximate Delaunay + naturally formed small world

NSW tries to combine the two requirements into a single graph.

The question the paper solves is therefore made concrete as follows.

In a general metric space, with no prior information, can a simple algorithm build a Delaunay graph approximation and a navigable small world graph at the same time?

3.2. Graph as Index

NSW uses a graph $G(V,E)$ as the index. Each data point is a vertex, and neighbors connected by edges appear in each other's friend list. Search does not go through a separate tree or hash table; it moves along these friend lists in the direction that gets closer to the query.

The graph must have two properties at once.

• Near the query, there must be enough local links. That keeps it from falling into false local minima as often.
• Far from the query, there must be long-range links. That keeps it from having to pass through many nodes one at a time.

The interesting part is that NSW does not create these two with separate rules. Short-range links and long-range links form simultaneously from one simple insertion rule.

The core of NSW is not "carefully engineer good edges". It is finding and connecting nearby neighbors in the current graph when new data arrives, and then preserving those connections over time.

3.3. Insertion Rule: Simultaneous Formation of Two Kinds of Links

The insertion rule is simple. When a new element arrives, find its $f$ closest neighbors in the current structure and connect them bidirectionally.

This rule is very simple, yet it produces two effects at once.

Spatial effect: the new element is connected to its neighbors that are close at the current moment. When first created, these edges are local links. Since nearby points get connected to each other, this works in the direction of approximating the adjacency relations of the Delaunay graph.

Temporal effect: as the dataset grows, points closer than an existing edge appear around it later. But NSW does not delete existing edges or replace them with closer ones. So an edge that started out as a local link becomes, over time, a relatively long-range link.

This is the most important idea in NSW. Preserving old links is not mere implementation convenience — it is the mechanism that creates small world navigation.

3.4. How Short-Range Links Approximate the Delaunay Graph

NSW's short-range links rest on the observation that "the set of a point's Voronoi neighbors" and "the set of that point's $f$ nearest neighbors" have a large intersection. Voronoi neighbors are the points whose cells are adjacent, and the owners of adjacent cells are generally close to each other. So picking the $f$ closest points amounts to approximating the Voronoi neighbors.

Of course, this approximation is not perfect. If $f$ is too small you miss necessary neighbors; if it is too large the graph becomes dense and memory and traversal costs rise. NSW accepts this trade-off and builds a sparse approximate graph instead of the exact Delaunay graph.

3.5. How Long-Range Links Form Naturally

NSW's link evolution. The same A-B link changes from short-range to long-range as the dataset grows.

When the dataset is small (T1), the inserted A-B link is short-range. But as the dataset grows (T3), closer points appear around A. If NSW does not delete the A-B link, the same edge turns into a relatively long-range link.

When this repeats across the whole graph, early nodes accumulate links across a variety of distance scales. High-degree hubs emerge naturally, and greedy search passes through the hubs, combining big jumps with fine adjustments. The long-range link distribution that would have had to be designed explicitly forms automatically from the randomness of the insertion order.

3.6. What It Takes Not to Break the Delaunay Graph and the NSW

For this structure to work well, two conditions matter.

A random insertion order is needed. If nearby points are grouped together and inserted in order, the relation "old link = relatively far link" does not form well. The same problem can occur when data expands chronologically from one region to another.

Old links must be preserved. Updating with "this one looks far now, so swap it for a closer point" erases the very core of NSW. The links that look far are exactly the long-range links that make small world navigation possible. This is the decisive difference between a plain k-NN graph and NSW.

4. Paper Algorithms

NSW's search and insertion effectively share the same traversal routine. First, find candidates close to the query on the graph; when inserting, treat the new element like a query and connect it to its nearby neighbors.

4.1. Search Algorithm

In section 2.2 we saw that greedy search on the exact Delaunay graph always reaches the nearest neighbor. But NSW is an approximate graph. So a false global minimum can occur, where every neighbor of the current node looks farther than the query even though a closer point exists somewhere in the graph.

The simplest greedy search looks like this.

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 search complements this plain greedy in two ways. First, it expands the candidate set until the top-k candidates stop improving. Second, to mitigate false global minima, it searches $m$ times from different random entry points. However, a shared visitedSet ensures the same node is not evaluated more than once.

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. Three searches started from different entry points share the visitedSet.

Accuracy is tuned at search time. If you need recall, increase $m$; if speed matters more, decrease $m$. This means search quality and speed can be adjusted without rebuilding the index.

4.2. Insertion Algorithm

Insertion is even simpler. Treat the new element like a query, find its $f$ closest neighbors in the current graph, then connect them bidirectionally.

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]);

The three steps of insertion. (1) New element arrives (2) Find the f closest via K-NNSearch (3) Connect bidirectionally.

The strength of this structure is implementation simplicity.

• No prior information needed: a distance function is all it takes — no coordinates, dimensionality, or distribution.
• Incremental: the index can keep growing even as data arrives one item at a time.
• Naturally parallelizable: only local information is used, so synchronization overhead is small.
• Distributable: since search only follows friend lists, the graph is easy to store in a distributed way.

4.3. What the Parameters Mean

The important parameters in the paper are $f$, $w$, and $m$.

Parameter $w$ determines the search accuracy at insertion time, and the paper recommends an insertion recall level of 0.95–0.99. As the dataset grows, the required $w$ increases logarithmically.

5. Experimental Results

The paper checks, on synthetic data and a real image feature dataset, whether NSW actually exhibits the navigable small world property, and how much it reduces distance computations compared to existing ANN algorithms.

5.1. Small World Navigation Property

The average hop count of greedy search on the NSW graph was measured against dataset size ($k=10, w=20, f=3d$).

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

The hop count grows logarithmically with dataset size. This is the core evidence that NSW has the navigable small world property. The dependence weakens as dimensionality grows; the paper explains that when greedy search encounters a long-range link it only picks the direction closer to the query, so the search behaves quasi one-dimensionally.

5.2. Distributed / Parallel Processing

NSW is a graph of independent objects expressed only through connections, so it distributes easily. On a 4-node cluster ($d=1$) it showed nearly linear throughput scaling with core count, and under $d=10$, inserting the first 1000 elements serially and then doing 16-thread parallel insertion caused no accuracy degradation. In other words, large-scale parallel insertion is possible without extra synchronization logic.

5.3. Search Complexity Scaling

With recall fixed at 0.999, the fraction of points evaluated was measured while growing the dataset size ($d=3 \sim 50, k=10$, 20,000 queries).

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

As the dataset grows, the fraction evaluated actually shrinks, and on a log-log plot it approaches a straight line (power-law decay). It means that at fixed accuracy, the fraction of the whole dataset that must be evaluated keeps getting smaller.

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

The number of distance computations grows as $C \log^2(n)$. Of the two $\log$ factors, one comes from the average hop count ($\log n$) and the other from the required number of multi-searches $m$ ($\log n$).

5.4. Dimensionality Scaling

With about 22 million data points, the evaluated fraction was measured per dimensionality (recall 0.999, $k=10$).

Average fraction of visited elements for ~22M elements

A plateau (an optimal dimensionality region) is observed in the curve. If the dimensionality is too small, the small world navigation effect is weak; if it is too large, the curse of dimensionality kicks in. In between, a stably good region exists, and its position shifts slightly with dataset size.

5.5. Performance on the CoPHiR Dataset

CoPHiR is a dataset of 208-dimensional feature vectors from 10 million real images ($k=30$, L1, 100K queries). The experiment took about 2 hours with 16 threads.

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

At recall 0.999, only 0.031% of the data needs to be evaluated. And yet the accuracy is nearly identical to brute-force.

5.6. Comparison with Other Algorithms

It is compared against two algorithms from the Permutation Index family — NAPP (Neighborhood Approximation) and OP (Ordering Permutation).

Average fraction of visited vs recall error for 10M CoPHiR

On CoPHiR (10M, 208d), compared to NAPP (K=7), NSW uses over 100 times fewer distance computations at recall 0.999. However, when the data count is small ($10^4$) and the dimensionality is very high (d=1024), NSW had to evaluate about 65% for recall 0.9 while OP managed with 42%.

What this comparison shows is clear. NSW's strength stands out on large datasets and under conditions where a navigable small world forms well. Conversely, when the data is small or the dimensionality is so high that the benefit of graph navigation weakens, other approaches can be better.

6. Limitations of NSW and Directions for Improvement

NSW's idea is simple and powerful, but that very simplicity produces clear limitations.

6.1. Limitations

6.1.1. Dependence on random insertion order

NSW's long-range links arise naturally from the insertion order. So the assumption that the insertion order is close to random matters. If data expands chronologically from one region to another, or nearby points arrive grouped together, the property "old links become long-range links" weakens.

6.1.2. Weak against deletion and dynamic updates

NSW must preserve old links to maintain the small world property. But real systems experience deletions, updates, and re-insertions. Deleting a node also removes the long-range shortcuts it provided, and how to restore them is not clear.

6.1.3. Disadvantaged on small datasets with very high dimensionality

On large datasets like CoPHiR the strengths were evident, but under $10^4$-scale data with d=1024 it fell behind OP (65% evaluated vs 42% evaluated). If the data is not large enough, a rich small world structure is hard to form, and if the dimensionality is excessively high, the discriminative power of distance itself weakens.

6.1.4. The scope of applicability remains empirical

The paper proposes an approach that works in general metric spaces, but the theoretical boundaries of which data distributions it works reliably on are not clear. So in practice, separate validation is needed depending on dataset size, dimensionality, distance function, and insertion order.

6.2. Directions for Improvement

6.2.1. Making neighbor selection more sophisticated

NSW's insertion picks the $f$ closest neighbors. This is simple, but it does not consider the distances among candidates or the diversity of directions. Picking only many close neighbors can produce redundant edges in similar directions. Even with the same friend count, choosing neighbors in more diverse directions can improve graph quality.

6.2.2. Not leaving small world formation entirely to natural emergence

NSW leaves long-range link formation to the insertion order. To build a more stable structure, one can think of explicitly managing links per distance scale, or introducing a hierarchical structure. The follow-up HNSW is precisely the algorithm that develops this question further.

6.2.3. Reducing the management cost of multi-search

During search, the visitedSet, the candidate priority queue, and the top-k result set must be continuously maintained. Increasing $m$ to raise recall increases this management cost too. Using fewer entry points at the same accuracy, or ordering candidate expansion more efficiently, become the improvement points.

To sum up, NSW's strength is that "a good graph emerges naturally from a simple insertion rule". At the same time, because it depends on that natural formation, it is structurally vulnerable to insertion order, deletion, and dynamic updates.

7. Wrapping Up

NSW is an algorithm that tries to pack the search accuracy of the Delaunay graph and the search efficiency of the navigable small world into a single graph. A simple rule that connects a new point to its nearby neighbors in the current graph creates local links, and by preserving those links for a long time, it naturally gains long-range links as time passes.

This perspective becomes an important starting point for later graph-based ANN algorithms. In particular, to understand HNSW, it helps to understand what problem NSW set out to solve first, and what it lacked. HNSW's hierarchical structure ultimately builds on NSW's underlying concern: "we want to make long-range navigation more reliable".

8. References

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