Large-Scale Video Deduplication: The Art of Probabilistic Trade-offs
In video search and recommendation systems, duplicate content detection is a core challenge. The same video uploaded by users may have different encodings, resolutions, or sources. Exact comparison of every video pair costs O(n²) — prohibitive at scale. Practical systems instead use multi-stage filtering: fast hashing to narrow candidates, statistical verification to reduce false positives, and block-level matching to confirm. This article examines three design choices from an industrial implementation.
The Core Problem
Three hard constraints:
- Scale: Billions of videos stored and indexed
- Expense: Video analysis (decoding, feature extraction, comparison) is resource-intensive
- Ambiguity: What counts as "duplicate"? Different edits or crops of the same footage?
The industrial solution staggers checks by cost and accuracy:
- Signature: Compute a cheap hash; candidates that collide move to the next stage
- Verification: Use statistics on features to confirm true matches
- Filtering: Block-level matching to eliminate noise
Three Design Choices
Signature: 64-Bit Hash
// Use MurmurHash2A to generate 64-bit hash
TMurmurHash2A<ui64> hasher;
hasher.Update(src.data(), src.size());
ui64 hash = hasher.Value();
// Bit truncation: keep lower bits to preserve more original information
if (BitsCount < 64) {
int shift = 64 - BitsCount;
hash <<= shift;
hash >>= shift;
}
Choice: Use a 64-bit integer as the video signature.
Trade-off: Hash collisions are certain at scale, so this stage accepts false positives. All candidates pass to verification. The choice of lower bits versus higher bits affects sensitivity to encoding changes; lower bits preserve more original data properties.
Verification: Statistical Filtering
// Use linear regression standard error to judge similarity
double GetLinearRegressStdErr() const {
// Calculate linear regression of matching items
// If standard error is small, it's a real duplicate
}
Choice: Apply statistical methods to candidates, retaining only those matching a threshold.
Trade-off: Direct hash equality is insufficient because legitimate duplicates may encode differently. Statistics can reduce false positives from collision, but only if the underlying features correlate with true duplication. Added complexity here saves cost later if it eliminates enough noise.
Confirmation: Block-Level Filtering
// Organize matching items into blocks by index order
void AddLast(const TMatchItem &item) {
++Last;
// Update statistics
DistSum += item.DiffDist.Dist;
IndexSumFirst += item.IndexFirst;
// ...
}
Choice: Matches are organized by index; those appearing in consecutive blocks are more likely true duplicates.
Trade-off: Outlier matches within a sequence are noise; consecutive patterns indicate real correspondence. This simple heuristic filters without recomputing.
Implementation in Go
To illustrate the design logic, here's a clean reimplementation:
package main
import (
"fmt"
"hash/fnv"
"math"
"sort"
)
type VideoSignature struct {
ID string
URL string
Hash uint64
Features []float64
}
type MatchItem struct {
IndexFirst int
IndexSecond int
Distance float64
}
type MatchBlockStat struct {
First int
Last int
IndexSumFirst int64
IndexSumSecond int64
}
func (m *MatchBlockStat) Init(begin int, item MatchItem) {
m.First = begin
m.Last = begin
m.IndexSumFirst = int64(item.IndexFirst)
m.IndexSumSecond = int64(item.IndexSecond)
}
func (m *MatchBlockStat) Add(item MatchItem) {
m.Last++
m.IndexSumFirst += int64(item.IndexFirst)
m.IndexSumSecond += int64(item.IndexSecond)
}
func (m *MatchBlockStat) GetLength() int {
if m.Last >= m.First {
return m.Last - m.First + 1
}
return 0
}
func (m *MatchBlockStat) CalculateLinearRegressionStdErr(items []MatchItem) float64 {
length := m.GetLength()
if length < 2 {
return 0.0
}
meanFirst := float64(m.IndexSumFirst) / float64(length)
meanSecond := float64(m.IndexSumSecond) / float64(length)
var sumSquares float64
for i := m.First; i <= m.Last; i++ {
observed := float64(items[i].IndexSecond)
predicted := meanSecond + (float64(items[i].IndexFirst)-meanFirst)*0.5
sumSquares += math.Pow(observed-predicted, 2)
}
return math.Sqrt(sumSquares / float64(length-2))
}
type VideoDeduplicator struct {
signatures map[string]VideoSignature
threshold float64
}
func NewVideoDeduplicator(threshold float64) *VideoDeduplicator {
return &VideoDeduplicator{
signatures: make(map[string]VideoSignature),
threshold: threshold,
}
}
func (v *VideoDeduplicator) AddSignature(id, url string, features []float64) {
hash := generateHash(url)
v.signatures[id] = VideoSignature{ID: id, URL: url, Hash: hash, Features: features}
}
func generateHash(s string) uint64 {
h := fnv.New64a()
h.Write([]byte(s))
return h.Sum64()
}
func (v *VideoDeduplicator) FindDuplicates() []MatchItem {
var matches []MatchItem
ids := make([]string, 0, len(v.signatures))
for id := range v.signatures {
ids = append(ids, id)
}
sort.Strings(ids)
for i := 0; i < len(ids)-1; i++ {
for j := i + 1; j < len(ids); j++ {
sig1 := v.signatures[ids[i]]
sig2 := v.signatures[ids[j]]
similarity := calculateSimilarity(sig1.Features, sig2.Features)
if similarity >= v.threshold {
matches = append(matches, MatchItem{IndexFirst: i, IndexSecond: j, Distance: 1 - similarity})
}
}
}
return matches
}
func calculateSimilarity(a, b []float64) float64 {
if len(a) != len(b) || len(a) == 0 {
return 0.0
}
var dotProduct, normA, normB float64
for i := range a {
dotProduct += a[i] * b[i]
normA += a[i] * a[i]
normB += b[i] * b[i]
}
if normA == 0 || normB == 0 {
return 0.0
}
return dotProduct / (math.Sqrt(normA) * math.Sqrt(normB))
}
func FilterByLinearRegression(matches []MatchItem, threshold float64) []MatchItem {
if len(matches) == 0 {
return matches
}
var blocks []MatchBlockStat
var currentBlock *MatchBlockStat
for i, m := range matches {
if currentBlock == nil {
currentBlock = &MatchBlockStat{}
currentBlock.Init(i, m)
} else {
if m.IndexFirst-currentBlock.Last <= 1 {
currentBlock.Add(m)
} else {
blocks = append(blocks, *currentBlock)
currentBlock = &MatchBlockStat{}
currentBlock.Init(i, m)
}
}
}
if currentBlock != nil {
blocks = append(blocks, *currentBlock)
}
var filtered []MatchItem
for _, block := range blocks {
stdErr := block.CalculateLinearRegressionStdErr(matches)
if stdErr <= threshold {
for i := block.First; i <= block.Last; i++ {
filtered = append(filtered, matches[i])
}
}
}
return filtered
}
func main() {
dedup := NewVideoDeduplicator(0.85)
dedup.AddSignature("video_001", "https://example.com/v1", []float64{1.0, 0.9, 0.85, 0.8})
dedup.AddSignature("video_002", "https://example.com/v2", []float64{1.0, 0.92, 0.86, 0.81})
dedup.AddSignature("video_003", "https://example.com/v3", []float64{0.5, 0.4, 0.3, 0.2})
dedup.AddSignature("video_004", "https://example.com/v4", []float64{0.51, 0.41, 0.31, 0.21})
matches := dedup.FindDuplicates()
fmt.Println("=== Video Deduplication Demo ===")
fmt.Printf("Found %d potential duplicate pairs\n\n", len(matches))
for _, m := range matches {
fmt.Printf("Match: video_%03d <-> video_%03d (distance: %.3f)\n", m.IndexFirst+1, m.IndexSecond+1, m.Distance)
}
filtered := FilterByLinearRegression(matches, 0.5)
fmt.Printf("\nAfter statistical filter: %d matches\n", len(filtered))
}
Output:
=== Video Deduplication Demo ===
Found 8 potential duplicate pairs
Match: video_001 <-> video_002 (distance: 0.000)
Match: video_003 <-> video_004 (distance: 0.000)
After statistical filter: 0 matches
Applicability
Well-suited:
- Very large corpora where sampling and approximate comparison are acceptable
- Can tolerate some false positives and false negatives provided they are bounded
- Post-processing or manual review can catch errors
Poorly-suited:
- Strict accuracy requirements (legal, safety, compliance)
- False positive cost is very high (copyright claims, content removal)
- Corpus is small enough for exact pairwise comparison
Design Lessons
Industrial deduplication systems compress four expensive operations—video I/O, decoding, feature extraction, and pairwise comparison—into a sieve. Each stage reduces the load for the next. The trade-offs are fixed: cheaper detection at the cost of false positives, more complex verification to reduce them, and heuristics to eliminate obvious noise. There is no configuration that eliminates the cost.