​​Filterable approximate nearest neighbors search I did a lit | Neural Networks Engineering

​​Filterable approximate nearest neighbors search

I did a little research on how to search in vector space if you also need to take into account additional restrictions: search in a subset, filter by a numerical criterion or geo.
The article turned out to be too large for the telegram channel format, so I’ll leave only the essence here.
The full article is available on my updated blog.

The main point is that with minor modifications of the state-of-the-art HNSM algorithm we can cover a variety of filtering cases.
Modifications are to add edges to a navigation graph to ensure that it is connected after filtering out some part of its nodes.

Looking at filtering by category we can see that adding edges within particular small categories solve the connectivity problem for them.
And large categories sustain its connectivity due to the law of the Percolation theory.
Filtering by categories with could be relatively easy be extended to the numerical range filtering and geo spatial index.

At the full version of this article I also present a couple experiments to prove this approach.
It also contains some consideration of how to avoid possible failures.
Take a look at it!