3 ms·
>2 in 2 trillion image pairs Reporting the collision rate per image pair feels misleading. What you really want to know is the number of false positives per i
by SilasX 5y ago
>2 in 2 trillion image pairs
Reporting the collision rate per image pair feels misleading. What you really want to know is the number of false positives per image in the relevant set, not image pair, as that's the figure that indicates how frequently you'll hit a false positive.
- dhosek 5y agoIn fact, I'd argue that the collision rate per image pair is overestimating the collision rate. It's the flip side of the birthday paradox. We don't care that any two images have the same hash, we care about any image having the same hash as one in the set that we're testing against.
- SilasX 5y ago>We don't care that any two images have the same hash, Why not?
- snet0 5y agoBased on the pigeonhole principle alone, it will always be the case that collisions exist. The size of the digest is very likely smaller than the size of any given image.
- SilasX 5y agoHow is that relevant to whether “per image” or “Per image pair” is the right metric? Heck, how is it relevant to anything given that hash functions avoid collisions in practice, even given the pigeonhole principle?
- LodeOfCode 5y agoThose should only differ by a factor of 2 [the collision rate for an image is the number of collisions it has divided by the number of other images, so the average collision rate is the total collisions divided by n(n-1) vs. n(n-1)/2 pairs] which isn't particularly relevant at this scale
- SilasX 5y agoYou care about the total number of collisions, not collisions for a specific image, so they differ by a square -- hence the 1 in a trillion vs million difference.