Simple, Fast, and Scalable Reverse Image Search

Interesting read. Especially the lookup method based on partitioning.<p>I tried to implement a similar reverse image search based on dHash as explained here <a href="https:&#x2F;&#x2F;github.com&#x2F;Rayraegah&#x2F;dhash" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;Rayraegah&#x2F;dhash</a> . However, I also had lookup performance problems. Exact matches are not a problem but the Hamming distance threshold matching is. Because my project was in Python, I tried to eke out more performance by writing a BK-tree backend module in C++ <a href="https:&#x2F;&#x2F;github.com&#x2F;mxmlnkn&#x2F;cppbktree" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;mxmlnkn&#x2F;cppbktree</a> It was 2 to 10x faster than an existing similar module but still was too slow when trying to look up something in a database of millions of images. However, as lookup tended to depend on the exact Hamming-distance threshold value, my next step would have been to try and optimize the hash. E.g, make it shorter so that only a short Hamming distance is necessary to be looked up but the mentioned multi-indexing method looks much more promising and tested.

“Fast Search in Hamming Space with Multi-Index Hashing” (<a href="https:&#x2F;&#x2F;www.cs.toronto.edu&#x2F;~norouzi&#x2F;research&#x2F;papers&#x2F;multi_index_hashing.pdf" rel="nofollow">https:&#x2F;&#x2F;www.cs.toronto.edu&#x2F;~norouzi&#x2F;research&#x2F;papers&#x2F;multi_in...</a>) is a great paper. Note that you can do significantly better (in terms of query latency&#x2F;throughput) with specialized implementations as in eg FAISS (<a href="https:&#x2F;&#x2F;github.com&#x2F;facebookresearch&#x2F;faiss&#x2F;wiki&#x2F;Binary-hashing-index-benchmark" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;facebookresearch&#x2F;faiss&#x2F;wiki&#x2F;Binary-hashin...</a>).

There is also <a href="https:&#x2F;&#x2F;rom1504.github.io&#x2F;clip-retrieval&#x2F;?back=https%3A%2F%2Fknn5.laion.ai&amp;index=laion5B&amp;useMclip=false" rel="nofollow">https:&#x2F;&#x2F;rom1504.github.io&#x2F;clip-retrieval&#x2F;?back=https%3A%2F%2...</a> which indexes the 5B images LAION dataset (basically a subset of the images from Common Crawl) and allows both text and image queries. The code as well as the image dataset is open source (although you need a new hard drive just to store the URLs).

4 requests per image lookup x 2000 requests per second = 8000 DynamoDB Reads per Second = 28,800,000 reads per hour<p>AWS price list says reserved instances come in at &quot;$0.00013 per RCU&quot; x 28,800,000 = $3744 per hour. Does this really cost $2.6 mio per month to operate?<p>If yes, contact me and I&#x27;ll be happy to save you $2.595 mio monthly by re-implementing things in C++ on bare metal servers.

I used ORB descriptors and Hamming Distance for a fuzzy&#x2F;partial&#x2F;inexact reverse image search at my last job. While it didn&#x27;t scale like the OP does, it found some really interesting fuzzy matches.

<a href="https:&#x2F;&#x2F;tineye.com" rel="nofollow">https:&#x2F;&#x2F;tineye.com</a> is pretty great for doing internet wide reverse image searches.

This was my internship subject (in another company) just before I graduated, I wonder what they used for the Perceptual Hash, ours was SIFT features. Happy to see that what I implemented would have been able to scale that much !

This looks to cool I didn&#x27;t know anything about perceptual hashing but the idea makes a lot of sense. I&#x27;m curious if the system lose its effectiveness if a user shifts an image a few pixels, reflects it, or apply a certain filter that makes all pixels have a slightly different tonality. I&#x27;m also thinking of some system maybe a small ML program that applies a minimal amount of noise to the image such that to the human eye it looks the same but pixel-wise is totally different.

95% of the time when I&#x27;m using reverse image search I&#x27;m just trying to find the original source of something. This is the opposite of what Google Lens focuses on but is a much simpler problem to solve :(

I would love to hear about the cost of this deployment.<p>10 billion images x4 rows each in Amazon DynamoDB with 2000 rps sounds like it&#x27;ll burn through your wallet faster than most explosives...

something i felt was missing from the piece - what is the typical hamming distance cutoff for something like this? he explains 2 is small enough to be identical but presumably it can go really high. what happens with a distance of like 100? what&#x27;s the state of research on false positives and adversarial attacks?