Hacker News Reader

Comment by thomasmg | Hacker News Reader

I'm not sure what it means to have a recall of 50%... For nearest neighbour search, you would only find 5 of the top 10 nearest entries? What would be the algorithm of choice if I need to find 9 out of the top 10? Would it be LSH? (In our case, we have 1024 features, and plan to move to 2048; this is for image similarity search; a few million images)

View on HN

Given the top 100 results produced by a flat index - how many of those are returned in the top 100 of our PQ/IVFPQ index. Although it's worth noting that this is at the lower end of performance for PQ, using the same Sift1M dataset we can hit 76% with IVFPQ using nlist=256, m=32, and nbits=8. I'm sure this could be increased with a little more fine-tuning too. A couple of options:

* IVFPQ seems reasonable but unlikely to hit 90%

* HNSW could be a fast and accurate alternative

* a Flat IVF index could definitely reach 90%, but it may be slow

My understanding: it normally sits at the bottom of the ranking algo. You are looking at whether the final top 10 will be in the top 10,000 (out of tens of millions) most of the time. After getting the top 10,000, you can do more finer-grain ranking to get the final top 10.

Yes, so you get the top 10'000 using e.g. an IVF+PQ index, then from those get the top 10 using brute-force.

In addition to these other answers, a commonly used metric in the literature is the k-Recall@R, or the portion of the top k ground-truth vectors that are found in the top R ANN queries. This parametrization can make it clearer when comparing between different approaches

For your case, you might find it helpful to look at the excellent ann-benchmarks.com, and in particular the benchmarks for GIST, which is an image embedding.

Reply on news.ycombinator.com