Speeding Up Fuzzy Image Matching
Cloudflare's CSAM image scanning tool identifies known harmful images by computing a 144-byte fuzzy hash from each image, then searching a database of millions of known hashes for a match. The hash itself is designed for fuzzy matching: rather than requiring an exact byte-for-byte comparison, the algorithm accepts images that are "close enough" to a known hash, meaning we need to find the hash in a database that minimizes the Euclidean distance to our query hash. That distance is computed across all 144 bytes of the hash, treating each as a coordinate in 144-dimensional space.
Before a match is declared, the computed distance must fall below a threshold; in practice, most queries are expected to have no match in the database at all. The matching problem is therefore less about finding the single nearest neighbor and more about proving, quickly, that nothing qualifies as a match.
The Naive Approach
The most straightforward algorithm is a linear scan that compares a query hash against every hash in the database, computing the Euclidean distance for each pair. This can be done by accumulating the squared distance over all 144 dimensions, avoiding the expensive square root operation since comparing squared distances yields the same ordering. With a database of one million hashes, that approach requires on the order of 432 million arithmetic operations per query:
- 144 × 1M subtractions
- 144 × 1M multiplications
- 144 × 1M additions
A test suite using a database of one million random vectors and 1,536 query hashes took about 85 seconds total, or roughly 55ms per query on average. That is far too slow for a production workload that needs to handle thousands of queries per second.
SIMD Optimizations Limits
A natural optimization is to use AVX2 SIMD instructions to process multiple bytes in parallel. The supported approach loads 16 bytes at a time, widens the unsigned 8-bit values to 16-bit, subtracts the corresponding bytes of the query hash, accumulates the results, and converts partial sums to 32-bit integers. Because there is no single AVX2 instruction that computes the Euclidean distance between two 8-bit vectors, the implementation requires several steps: unpack the bytes, perform the subtraction, square the deltas, and accumulate across the entire 144-byte hash.
This AVX2 version delivered roughly a 3x improvement, bringing the cost down to about 17ms per query. But performance is now bounded by memory bandwidth: the 1 million-entry database occupies about 137MiB, so holding a CPU with a theoretical peak of roughly 25GB/s, simply reading the database costs at least 5ms. Further gains from the same algorithm are not possible.
Why Space Partitioning Fails
The obvious alternative is a space partitioning data structure like a vantage point tree. A VP-tree works by recursively splitting the dataset into points that are near to and far from a chosen vantage point, reducing the search to O(log(N)) nodes when a close match exists. This problem, however, exhibits the curse of dimensionality. With 144 dimensions, the search space is astronomically large, yet every point in the database sits in the same neighborhood: the maximum possible distance between any two points is 3060 (the square root of 255² × 144), and in practice the vectors are all relatively close to one another.
The result is that tree-based pruning fails for the common case of a query with no nearby match. The algorithm cannot meaningfully narrow the search space, ends up visiting roughly half of the tree’s nodes, and the overhead of the tree walk makes it slower overall than a straight brute-force scan.
Short-Distance Filtering
A key observation turns the problem around: to eliminate the vast majority of database entries, we do not need to compute the full 144-byte distance. The Euclidean distance is monotonically non-decreasing as more dimensions are added to the sum. If the distance computed across a small subset of dimensions — say 32 of the 144 bytes — already exceeds the best score seen so far, no amount of additional computation can bring the full distance below that value.
This suggests the algorithm:
- Extract a 32-byte subset of the query hash.
- Compare it against precomputed and densely packed 32-byte subsets for every hash in the database.
- If the short distance exceeds the current best match, move on immediately.
- Only for the rare entry that is still plausible, compute the full 144-byte distance.
In the realistic use case, we do not need to find the single closest hash. Instead, we need to establish that no hash exists within a predefined distance threshold. With a threshold of 220 (squared distance 48,400), almost every database entry will fail the short-distance test, so the full distance computation almost never runs. Between the reduced 32-byte comparison and the threshold check, this variant substantially cuts both the memory traffic and the arithmetic load. An additional ordering trick, in which database hashes are sorted by their distance from a fixed origin point, allows the search to consider only hashes whose origin distance falls within a band of ± threshold from the query's origin distance, gaining roughly a 20% speedup.
Transposed Data for AVX2
Further AVX2 gains came from a data layout change rather than from new instruction selection. The original implementation stored each hash contiguously, so computing a distance requires loading 16 bytes from the query hash and 16 bytes from a single database entry. Instead, the database can be transposed: rather than storing entries as rows
[a1, a2, a3][b1, b2, b3][c1, c2, c3]
the data is stored column-wise in memory:
[a1, b1, c1][a2, b2, c2][a3, b3, c3]
Now a single load fetches the same byte from many different database hashes. The AVX2 code can then perform the subtraction, multiplication and addition on 16-bit values using _mm256_sub_epi16, _mm256_mullo_epi16 and _mm256_adds_epu16, the saturating add being sufficient since the squared threshold fits comfortably in a 16-bit integer. This layout converts what was scattered reads and horizontal reduction work into a set of straightforward and fast vertical SIMD operations over 16 database hashes at a time.
Combined with the short-distance filter and careful batching, the performance improvement is dramatic:
- Naive scalar: 55ms / query
- Naive AVX2: 17ms / query
- Short-distance, transposed AVX2: 0.73ms / query
Additional micro-optimizations remain, such as memory prefetching or the use of huge pages, but the tuning returns diminish quickly at this point.
The lesson is a familiar one for high-performance systems work. More complex algorithms promised better asymptotic behavior, but the actual data distribution defeated them. A straightforward brute-force scan, once optimized for the CPU's memory subsystem and AVX2 instruction set, was the winner. The effort was specific to x86 CPUs; a GPU with CUDA intrinsics like vabsdiff4 and dp4a matched the Euclidean distance computation extremely well, but the cost of server-grade GPUs is hard to justify when equivalent throughput can be had from commodity CPU cores. For this workload, carefully tuned AVX2 code on general-purpose hardware was the right choice.
