Table of contents
ADR 0115: Perceptual duplicate detection via dHash
Status: accepted Date: 2026-10-17
Context
The cleanup ("Aufräumen") surface must surface near-identical photos/videos so the owner can triage them. Upload-time dedup only catches byte-identical originals (shared StoredObject reuse), which misses the common re-export/re-encode/re-render duplicates. Two alternatives were rejected: CLIP embeddings (semantic similarity is not identity — a semantically related but different photo scores as similar, and embedding storage/inference adds an ONNX model lane where a pure pixel signature suffices) and exact SHA-256 (byte-identical uploads are already handled by upload-time dedup via shared StoredObjects, so exact hashing adds no new information for this problem). The library is local-first and privacy-first: candidate generation has to run inside the existing media worker pipeline without external services, without re-decoding originals, and with a query path that stays indexed as the library grows. The v1 dHash-64 (9x8, threshold 2) shipped in 1.21.x, but production measurement showed the receiver problem: of 4246 grouped pairs (v1 distance <= 2), 1051 pairs (25%) were burst/serial frames with capture times 0-10s apart and 256 pairs had times >10s apart — on 64 coarse gradient bits a burst frame with a slight pose change is indistinguishable from a true re-encode. The owner decided on a finer signature (phase 2) rather than a timestamp guard.
Decision
Use dHash-960 (v2): the media worker job compute_perceptual_hash resamples the SAME already-promoted 512px thumbnail (fallback: 2048px preview) to exactly 33x31 pixels (aspect forced), takes BT.601 luma and sets bit k = y*32+x (row-major, 0..959) when pixel (x,y) is strictly brighter than (x+1,y) — 32x30 comparison grid, 240 lowercase hex chars on the wire, algorithm string dhash_v2_960. Storage (V173): media_perceptual_hashes gets one row per (media_item_id, algorithm) — v1 rows stay as rollback data, queries and guards read ONLY hash_v2 IS NOT NULL. hash_v2 is BIT(960); bit k of the hex wire format is PG bit position k+1. Candidate generation with a real recall guarantee: hash_v2 is partitioned into 32 generated 30-bit block columns (v2_b0..v2_b31, substring(...)::bit(30)::integer — IMMUTABLE, no triggers) with one B-tree each. Pigeonhole: two hashes at Hamming distance <= 31 can touch at most 31 of the 32 blocks, so at least one block is identical — the UNION ALL over the 32 block-equality joins generates EVERY within-threshold pair, with no recall hole (v1's 4 x 16-bit blocks only guaranteed distance <= 3). The exact distance filter bit_count(h1.hash_v2 # h2.hash_v2) <= 15 runs per candidate arm in SQL (bit_count(bit) works directly on BIT(960); PostgreSQL has no bit_count(bigint)); transitive grouping via Union-Find, stable ordering minDistance ASC / size DESC / groupId ASC unchanged, minDistance stays on the v2 scale (0..960) in the unchanged response contract. Threshold 15 of 960 bits (1.6%), empirically tuned BEFORE the merge against the production library (evaluation harness PerceptualHashEvaluationTest: every thumbnail of all v1-grouped pairs re-hashed locally, v1 pipeline cross-check 4496/4496 = 100% against stored v1 values, filename-heuristic classification of every pair): at T=15 burst pairs captured 0-10s apart fall from 100% (v1 grouped 928 of set A) to 5 of 1051, >10s pairs (set D) to 18 of 256, and the v1-grouped burst-classified pairs overall (A+B+D) from 1346 to 75 (-94.4%); same-timestamp pairs keep 1779 of 2469 (72.1%), i.e. 1709 of the 2066 non-burst pairs (82.7%) — pixel-identical duplicates (distance 0) always stay. The literal target pair (A+D empty AND B >= 98%) is NOT jointly satisfiable on this data: B's tail is same-second bursts (EXIF timestamps have 1s precision — e.g. DSC01361/DSC01362 land in B) plus re-uploads of downscaled variants (a 256px thumb of a photo gets its own upscaled 512 thumbnail and hashes 100-200 bits away from the full-size sibling); B >= 98% needs T ~ 120-150, which re-introduces 669 of the 1051 A false positives. T=15 is the measured knee; raising it is a pure owner trade-off decision.
Consequences
Duplicates are found per owner across active media only (trashed/foreign items never group); the endpoint is review-only — no merge, no deletion. Backfill and promotion-time enqueue guards key off 'v2 hash missing' (a lingering v1-only row does not suppress a job); failed hash jobs stay re-enqueueable via backfill; the backfill response shape is unchanged. The worker computes and submits v2 only; a stale v1 worker image submitting dhash64 is rejected by the API (algorithm string is part of the protocol) and its job fails into the re-enqueueable lane. Candidate generation is COMPLETE for every threshold <= 31 (pigeonhole above) — the former v1 recall hole is gone. Measured query cost on the full production copy (27k media, 21.4k-item owner, 55k hash rows after backfill): the 32-arm candidate query ~1.06 s (v1 4-arm query ~0.10 s on the same data); ANALYZE at the end of V173 provides column statistics immediately (without any statistics the planner picked a pathological all-sequential plan, ~15 min, on a stats-free copy — autovacuum would not have run before the first request). Operational: after the deploy the user-triggered backfill (or the automatic post-promotion enqueue) computes v2 for existing media; v1 rows are inert rollback data. Rollback: revert the application code and re-enable the v1 read path (v1 rows and block indexes are untouched); dropping hash_v2 + the v2 columns/indexes and restoring UNIQUE (media_item_id) restores the v1-only shape. Perceptual hashes remain derived data: deleting/re-ingesting media cascades via the FK, and recomputation from a regenerated thumbnail simply upserts.
Memories Wiki
Using Memories
- Accounts, the Library Hub, and Data Export
- Albums and Automatic Suggestions
- Explore and Discovery Domains
- The Media Viewer
- People and Faces
- Places and Map
- Plants (In Development)
- Datenschutzerklärung (Privacy Policy)
- Fast, Progressive Image Loading
- Search
- Sharing and Households
- Timeline and Photos
- Uploading and Import
Self-Hosting
- Backup and Restore
- CLI Password Reset
- Deployment Architecture
- Known Issues and Operator Diagnostics
- Map Tiles and Place Data Privacy
- Storage Layout
- Upgrades and Versioning
- Workers
Reference