Look into ACORN-1, or another algorithm to aid in filtered HNSW search

[benwtrent]

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: weaviate/weaviate#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-gamma part of the paper and focus in on Acorn-1. I am not sure we need to adjust the graph construction.

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).