benwtrent opened a new issue, #13940: URL: https://github.com/apache/lucene/issues/13940
### Description Lucene already does OK in filtered kNN search, but it can be better. An interesting paper in this area: https://arxiv.org/abs/2403.04871 Weaviate has done an implementation of such paper: https://github.com/weaviate/weaviate/pull/5369 The key idea is a multi-expansion search of the graph. Instead of pure fan out only looking at the current neighborhood, additional neighbor-neighborhoods are explored, regardless if you have collected all the candidates or not. This does allow some nice properties and honestly, doesn't seem that difficult to implement. I would ignore Acorn-lamba part of the paper and focus in on Acorn-1. I think for graph construction and storage, building from quantized estimations & potentially bi-partite graph organization of the nodes would be overall better. But, this "explore the next hop" thing does seem nice. Also, our recent connectivity improvements will only make filtered search better. One additional thought, I wonder if we should also allow more than one entry point into the bottom layer with filtered search? Honestly, all this optimization tuning can get tricky as you consider the filtering percentages (did the user filter out only 1% of the docs or 80% of them). -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
