The shared recipe behind search: Images, Shazam and RAG

Or: why every modern “find me something similar” feature is the same problem in disguise — and what makes it hard at scale.

RAG stands for Retrieval-Augmented Generation

Open Google Images, drop in a photo, and a few hundred milliseconds later you get every page that hosts a near-duplicate of it. Hum into Shazam and it tells you the song. Type a question into ChatGPT and, before answering, it pulls the three most relevant documents out of a database that might have a hundred million entries. Spotify suggests songs that feel like the one you’re playing. Tinder shows you faces that look like the ones you swipe right on.

These all look like wildly different features built by different teams. They’re not. Under the hood it’s the same trick, repeated four times:

1. Turn the messy real-world thing — a photo, a song, a sentence, a person — into a vector of numbers.
2. Drop that vector into a shared space along with millions of others built the same way.
3. When a query arrives, turn it into a vector too.
4. Find the nearest existing vectors to the query. Those are your answer.

The first step is called making a descriptor. The fourth step is nearest-neighbour search, often shortened to KNN (k nearest neighbours).

This post is a tour. We’ll start completely from scratch — what a descriptor even is, with examples from images, audio, and text. Then we’ll watch all of those collapse into the same geometric problem, look at why that problem is genuinely hard at high dimensions (the curse of dimensionality), and end with a specific trick that works really well for binary descriptors: Multi-Index Hashing (MIH). Along the way I’ll show you some benchmark numbers from pynear, the small library we built for exactly this kind of work.

This is aimed at curious developers — no machine-learning background required. The math sections are marked, and you can skip them.

1. Descriptors: the steady bridge from messy data to geometry

A descriptor is a small summary of a thing — small enough that you can store millions of them in memory, structured enough that similar things produce similar descriptors. That second property is the whole game. If similarity in your problem maps to closeness in the descriptor space (or what we call a “vector” or point in that space), then finding similar items reduces to finding close vectors, which is a geometry problem. Geometry has decades of fast algorithms development behind it. Domain semantics (like “are these two cats the same breed?”, “are these two paragraphs talking about the same thing?”) do not.

So: how do you build a descriptor that has this property? It depends on the domain.

Images — SIFT, ORB, and friends

A photograph is a few million pixels. You can’t compare two photographs pixel-by-pixel — shift the camera one pixel to the left and every comparison fails. What you can compare is the local structure at the interesting points: corners, blobs, places where the image has distinctive texture.

SIFT (Scale-Invariant Feature Transform, 1999) and ORB (2011) are recipes for turning each interesting point into a fixed-size descriptor — typically 128 floats for SIFT, 256 bits for ORB. The recipe, in spirit:

1. Find a few hundred “interesting” points in the image (corners, blobs).
2. Around each one, look at a small neighbourhood (say 16×16 pixels).
3. Compute the dominant gradient direction in that patch, and rotate the patch to point that direction up. This is the rotation-invariance trick: no matter how you tilt the camera, the descriptor for the same physical corner comes out the same.
4. Split the rotated patch into sub-cells, build a histogram of gradient directions in each cell, concatenate them all → that’s your descriptor vector.

The clever part is step 3. A corner of a building looks like a corner whether you photograph the building from upright, sideways, or upside-down. Without orientation alignment, those three photos would produce three totally different descriptors and pixel-matching would fail. With it, all three give you (approximately) the same vector.

ORB does the same thing but cheaper: instead of gradient histograms, it computes a few hundred binary tests (“is this pixel brighter than that pixel?”), packs the results into a 256-bit string, and ships it. Each ORB descriptor is therefore 32 bytes. A 1 GB index can hold ~30 million of them.

Same recipe works on faces (FaceNet, ArcFace), fingerprints (detail descriptors), satellite-image patches, MRI volumes, anything spatial.

Audio — Shazam, Chromaprint, and the spectrogram

