Problem
Canva stores a fast-growing collection of user media. Exact file hashes such as SHA512 or MD5 change completely after one pixel, a watermark or a quality change, so they only find byte-identical files. The team needed a lookup that returns all stored images within a small visual distance of a query image, at the scale of billions of images. Uses: storage deduplication and moderation takedowns.
Example from the article: an image and the same image with a small watermark have a perceptual-hash Hamming distance of 2, while their MD5 hashes are fully different.
Solution in brief
Compute a perceptual hash per image and search by Hamming distance with multi-index hashing: split each hash into segments and store every segment as a DynamoDB partition key. A query runs one lookup per segment, then filters the merged candidates by exact Hamming distance. At rollout the system was unusable until the split count was reduced and low-complexity images were left out of hashing.
Questions this case answers
- How to retrieve all stored items within a small Hamming distance of a query hash at billions-of-items scale with millisecond latency
- How to keep a key-value-store index for approximate matching from returning huge candidate sets because of skewed or low-entropy keys
- How to find visually duplicate or lightly edited images among billions of stored files in tens of milliseconds?
- How to choose the number of hash segments in multi-index hashing so that queries stay cheap?
Tools and methods
- Perceptual hashing (pHash) — hash from pixel content; similar images differ in few positions
- Hamming distance — number of differing positions between two hashes; the match criterion
- Multi-index hashing (Norouzi, 2012) — splits hashes into segments so a distance threshold needs only exact-match lookups
- DynamoDB — one row per hash segment: partition key = indexed segment, sort key = image id
Google or a one-time email code. No password.