Investigate various implementations of ann search for vector fields

[mayya-sharipova]

ann (approximate nearest neighbours) will be a licensed feature of Elasticsearch (not OSS).

We plan to implement prototypes of various algorithms for ann for different distance metrics:

• LSH and multiprobe LSH for euclidean distance
• partition trees for euclidean/cosine distance
• clustering-based approaches, including product quantization

We are interested in users' feedback about:

• application domains
• what distance metrics are used (euclidean vs cosine vs Hamming etc).
• what are data types in vectors (vectors of integers, bits, longs, floats etc).

We have decided to adopt Lucene implementations on ann search, so development of ann search is moved here. Relevant Lucene issues: https://issues.apache.org/jira/browse/LUCENE-9004, https://issues.apache.org/jira/browse/LUCENE-9322, https://issues.apache.org/jira/browse/LUCENE-9136

[elasticmachine]

Pinging @elastic/es-search

[wmelton]

You should also consider Covering-LSH - it, with some recent optimizations, appears to solve the false-negative problem common with LSH approaches.

https://arxiv.org/abs/1507.03225

There appear to be some early implementations in C++ already available, however, these do not appear to include the Hadamard code examples in the later white paper revisions that offer performance improvements.

https://github.com/kasperisager/hemingway

[markhuds]

@mayya-sharipova are you interested in using existing commodity approximate nearest neighbors implementations or implementing an algorithm from scratch? Annoy is a simple to use, simple to tune library created by spotify to perform ann search from an index stored on disk. It indexes vectors with integers which I think you also do behind the scenes. It looks like they also have java bindings so it could maybe fit well with your stack https://github.com/spotify/annoy-java

[mayya-sharipova]

@markhuds Thanks for your suggestion. We are currently evaluating different ann approaches based on the performance but also based how they fit into our elasticsearch/lucene infrastructure. We have considered spotify annoy's approach as well. We still need to make a decision.

We are interested in your use case for the ann search. For what use case have you found annoy compelling?