3 ms·
I'd be curious how this stacks up on ANN-benchmarks (https://ann-benchmarks.com/ https://ann-benchmarks.com/). FWIW exhaustive search is still probably good en
by huac 3y ago
I'd be curious how this stacks up on ANN-benchmarks (https://ann-benchmarks.com/ https://ann-benchmarks.com/).
FWIW exhaustive search is still probably good enough for most use cases. IMO the exhaustive search should use a heap https://github.com/fennel-ai/fann/blob/main/src/main.rs#L12 https://github.com/fennel-ai/fann/blob/main/src/main.rs#L12 as you're only looking for top-k, it reduces time and memory complexity greatly. On a relatively unoptimized Golang implementation (though much beefier hardware) I get ~100ms to process 1M vectors of 300 dim. Still quite a bit slower than approximate, of course, but in absolute terms probably good enough for most use cases, especially because many use cases don't have 1M vectors.
- zX41ZdbW 3y agoI've recently presented the approach with exhaustive search and heap, then iteratively adding simple indices, using ClickHouse. It works pretty well despite the overall usage simplicity. Video: https://www.youtube.com/watch?v=hGRNcftpqAk https://www.youtube.com/watch?v=hGRNcftpqAk Presentation: https://presentations.clickhouse.com/meetup74/ai/ https://presentations.clickhouse.com/meetup74/ai/ PS. It should work at the same speed as "bruteforce-blas" in the ANN benchmarks.
- huac 3y agonice, if I'm reading this right, you do random projection as a first stage filter, then exact search over the filtered subset? that's clever, did you test precision/recall at all?
- zX41ZdbW 3y agoYes, this is the idea. I set the threshold for approximate search with a margin so that on a few test queries, I get 100% recall, and then it is filtered by precise search. But I didn't evaluate it thoroughly. The threshold for Hamming distance over bit masks was set almost arbitrarily, and it will be interesting to test further.