Problem RestatementProblem
Google asked an ML engineer: design a system that detects near-duplicate videos at huge scale. For example, re-uploads of copyrighted content that were cropped, re-encoded, resized, sped up, mirrored or had logos or borders added. For each new upload, quickly find existing videos (out of billions) that are near-duplicates, fully or partially (a 30-second clip from a movie).
Pipeline Overview
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
UP["New upload"] --> DEC["Decode + sample frames (e.g., 1 fps + scene changes)"]
DEC --> FEAT["Frame features - perceptual hash + CNN embedding"]
FEAT --> AGG["Segment signatures - e.g., every 5 s"]
AGG --> ANN["ANN search - vector index of reference segments"]
IDX[("Reference index - billions of segments")] --> ANN
ANN --> VER["Temporal alignment + verification"]
VER --> DEC2["Decision: match / no match + score"]
DEC2 --> ACT["Policy: block, claim, review queue"]
AGG -->|"add as reference"| IDXFingerprints (features)
- Sample frames: e.g., 1 frame per second plus frames at scene changes. Normalize them (resize, grayscale or color-normalized, crop black borders).
- Perceptual hashes (pHash/dHash): tiny 64-bit signatures that barely change under re-encoding or resizing. Fast and cheap, but weaker against crops and overlays.
- Learned embeddings: a CNN or vision transformer trained (with contrastive learning) so the same content under edits maps to nearby vectors, and different content to far vectors. Train with augmentations matching real attacks (crop, flip, color shift, speed change, overlay text).
- Audio fingerprints (optional but powerful): spectrogram peak hashes survive video edits.
- Segment signatures: combine frame embeddings over short windows (e.g., 5 seconds) into one vector per segment. This enables partial matching.
Deep Dive — Searching billions of fingerprintsDeep dive
Each reference video contributes many segment vectors, so the index holds billions of them. A query video produces hundreds more, and every one needs its nearest neighbours.
Compare the query against every reference
For each query segment, compute similarity against every stored vector and keep the best.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
Q["300 query segments"] --> CMP["x 2,000,000,000 reference vectors"]
CMP --> OPS["600 billion distance computations per upload"]
OPS --> TIME["Hours of GPU time for one video"]
CMP --> MEM["Full-precision vectors do not fit in memory"]Exhaustive search is exact and hopeless at this scale. It also forces full-precision vectors to stay resident, which is where the memory budget goes before the compute budget does.
An exact nearest-neighbour index
Build a tree or inverted structure that prunes the search space and returns exact neighbours.
Better than brute force, and high-dimensional vectors defeat the pruning: above a few dozen dimensions, distances concentrate and exact structures degrade toward scanning everything. Embeddings here are hundreds of dimensions, so the index stops earning its cost precisely where it is needed.
Approximate search over quantised vectors, sharded
Accept a small recall loss for orders of magnitude in speed and memory:
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
REF["Reference segment vectors"] --> PQ["Product quantisation - compress each vector to bytes"]
PQ --> IVF["IVF / HNSW index, sharded across machines"]
QS["Query segment"] --> IVF
IVF --> TOPK["Top-k candidates above a similarity threshold"]
TOPK --> VER["Verification - temporal alignment, exact re-scoring"]
VER --> MATCH["Confirmed near-duplicate"]
VER --> DROP["False positive dropped"]- Product quantisation is what makes it fit. Compressing each vector to a handful of bytes lets billions of them live in memory across a shard set — the difference between an index that exists and one that does not.
- ANN trades recall for speed deliberately. Missing a small fraction of true neighbours is acceptable because a duplicate video contributes many segments, so a match surviving in any of them is enough to flag the video.
- Sharding is by vector, and queries fan out to all shards with a deadline, merging top-k results.
The approximation is safe because verification follows. Candidates are re-scored exactly and checked for temporal alignment — do the matching segments appear in a consistent order and spacing? — which is what separates a genuine re-upload from two videos that happen to share a stock clip. Approximate retrieval for recall, exact verification for precision: the ANN index is allowed to be loose precisely because nothing downstream trusts it on its own.
Verification (reduce false positives)
- Temporal alignment: a real duplicate matches many consecutive segments of the same reference video with a consistent time offset (and maybe a consistent speed factor). Random single-segment hits are noise.
- Score = matched duration × average similarity. Apply thresholds tuned for precision/recall, with separate thresholds for full vs partial matches.
- Borderline cases → a human review queue.
Evaluation and Operations
- Labeled test sets of original + transformed copies (the known attack types) and hard negatives (different videos that look alike: news clips, sports games).
- Metrics: precision and recall at the operating threshold, and latency from upload to decision (e.g., under a few minutes, with fast checks during upload).
- Adversaries adapt: monitor missed cases reported by rights holders, and retrain with new augmentations.
- Cost: fingerprint once at upload, run cheap perceptual hash matching first, and use embeddings and ANN for the rest. Store only compact fingerprints, not frames.
Wrap-UpWrap-up
Sample frames, compute robust features (perceptual hashes, contrastively trained embeddings, audio fingerprints), and aggregate them into short segment signatures. Search a sharded, compressed ANN index of reference segments for candidates, then verify with temporal alignment (many consecutive matches at a consistent offset) to confirm full or partial duplicates with tuned thresholds and human review for borderline cases. Evaluate on transformed copies and hard negatives, and retrain as edit attacks evolve.