Papers
Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs
Yu. A. Malkov, D. A. Yashunin · IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI); preprint arXiv:1603.09320, 2018
The problem: nearest-neighbor search at scale
K-nearest-neighbor search (K-NNS) starts from a distance function between elements and looks, in the stored set, for the K elements closest to a query. It appears in applications such as nonparametric machine learning, image feature matching in large databases, and semantic document retrieval. The naive approach computes the distance from the query to all elements, so the cost grows linearly with the size of the dataset, which makes large sets infeasible. Exact solutions only bring a substantial speedup when the data has few dimensions, because of the so-called curse of dimensionality. The way out is approximate search (K-ANNS), which accepts a small number of errors in exchange for speed. The quality of an inexact search is measured by recall: the ratio between the true neighbors found and K. The paper lists as popular K-ANNS families the approximate versions of tree-based algorithms, locality-sensitive hashing (LSH), and product quantization (PQ). Algorithms based on proximity graphs have gained popularity for performing better on high-dimensional data, but the paper points out that their routing scales as a power law and degrades a lot on low-dimensional or clustered data. This is where HNSW proposes an incremental, fully graph-based structure with logarithmic scaling.
Navigable graphs (NSW) and why they were still not enough
In proximity graphs, search is greedy routing: it starts at an entry point, examines the distances from the query to the neighbors of the current node, and jumps to the closest neighbor, keeping the best candidates until a stop condition is met. The Navigable Small World (NSW) is a graph built by inserting elements in random order and linking each new element, in both directions, to the M closest neighbors among those already inserted. Links made early in construction become bridges between hubs and keep the graph connected, which lets the number of greedy-routing hops grow logarithmically with network size. Even so, the paper explains that the total cost of an NSW search is approximately the number of hops multiplied by the average degree of the nodes on the path, and that degree also grows logarithmically for two reasons: the search tends to pass through the same hubs as the network grows, and the average number of connections of those hubs grows logarithmically with network size. The result is polylogarithmic scaling, not logarithmic. There is also an initial zoom-out phase, in which the search starts at low-degree nodes and can get stuck in a false, distant local minimum. Starting the search at a hub helps, according to the cited tests, but it keeps the polylogarithmic scaling and yields less on high-dimensional data than HNSW.
The core idea: hierarchical layers, like a skip list
HNSW separates the graph links by the scale of their length, distributing them across layers. Each element gets a maximum level drawn with a probability that decays exponentially, so that the upper layers contain progressively smaller subsets of the elements and the expected number of layers grows logarithmically. Each layer has a proximity graph, and the high layers have the longest links. The search starts at the entry point of the top layer and does greedy routing until it reaches a local minimum. It then moves down one layer, restarts from that element, and repeats the process until layer zero, where all the elements are. Since the maximum number of connections per element can be constant across all layers, only a fixed fraction of the links is evaluated per element, regardless of the size of the network. On insertion, the new element draws its level, descends through the layers above that level with a simple greedy search, and, from its level down, looks for neighbors in each layer to connect to. Because the randomness comes from the level draw, there is no need to shuffle the elements before insertion, which enables incremental indexing. The paper points out the similarity to the probabilistic skip list, in which the linked lists are replaced by proximity graphs.
Parameters: M, mL, Mmax0, efConstruction and ef
The paper describes a few parameters with distinct roles. M is the number of connections an element establishes at insertion; the paper presents it as the only truly relevant construction parameter for the user, with a reasonable range of 5 to 48. In its simulations, smaller M tends to work better with low recall or low-dimensional data, and larger M with high recall or high-dimensional data. M also determines memory consumption, which is proportional to it. The parameter mL normalizes level generation; the paper suggests 1/ln(M) as a simple choice, and mL equal to zero is equivalent to a single layer. Mmax0 is the maximum number of connections at layer zero, and 2·M is the paper's suggestion, since fixing it at M heavily penalizes high recall and larger values worsen performance and waste memory. efConstruction is the size of the dynamic candidate list during construction; it should be large enough for the recall of the search during construction to be close to 1 (the paper says 0.95 is enough in most cases). ef, in turn, is the size of the candidate list during the query and controls search quality. The paper also describes a neighbor selection heuristic that chooses diverse connections, instead of just the closest ones. In all tested cases it gave performance equal to or better than simply linking to the closest neighbors, with a stronger effect on low-dimensional data, on high recall for medium-dimensional data, and on highly clustered data.
Trade-offs: recall, latency, construction, and memory
In HNSW, the query knob is ef: a larger candidate list examines more of the neighborhood and raises recall, at the cost of more distance computations and more time per query. In experiments with random 4-dimensional data, the paper shows that the ef needed to reach a fixed recall saturates as the dataset grows, which supports the logarithmic scaling observed in low dimensions; the paper stresses that, for high dimensions, this empirical evidence was not possible and analytical arguments are missing. At construction time, efConstruction trades indexing time for quality: for 10 million SIFT vectors, a reasonable-quality index with efConstruction=100 was built in about 3 minutes on a Xeon server with 4 processors of 10 cores each, and increasing the value further brought little gain at a much higher time cost. Memory is dominated by the connections; with a typical M between 6 and 48 and 4-byte links, the paper estimates about 60 to 450 bytes per object, not counting the data. In the comparison on Euclidean spaces (ann-benchmark, single thread), HNSW comfortably outperformed the baseline NSW, FLANN, Annoy, VP-tree, and FALCONN on the SIFT, GloVe, DEEP, and CoPhIR datasets; on low-dimensional data (d=4), it was only slightly faster than Annoy at high recall, although it comfortably outperformed the others. The paper also states that construction can be parallelized with few synchronization points and with no measurable effect on index quality.
See the ideas at work
Practice the designs that use this paper in the System Design school.