Katkat
Back

Design large-scale near-duplicate video detection

GoogleMachine Learning Engineer · Onsite
HardMachine Learning EngineerOnsiteSystem Design

Last updated

This question tests the ability to design an end-to-end pipeline for detecting near-duplicate videos at a massive scale, focusing on embedding generation, vector indexing, and trade-offs between precision and recall.

Problem Statement

You are tasked with building a system for a video hosting platform that detects near-duplicate videos in real-time. A "near-duplicate" is defined as a video that has been slightly modified (e.g., re-encoded, color-shifted, watermarked, or cropped) compared to an existing video in our database of 1 billion assets.

Functional Requirements

  • Ingestion: As a new video is uploaded, the system must determine if it is a near-duplicate of an existing video within 500ms.
  • Storage: Maintain a global index of existing video embeddings.
  • Updates: Newly identified unique videos must be indexed within 5 minutes.

Non-Functional Requirements

  • Scale: Handle 10,000 requests per second (RPS).
  • Precision/Recall: High precision is required to avoid false positives (e.g., blocking legitimate original content), while recall must be high enough to effectively curb copyright infringement.

Design Deliverables

  1. Feature Extraction: Propose a method for generating compact, robust video embeddings that are invariant to minor perturbations.
  2. Indexing Strategy: Design an Approximate Nearest Neighbor (ANN) search architecture that scales to 1 billion items.
  3. Post-processing: How do you handle borderline cases or verify matches before taking automated action?
  4. Trade-offs: Discuss the balance between embedding dimensionality, storage costs, and search latency.

Hints

Hint 1

Consider using temporal signatures or frames sampled at fixed intervals to represent the video's content rather than processing the entire video stream.

Hint 2

Look into Product Quantization (PQ) or Locality Sensitive Hashing (LSH) to reduce the memory footprint of the billion-item vector index.

Hint 3

Think about a multi-stage approach: a coarse-grained retrieval filter followed by a fine-grained feature comparison for high-confidence matches.

Follow-up questions

  • How would you handle a scenario where an attacker tries to bypass detection by adding a subtle, non-visible overlay to every frame?
  • If the database grows to 10 billion videos, how would you shard or distribute the index while maintaining search latency?
  • How would you measure the performance of your system in production if you do not have ground-truth labels for all duplicate pairs?