Sound is a one-dimensional waveform that nobody can usefully compare in the time domain. Convert it to a spectrogram (frequency over time) and suddenly there’s structure: a song has characteristic frequency peaks at characteristic moments. Shazam picks the locally strongest peaks, then encodes the constellation of (frequency, time-offset) pairs around each one as a 32-bit hash. A 3-minute song becomes a few thousand hashes. Match a recorded clip against the database and the hashes that line up in the same temporal pattern identify the song — even through phone microphones, noise, and lossy compression.

Chromaprint (the engine behind AcoustID and MusicBrainz) does a related thing — projects the spectrogram onto a 12-note chromatic basis, then quantises to bits. Two recordings of the same song produce nearly the same descriptor, even at different bitrates.

SoundHound’s “hum a tune” feature uses a different family — pitch-contour matching against a tune database — but the bones are the same: turn audio into a vector, find the nearest vectors.

Text — SimHash, MinHash, and embedding models

Two documents about the same topic should have similar descriptors. The classic trick is SimHash: hash every word (or n-gram) of the document, take the sign of a weighted sum of those hashes, and pack the signs into a bit string. Two documents that share most of their vocabulary get most of those signs the same way, so their SimHashes differ in only a few bits. Google uses this to dedupe near-identical web pages.

The modern version is embedding models — neural networks trained specifically to produce close vectors for semantically related text. text-embedding-3-small, all-MiniLM-L6-v2, BGE, and similar models give you a 384-D or 768-D float vector per sentence or paragraph. “How do I bake bread?” and “What’s a sourdough recipe?” land near each other; “How do I bake bread?” and “What’s the capital of France?” don’t. This is what powers RAG (retrieval-augmented generation): when you ask an LLM a question, it first KNN-searches a database of paragraph embeddings to find context, then uses that context to answer.

The shared shape

Different domains, different recipes, same output:

A 16-byte ORB binary string. A 512-bit Chromaprint fingerprint. A 768-dimensional float embedding. Each one is just a point in a high-dimensional space. Once you’ve decided which space your problem lives in, you stop caring about photos and songs and sentences. You care about points.

2. KNN — the central reduction

Now zoom out. Whatever the modality, the runtime problem looks like this:

• You have a database of N descriptors (N might be 10⁵ for a side project, 10⁹ for an image-dedup pipeline at a big tech company).
• A query arrives — its descriptor, computed the same way as the database’s.
• You want the k database descriptors closest to the query, by some distance function (Euclidean, cosine, Hamming).

That’s it. That’s the whole problem. The drag is the scale. Even if comparing a query to one database descriptor takes a microsecond, comparing it to a billion descriptors takes 1 000 seconds. Per query. There are 86 400 seconds in a day, so a single CPU core can handle about 86 queries a day at that rate. Not exactly Google scale.

You need structure. You need an index.

3. The two regimes: low-dim vs high-dim

Here’s where things split.

If your descriptors are low-dimensional (a few dozen dimensions, say), the geometry of the space cooperates. You can build a tree that recursively splits the space into halves, and at query time you only descend into the half that contains the query — you prune away half the database every step. Classical 2-D / 3-D nearest-neighbour search runs in O(log N) per query.

If your descriptors are high-dimensional (hundreds of dimensions, like SIFT-128 or text embeddings), this strategy collapses. Pruning stops working. The reason is one of the most counter-intuitive facts in geometry: in high dimensions, every point is roughly the same distance from every other point. There’s nothing left to prune. We’ll show you that in a moment.

Spatial indices that work in low dimensions: VP-trees vs kd-trees

You might know kd-trees from a college algorithms class. They’re the classical structure: at each level, split the points along one axis at the median. A query then walks down the tree, only visiting the side of each split that the query could plausibly contain neighbours in.

Kd-trees work great in 2–3 dimensions and become useless past about 20. The reason is axis-aligned splits. As dimensions grow, the bounding box of any sub-tree extends far in many directions, and the query is almost always close to the “wrong” side of some axis split. The pruning logic kicks in less and less often. By d=20 you’re visiting nearly every node.

