Is the picture content dedup really NxN?

[gbarrett28]

I have a use case for deduping that should be a lot better than NxN and I suspect it has likely already been impemented but wanted to find out from people who know before looking in the code....

I have several resolutions of upload to google photos that I want to weed out. This means that EXIF timestamp is a pretty good indicator of similairty but not 100% reliable. I was thinking of a flow that went something along the lines of:

1. Identify EXIF equivalence and then do fuller comparison within those sets (which I think can be linear rather than quadratic - more below).
2. Use the above equivalences to deduce file name mangling and do a fuller comparison within sets whose filenames correspond. This is probably enough for my use case as nearly all the duplicates will fall into one of these categories.
3. Rather than NxN for a general compare, take each comparison axis in turn (for each 15x15 grid point and each of RGB), sort the pictures on that axis and mark all pairs within the tolerance window. That should be much less complex than NxN (the sort is N log N and the tolerance window will give a sparse matrix).

Within the small equivalence candidate set where EXIF values are the same or filenames correspond, we can pick the picture that would be chosen from the set if they were all equivalent and compare each file to that. Most of the time, these sets will be equivalent, so the comparison is linear in the size of the set. Where not all files are equivalent, we can refine down to the files that aren't equivalent to the one we picked first and go again. That is quadratic worst case but only exceptionally.