Large-Scale Near-Duplicate Video Detection

0) Problem Restatement

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).

1) Pipeline Overview

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"| IDX

2) Fingerprints (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.

3) Search at Scale

• Store reference segment vectors in an approximate nearest neighbor (ANN) index (FAISS IVF-PQ, ScaNN, HNSW), sharded across many machines, with vectors compressed via product quantization (billions of vectors fit in memory).
• For each query segment, retrieve the top-k similar reference segments above a similarity threshold.

4) 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.

5) 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.

6) Wrap-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.