A Versatile Implementation of HNSW for Efficient Approximate Nearest Neighbor Search

In this thesis, I present the implementation of a Hierarchical Navigable Small World (HNSW) graph for approximate nearest neighbor (ANN) search, developed in Rust and integrated into the KANNolo library developed by the Consiglio Nazionale delle Ricerche (CNR) and University of Pisa. This implementation is designed for versatility, supporting both dense and sparse datasets, as well as two different types of quantizers. The primary role of a quantizer is to encode vectors, reducing dimensionality for more efficient computation. One of the supported quantizers does not encode the vectors, allowing the HNSW index to work with the original data, while the other employs the Product Quantization (PQ) process to efficiently encode the vectors. The HNSW implementation is adaptable across different datasets and quantizers, as they just need to implement the Dataset and Quantizer traits, respectively. These traits are defined and implemented in the KANNolo library to establish the required functionality. This design ensures future extensibility, allowing the HNSW index to support new datasets or quantizers by simply implementing these traits, making it highly adaptable to evolving requirements in similarity search tasks.