VP-trees (Vantage-Point trees) handle this much better. Instead of splitting on axes, they split on distance from a chosen pivot point. At each node you pick a pivot and a radius; everything inside the radius goes left, everything outside goes right. A query at distance d from the pivot can only have neighbours in the “near” half if its distance is within the radius (plus some slack); same for the “far” half. This is a metric split rather than a geometric one, so it respects the actual distance function rather than the coordinate system.

VP-trees stay useful out to ~100–200 dimensions for many real datasets, where kd-trees gave up at d=20. They’re also metric-agnostic: as long as your distance is a valid metric (triangle inequality holds), VP-trees work. Cosine, L1, L2, Hamming, edit distance — all of them.

(pynear uses VP-trees as its exact-search backbone for exactly this reason. The detailed walk-through is in the pynear docs.)

But past ~256 dimensions, even VP-trees struggle. To understand why — and why this isn’t a problem you can engineer your way out of — we need to look at the curse of dimensionality.

4. The curse of dimensionality (the intuitive version)

Imagine you live on a number line — one dimension. You’re standing at position 0.5. You declare that anything within distance 0.1 from you is “near”. How much of the available space is “near”? A length of 0.2 out of [0, 1] — 20% of the space.

Move to 2D. Same rule: anything within distance 0.1 is near. Now “near” means inside a small circle of area π × 0.01 ≈ 0.031, out of the unit square’s area of 1. 3% of the space.

In 10D: a tiny ball of radius 0.1 in a 10-cube has volume ≈ 0.¹¹⁰ = 10⁻¹⁰. One ten-billionth of the space is near you.

This is bad enough by itself: in high dimensions, the “neighbourhood” you can plausibly search has vanishing relative volume compared to the whole space. But there’s a second, stranger effect that’s the actual killer.

Pairwise distances collapse to a single value

Take N random uniform points in a d-dimensional unit cube and look at the distribution of pairwise distances between them. Here it is for d = 2, 20, and 200:

In 2D the distances span a wide range — there are nearby pairs and faraway pairs, and the difference is meaningful. In 20D the distribution is already much tighter. By 200D, every pair of points is at roughly the same distance from every other pair. The variance has essentially disappeared.

This is the actual reason high-dim KNN is hard. If every database point is roughly the same distance from your query, then “the nearest 10” are barely distinguishable from “the farthest 10”, and there’s nothing for a tree to prune. The geometry isn’t telling you anything useful.

The thin-shell effect

Here’s a related fact that’s even more startling. Take a unit ball in d dimensions. What fraction of its volume is in the outer 10% of its radius — i.e., between r=0.9 and r=1.0?

In 3D: about 27% (you can almost compute it in your head — most of a ball’s volume isn’t in the very middle, but it’s still spread out).

In 20D: 88%.

In 100D: 99.997%.

There is essentially no “inside” to a high-dimensional ball. All the volume is crammed into a thin crust at the surface. Combined with the previous fact (everyone is the same distance apart), this paints the picture: in high-dim space, all the points cluster near the boundary of any region you draw, and they’re all approximately the same distance from each other. Your intuitions about “neighbourhoods” stop working.

What this means for KNN

For high-dim KNN, you mainly have two options:

1. Accept that you’ll have to check most of the database for every query. This is what brute force does — compare the query to every single descriptor. It sounds terrible, but at d=128 with good SIMD code it’s surprisingly fast: a million comparisons in a few hundred microseconds. Faiss’s IndexBinaryFlat is exactly this.
2. Give up on “exact” and accept an approximation. Approximate methods (HNSW graphs, IVF, LSH) trade a small recall loss for a large speedup. They don’t beat the curse; they live with it.

There’s a third option, but only for one specific case: binary descriptors with small Hamming radius. That’s MIH, and it’s where pynear’s biggest wedge lives.

