Audio fingerprinting identifies a recording from a short, noisy excerpt of it. The published algorithm behind the best-known implementation is twenty years old, simple enough to describe completely, and its cost is entirely an indexing problem — which is the part nobody derives.
What the problem actually is
The requirement is exact-recording identification under severe degradation. Ten seconds of audio recorded on a phone in a bar, through a lossy codec, with conversation over it, must find the exact master recording in a library of millions. It must not match a different performance of the same song, and it must return nothing rather than something for audio that is not in the library.
That set of requirements rules out most of what people first try:
- Cryptographic hashing is exact-file matching. One re-encode and it fails completely. Useful for byte-identical duplicates and nothing else.
- Embedding the whole clip and using nearest neighbours struggles with alignment: the query is ten seconds from an unknown offset in a four-minute track, so you would need embeddings at every offset, and the nearest neighbour to a noisy clip is often a different track of similar texture.
- Correlating the waveform is defeated by any change in gain, EQ or codec, and is far too slow at library scale.
What works is finding features that survive the degradation and are sparse enough to index.
Peaks, because peaks survive
The insight in Avery Wang’s 2003 paper describing Shazam’s algorithm — published as “An Industrial-Strength Audio Search Algorithm” — is that local maxima in the spectrogram are robust in exactly the way needed.
- Compute the spectrogram: overlapping windows, FFT, magnitude. The same front end as speech recognition, without the mel projection — this task cares about exact frequencies, not perceptual ones.
- Find points that are the maximum in a neighbourhood of the time-frequency plane. These are the loudest components at their moment and their frequency.
- Discard everything else. The recording becomes a sparse constellation of a few dozen points per second, defined only by time and frequency; amplitude is thrown away.
Why this survives: additive noise raises the floor across the spectrum but rarely creates a new local maximum louder than an existing musical peak. Lossy compression discards masked content, which is by definition not the peaks. Filtering and EQ change amplitudes, and amplitude has already been discarded. What remains is a pattern that is nearly invariant to everything the recording will be put through — and discarding amplitude is precisely what buys that invariance.
Combinatorial hashing
A single peak is not distinctive: thousands of tracks contain a peak at 440 Hz. Pairs of peaks are. Each peak is taken as an anchor, and paired with each peak in a target zone ahead of it in time.
For each anchor peak, and each of F peaks in its target zone:
hash = (f1, f2, dt)
f1 frequency of the anchor quantised, ~10 bits
f2 frequency of the target quantised, ~10 bits
dt time between them quantised, ~12 bits
Packed into 32 bits comfortably.
Stored against that hash:
t1 absolute time of the anchor in the track
track_id which recording it came from
The lookup key contains NO absolute time, only the offset between
the two peaks. That is the whole trick: the key is invariant to
where in the track the excerpt starts, so a query from an unknown
offset matches directly.
Two properties fall out:
specificity a triple is far rarer than a single frequency, so
a hash hit is strong evidence rather than a weak one
multiplicity each anchor generates F hashes, so the index grows
by a factor of F -- this is the cost of the trick
and the subject of the sizing section below
The fan-out F is the tuning parameter that trades robustness against index size. A larger target zone means more pairs survive when some peaks are destroyed by noise, and a proportionally larger index.
Matching by time offset
Retrieval is a histogram, and this step is what makes false positives rare.
1. Fingerprint the query the same way -> a set of (hash, t_query).
2. Look up each hash. Each hit gives (track_id, t_track).
3. For every hit, compute the offset:
delta = t_track - t_query
4. Histogram delta, per track.
A TRUE match produces a spike: every genuine hash agrees on the
same delta, because the query is a contiguous excerpt and all its
peaks sit at the same fixed distance from the track's start.
A FALSE match produces a flat scatter: coincidental hash
collisions land at unrelated offsets and never pile up.
So the decision is not "how many hashes matched" -- it is "how
many matched AT THE SAME OFFSET". A track with 200 scattered hits
loses to a track with 30 hits in one bin. This is what lets the
system return nothing at all for audio it does not know, which is
the requirement most similarity approaches fail.
The winning bin also tells you WHERE in the track the excerpt
came from, for free.
Sizing the index
This is the part that decides whether the project is feasible, and it is straightforward arithmetic. Every parameter below is an assumption you set; substitute your own.
Assumptions, all of which you must state when you quote a result:
p peak density 30 peaks per second
F fan-out per anchor 10 target peaks
L average track length 240 s (4 minutes)
N library size 1,000,000 tracks
B bytes stored per hash entry 8 bytes
(32-bit packed hash is the KEY; the VALUE is a 32-bit
track id plus a 32-bit time offset, so the payload is
8 bytes before any index overhead)
Hashes per second of audio:
p * F = 30 * 10 = 300 hashes/s
Hashes per track:
300 * 240 = 72,000
Hashes in the library:
72,000 * 1e6 = 7.2e10 = 72 billion entries
Payload bytes:
7.2e10 * 8 = 5.76e11 = 576 GB
...before the hash table's own overhead, which for an on-disk
inverted index with 32-bit keys is realistically another 30-100%.
Call it under a terabyte and over half of one.
Now the query side:
10-second query -> 300 * 10 = 3,000 hash lookups
each lookup returns every occurrence of that hash anywhere in
the library
expected postings per lookup ~= total_entries / distinct_hashes
With a 32-bit hash space that is 7.2e10 / 4.3e9 ~= 17 postings
per lookup on a UNIFORM distribution -- so roughly 50,000
postings to histogram per query. Real peak distributions are far
from uniform: common hashes have vastly more postings than that,
which is why production systems cap the postings per hash and
drop the most frequent hashes entirely.
Three engineering conclusions follow directly from that arithmetic, and none of them requires an experiment:
- The index is the system. Fingerprinting a track is cheap and one-off; the recurring cost is holding 72 billion postings somewhere they can be read in milliseconds. Every design decision is really about that number.
- F is the lever with the largest effect. It multiplies both the index size and the query cost linearly. Halving the fan-out halves your storage and roughly halves your query work, at some cost in robustness on degraded audio. Tune it against real degraded queries, not clean ones.
- Hash skew must be handled explicitly. A uniform distribution is an assumption the audio does not honour. Cap postings per hash, or drop hashes above a frequency threshold; both cost almost nothing in recall and prevent a single common hash from dominating every query.
Chromaprint, the fingerprinter behind the open AcoustID service, takes a different route — chroma features summarising pitch class over time, compressed into a compact fingerprint — and trades some of the excerpt-matching robustness for a much smaller footprint. Which family fits depends on whether your queries are short noisy excerpts or whole files.
Deduplication is a different task
Finding a clip’s source and deduplicating a library look similar and want different tools. Match the tool to the question:
| Question | Description |
|---|---|
| byte-identical? | SHA-256 of the file. Free, exact, and catches the large fraction of real duplicates that are literally the same file copied twice. |
| same audio, different container? | Hash the decoded PCM rather than the file. Catches re-muxes, tag edits and container changes, which no file hash catches and which are extremely common in a real library. |
| same recording, re-encoded? | Fingerprinting as described above. This is the case the algorithm is for: different bitrate, different codec, trimmed, normalised. |
| same work, different performance? | Not a fingerprinting question at all. A live version and a studio version share a composition, not a recording, and a fingerprinter is designed specifically not to match them. This needs melodic or embedding-based similarity, and it will have false positives that exact matching does not. |
| same speaker or same meeting? | Also not fingerprinting. Two recordings of one meeting from two microphones are different audio. Use the transcripts: shingle the text and compare, which is far more robust than anything acoustic here. |
Run them in that order. Each stage is cheaper than the next and removes work from it, and the first two together typically resolve most of a real library before anything clever is needed.
Top comments (0)