Close Enough 0% ◫Browse AaGlossary
2.2
Stage 2 · Trees, hashing, clustering

Cut the space into pieces

Three ways to partition space, in the order they were invented. Each one fixes the previous one's blind spot, and the last one wins by looking at the data.

~3 min

1Family 1 · Trees: boxes

A k-d tree (Bentley, 1975) cuts space along one coordinate at a time, so a query only descends into nearby boxes.

  • Excellent in 2 to 10 dimensions: maps, geometry, games.
  • Hopeless at 768: with one cut per level, a tree over a billion points uses only about 30 of the 768 coordinates. The query’s neighbours end up spread across most boxes (1.7 What does “close” mean?).

Random projection trees (Spotify’s Annoy, 2013) split along random directions instead and build a forest of them. Good enough for music recommendations at the time; now mostly superseded.

2Family 2 · Hashing: make collisions mean closeness

A normal hash function scatters similar inputs. Locality-sensitive hashing (Indyk and Motwani, 1998) does the opposite: it is designed so that close points are likely to land in the same bucket.

For cosine similarity the classic version is Charikar’s SimHash. Each bit records which side of a random hyperplane the vector falls on.

SimHash in three linesnumpy
R = np.random.randn(d, 16)              # 16 random hyperplanes through the origin
signature = lambda v: tuple(v @ R > 0)  # 16 bits
# For vectors at angle theta, each bit differs with probability theta / pi.

Similar vectors share most bits and so share a bucket. Several tables catch the near-misses.

3Family 3 · Clustering: learn where the data is

The insight that took over: real data is clumpy, so learn the partition from the data.

  1. Run k-means to get, say, 4,096 centroids.
  2. Assign every vector to its nearest centroid. That gives 4,096 lists.
  3. At query time, find the few centroids closest to the query.
  4. Scan only those lists.

This is the inverted file index (IVF), named after the inverted index of keyword search. The knob is nprobe: how many lists to scan.

work per query  ≈  K⏟compare to centroids  +  nprobe⋅NK⏟scan the lists \text{work per query} \;\approx\; \underbrace{K}_{\text{compare to centroids}} \;+\; \underbrace{\texttt{nprobe}\cdot \tfrac{N}{K}}_{\text{scan the lists}}

With K≈NK \approx \sqrt{N} both terms are about N\sqrt N: a thousand-fold saving at a million vectors.

4The cluster id is already compression

Notice what IVF did besides routing. Knowing that a vector is in list 2,317 of 4,096 tells you 12 bits about where it is. Store only the difference from the centroid (the residual) and that difference is smaller and easier to compress than the vector was.

That observation, taken seriously, is Part 4.