You don't have to compare all images to one another and doing so wouldn't reliably dedupe - what if one image is slightly different resolution, different image

You don't have to compare all images to one another and doing so wouldn't reliably dedupe - what if one image is slightly different resolution, different image type, different metadata, etc? They would different hashes but still basically the same data. I think the way you do it is to train a model to represent images as vectors. Then you put those vectors into a BTree which will allow you to efficiently query for the "nearest neighbor" to an image on log(n) time. You calibrate to find a distance that picks up duplicates without getting too many non-duplicates and then it's n log(n) time rather than n^2. If that's still too slow there is also a thing called ANNOY which lets you do approximate nearest neighbor faster.