Optional math digression

(its safe to skip this section)

The “thin shell” claim above isn’t hard to verify. The volume of a d-dimensional ball of radius r is proportional to rᵈ. So the fraction of a unit ball’s volume that sits between radius 0.9 and 1.0 is:

1–0.9^d

At d = 100, 0.9¹⁰⁰ ≈ 2.66 × 10⁻⁵. So 99.997% of the unit ball is in the outer 10%. The same calculation for d = 1000: essentially all of it.

The distance concentration shown in the histograms above also has a clean asymptotic form. For random uniform points in d-dim, the ratio (max distance − min distance) / (min distance) tends to zero as d → ∞, at rate roughly 1/√d. This is called the concentration of distances phenomenon and is the formal statement of what the histograms show.

The pynear docs have a longer derivation with the volume integrals worked through. It’s not essential reading for what follows.

5. The binary descriptor twist — Multi-Index Hashing

We just said the curse of dimensionality breaks tree-based pruning. That’s true. But it doesn’t break hashing, and for binary descriptors there’s a beautiful hashing trick that genuinely works: Multi-Index Hashing, or MIH.

The setup

You have N binary descriptors, each d bits wide (typical: d = 128, 256, or 512). You want to find every database descriptor within Hamming distance r of a query. (Hamming distance = number of bit positions where the two strings differ. POPCNT is a single CPU instruction, so comparing two 128-bit descriptors takes about a nanosecond.)

The naive approach: compare the query to every descriptor and keep the ones within radius r. Brute force at SIFT1M scale: ~50 ms per query. Workable but not fast.

The pigeonhole observation

Here’s the key insight. Split each d-bit descriptor into m sub-strings of d/m bits each. For d=128, m=4 gives you four 32-bit sub-strings.

Now: if two descriptors q and x differ in at most r total bits, then those r differences are distributed across the m sub-strings somehow. By the pigeonhole principle, at least one sub-string must contain ≤ ⌊r/m⌋ of those differences.

For d=128, m=4, r=8: at least one of q’s four sub-strings must match the corresponding sub-string of x to within ⌊8/4⌋ = 2 bits.

Why this is useful

This converts a search problem into a hash lookup problem. Build m hash tables, one per sub-string position. For each database descriptor, insert it into all m tables, keyed by its sub-string in that position. To answer a query at radius r:

1. For each sub-table t (1 to m):

• Extract the query’s t-th sub-string.
• Enumerate all sub-strings within Hamming distance ⌊r/m⌋ of it.
• Look each one up in table t; collect the matching descriptor IDs.

1. Union all the candidate sets. The true neighbours are guaranteed to be there.
2. Verify each candidate with a full d-bit POPCNT against the query.

The pigeonhole principle guarantees you can’t miss any true neighbour at distance ≤ r — pure hash lookups, no scanning. The verification step is fast because you’re only checking the small candidate set, not the whole database.

The catch

When does MIH actually beat brute force? When the candidate sets stay small. That happens when:

• r is small (you’re searching for near-duplicates, not exhaustive neighbours)
• d is large (the sub-string key space 2^(d/m) is much bigger than N, so each lookup returns few hits)
• The data isn’t too clustered (clustered data inflates buckets)

For d=512, m=8: each sub-string is 64 bits → 2⁶⁴ key space. With N = 10⁶ descriptors, the average bucket holds 10⁶ / 2⁶⁴ ≈ 0 candidates. Lookups are effectively free. MIH at this size is hundreds of times faster than brute force.

For d=128 on real, clustered SIFT data: sub-strings are 32 bits → ²³² key space. With N = 10⁶ that’s ~233 candidates per bucket on average, and the clustered nature of real data makes some buckets blow up to thousands. The verification step dominates, and MIH only modestly beats brute force.

Of course, MIH is not magic for every case. It’s a great fit for image and document near-duplicate detection (small radius, large descriptor), and a mediocre fit for high-recall search on clustered low-dim binary data.

