4 ms·
> In order to test things, I decided to search the publicly available ImageNet dataset for collisions between semantically different images. I generated NeuralH
by tehnub 5y ago
> In order to test things, I decided to search the publicly available ImageNet dataset for collisions between semantically different images. I generated NeuralHashes for all 1.43 million images and searched for organic collisions. By taking advantage of the birthday paradox, and a collision search algorithm that let me search in n(log n) time instead of the naive n^2, I was able to compare the NeuralHashes of over 2 trillion image pairs in just a few hours.
I don't know what the author means by "taking advantage of the birthday paradox". If they're referring to the "birthday attack" [0], I don't think it makes sense. The birthday attack is a strategy that helps you find a collision without hashing every single image, but he states that he already generated NeuralHashes for all 1.43 million images.
Furthermore, isn't there a simple linear time algorithm to detect collisions given that you already have all the hashes? Iterate over your NeuralHashes and put them into a hash table where the NeuralHash is the key, and the number of occurrences is the value. Whenever you insert something into a bucket and there's already something there, you have a neural hash collision.
[0]: https://en.wikipedia.org/wiki/Birthday_problem#Probability_table https://en.wikipedia.org/wiki/Birthday_problem#Probability_t...
- tibbar 5y ago1) the point of the birthday paradox is that even if two elements of a set are unlikely to overlap, in a large set it is much more likely than perhaps intuitive that some pair of elements overlap. 2) I’m assuming he did something like putting all the hashes in a list and sorting them, which is at least better than looking at each pair. As you say, it’s not optimal and also doesn’t seem particularly worth including in the otherwise very interesting post
- sweezyjeezy 5y agoBy "taking advantage of the Birthday Paradox" - he means that even though the chance of two random images colliding is ~ 1/1 trillion, if you have a set of size ~ sqrt(1 trillion) you have a good chance of having a collision amongst all pairs.
- tehnub 5y agoBut did the birthday paradox inform his procedure in any way? I guess he wouldn't have even attempted to do this at all if he didn't think it was likely to find collisions.