Hacker News Reader

Comment by SilasX | Hacker News Reader

>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.

View on HN

In 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.

>We don't care that any two images have the same hash,

Why not?

Based 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.

How 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?

Those 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

You 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.

Reply on news.ycombinator.com