6. Our implementation — what makes pynear’s MIH fast

pynear is the small KNN library we built around exactly these workloads. It’s a C++ core with a tiny Python wrapper — pip install pynear and you’re done, no native dependencies to fight with.

Building an MIH index is one line:

import numpy as np, pynear
# 1M × 128-bit descriptors, e.g. sign-quantised SIFT
db = np.random.randint(0, 256, size=(1_000_000, 16), dtype=np.uint8)
index = pynear.MIHBinaryIndex(m=4) # m=4 for 128-bit descriptors
index.set(db)
queries = np.random.randint(0, 256, size=(100, 16), dtype=np.uint8)
ids, distances = index.searchKNN(queries, k=10, radius=8)

Three things we did differently from the textbook implementation:

1. uint64_t sub-string keys, packed via memcpy. Every sub-string fits in a single 64-bit integer, so hash lookups bottom out in a single std::unordered_map<uint64_t, …>::find(). No string hashing, no per-key allocation.

2. POPCNT-based verification batched per query. When the candidate set comes back from the hash lookups, we deduplicate it once and then run hardware POPCNT on every candidate against the query in a tight loop. The compiler vectorises this nicely.

3. OpenMP parallel-for over the query batch. Each query is independent — the index is const during search. So the outer query loop is #pragma omp parallel for, which on a 24-core machine gives close to 24× speedup for batch queries.

Benchmarks

Compared head-to-head against Faiss’s own MIH (faiss.IndexBinaryMultiHash) and its brute-force binary index (faiss.IndexBinaryFlat), on the standard SIFT1M dataset (1M × 128-bit sign-quantised SIFT descriptors, 24 threads):

A few observations:

• At every recall point, pynear MIH beats Faiss MIH — about 1.5× faster on this dataset.
• At low-to-moderate recall (~0.3–0.7), both MIH implementations are dramatically faster than brute force.
• At high recall (>0.82), brute force beats both MIHs. This is the curse-of-dim showing up in practice: pushing recall up means widening the search radius, which inflates the candidate set, which approaches the brute-force cost.

And on the d=512 near-duplicate workload that MIH was designed for (1M × 512-bit, 100% Recall@10): pynear MIH delivers 117 000 QPS vs Faiss MIH’s 44 QPS — about 2 600× faster, and ~38× faster than Faiss brute-force. This is the regime where MIH genuinely earns the speedup.

The full benchmark scripts are in the pynear repo, reproducible on any machine with Faiss installed.

7. Try it yourself

pip install pynear
import numpy as np, pynear
# Your real binary descriptors here - ORB / SimHash / Chromaprint / etc.
db = np.random.randint(0, 256, size=(1_000_000, 16), dtype=np.uint8)
queries = np.random.randint(0, 256, size=(100, 16), dtype=np.uint8)
index = pynear.MIHBinaryIndex(m=4)
index.set(db)
ids, dists = index.searchKNN(queries, k=10, radius=8)

Wheels are pre-built for Linux, macOS (Intel + Apple Silicon), and Windows; no native dependencies beyond NumPy. pynear also has VP-trees for exact low-dim search.

Code: github.com/pablocael/pynear Docs: the README and the formal benchmark PDF.

Wrap-up

Image search, song recognition, RAG, and recommender systems all run the same loop: encode the world as vectors, then find the closest vectors to a query. The hard part is the second step at scale, and at high dimensions the geometry stops cooperating in fundamental ways.

For binary descriptors with small search radii — exactly the regime that image deduplication, perceptual hashing, and ORB-style feature matching live in — MIH is a beautiful trick built on the pigeonhole principle. We wrote a small library around it. If you have a project that touches any of those workloads, give pynear a try.

Questions, bugs, feature requests, or stories about what you’re building with it — issues and discussions are open at github.com/pablocael/pynear.