2 ms·
He means that even though the chance of two random images colliding is ~ 1/ 2 trillion, once you get up to a set of order sqrt(2 trillion) you have a good chan
by sweezyjeezy 5y ago
He means that even though the chance of two random images colliding is ~ 1/ 2 trillion, once you get up to a set of order sqrt(2 trillion) you have a good chance of having a collision amongst all pairs.
- throwaway287391 5y agoThat explains the "birthday paradox" part, what I'm unclear on is the need for a "collision search algorithm" that isn't just "build a hashmap" which should take roughly O(N) time. (I suppose it could just be that, but I'm surprised it's even mentioned in that case. In my uncle(?) comment I wrote an 8 line Python implementation that runs in 3 seconds on my laptop.)