Image Matching Algorithm Performance

2 posts · Dec 2019 – Dec 2020

What this trail covers

Cloudflare's image matching capabilities have evolved to address performance bottlenecks in high-dimensional data. Initial approaches using naive quadratic algorithms and SIMD optimizations (AVX2) showed limited gains due to memory bandwidth constraints. Advanced algorithms like VP-trees struggled with the 'curse of dimensionality' in 144-dimensional spaces. Subsequent efforts focused on optimizing brute-force methods by introducing a 'short distance' variation that computes a subset of dimensions, and further refined by considering the 'origin distance' to quickly discard non-matches based on a threshold.

All Cloudflare trails

Dec 2020Computing Euclidean distance on 144 dimensionsThis post details the challenges and optimizations involved in computing Euclidean distance for 144-dimensional fuzzy hashes used in image matching. It explores naive quadratic algorithms, SIMD (AVX2) optimizations, and the limitations of VP-trees due to the 'curse of dimensionality'. The key innovation presented is the 'short distance' variation, which computes distance on a subset of dimensions (32 out of 144) to quickly discard non-matches, significantly improving performance by reducing the need for full distance calculations. Further refinement with an 'origin distance' variation, leveraging the application's expectation of few matches, further boosts performance by quickly discarding non-matches based on a threshold.
Dec 2019Announcing the CSAM Scanning Tool, Free for All Cloudflare CustomersIntroduced a CSAM Scanning Tool for all Cloudflare customers, leveraging fuzzy hashing (PhotoDNA) to identify visually similar images. The tool automatically flags CSAM, blocks access with a 451 status code, and supports proper reporting. This builds upon existing image matching algorithm performance work by applying fuzzy hashing techniques to a critical security and content moderation use case.
Advertisement