Concepts
Approximate nearest neighbor search with hierarchical graphs (HNSW)
Intuition
Imagine that you need to find, among millions of items, the ones most similar to an item you have in hand, and comparing against all of them one by one would take too long. A shortcut is to accept an almost perfect answer: you fly by plane to the right region, then continue by car to the neighborhood, and only then walk on foot, looking at a few candidates at each stage. Instead of always guaranteeing the best result, the method trades a little exactness for a lot of speed, and you choose how much extra effort you want to spend to make fewer mistakes.
How it works
K-nearest-neighbor search requires a distance function, and the naive approach compares the query against every element, at a cost linear in the size of the dataset; approximate search accepts some errors, measured by recall (the ratio between the true neighbors found and K). In proximity graphs, search is greedy routing: it starts from an entry point and, at each step, jumps to the neighbor of the current node that is closest to the query. HNSW distributes the links across layers: each element draws a maximum level with a probability that decays exponentially, so the upper layers hold ever smaller subsets and have the longest links, and the expected number of layers grows logarithmically. The query does greedy routing on the top layer until a local minimum, drops one layer restarting from that element, and repeats until layer zero, where all elements live, similar to a probabilistic skip list. On insertion, the new element draws its level, descends through the layers above it with a simple greedy search and, from its level down, searches for and links neighbors in each layer; since the level draw already brings in the randomness, there is no need to shuffle the elements, and indexing is incremental. The parameters play distinct roles: M is the number of connections on insertion and is proportional to memory; mL normalizes level generation (1/ln(M) is the paper's suggestion); Mmax0 caps the connections on layer zero (the suggestion is 2·M); efConstruction is the size of the candidate list at construction time; and ef is the size of the candidate list at query time. A neighbor selection heuristic that picks diverse connections, instead of only the closest ones, performed equally well or better in every case tested.
In practice
At query time, the knob is ef: a larger list examines more of the neighborhood and raises recall, at the cost of more distance computations and more time per query. At construction time, efConstruction trades indexing time for quality (for 10 million SIFT vectors, efConstruction=100 produced a reasonable-quality index in about 3 minutes on the experiment's server, and larger values brought little gain with much longer time), and M, with a reasonable range of 5 to 48, sets the memory: with 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 paper's simulations, a smaller M tends to work better for low recall or low-dimensional data, and a larger M for high recall or high-dimensional data. In single-thread comparisons, HNSW comfortably outperformed NSW, FLANN, Annoy, VP-tree and FALCONN on SIFT, GloVe, DEEP and CoPhIR, but on low-dimensional data (d=4) it was only slightly faster than Annoy at high recall.
Use it in a design
Practice the cases that rely on this concept in the System Design school.