Filtrable HNSW

Andrei Vasnetsov explores the potential of enhancing the Hierarchical Navigable Small World (HNSW) algorithm to incorporate constraints directly during the search process, rather than applying conditions post-search, which is common with other approximate nearest neighbor (ANN) search libraries like Annoy and FAISS. The modified approach involves applying filter criteria to the nodes within the HNSW navigation graph, allowing for searches that adhere to specific conditions such as categorical filtering, numerical ranges, or geographical constraints. This method leverages principles from Percolation theory to maintain graph connectivity despite node removal and aims to ensure the search remains effective by adjusting parameters like the number of edges per node. Vasnetsov suggests that, for categorical filtering, additional edges within each category can maintain connectivity, while geographical searches can utilize geohashing to connect graph nodes. The article acknowledges that implementing these modifications in real-world systems would require a more efficient version, such as NMSLib, to meet production-level performance demands.