1 Introduction↩︎

Nearest Neighbor (NN) search is a fundamental problem in many domains of computer science, including image processing, information retrieval, and recommendation systems. NN algorithms search through a dataset \(X\) of \(d\)-dimensional vectors to identify the \(k\) nearest neighbors to a given query point \(x \in \mathbb{R}^d\). While exact solutions to this problem are computationally feasible in low-dimensional spaces, exact nearest neighbors search algorithms are no better than brute-force linear scans in high-dimensional settings. Approximate Nearest Neighbors (ANN) techniques tackle this aspect by giving up on exactness to offer a valuable trade-off between accuracy and efficiency. These techniques are especially popular nowadays due to the advent of effective learned vector representations (embeddings) powered by Large Language Models. In response to this trend, several well-known ANN libraries have been developed.

Many of these libraries, such as NMSlib [1], DiskANN [2] (Microsoft), and ScaNN [3] [4] (Google) implement highly efficient ANN search algorithms optimized for speed and scalability. However, these solutions are typically built around specific indexing or quantization techniques, with rigid codebases that do not support easy integration of new components or generalization beyond their original design. This lack of flexibility poses a significant limitation for researchers and developers who need to prototype or modify ANN algorithms. Even FAISS [5], Meta’s comprehensive library for ANN search which provides a wide variety of indexing techniques and quantization methods, lacks the modularity required for advancing research in the field. FAISS is heavily engineered for performance, leading to specialized implementations of each ANN/quantization technique. For example, in the case of the IVF (Inverted File Index), FAISS provides ten distinct classes that implement several versions of IVF index coupled with different quantizers. This highly specific architecture makes it challenging to introduce new functionalities that apply across different IVF variants, limiting flexibility in experimental settings. Moreover, FAISS suffers from a lack of support for sparse datasets and —like other more specialized libraries— it lacks comprehensive and easily accessible documentation. This can make it challenging to quickly understand the codebase and the functioning of the library.

In this work, we introduce kANNolo, a new Rust library for ANN. Unlike existing libraries, kANNolo is designed having ANN researchers in mind. We design it by prioritizing the ease of modification and prototyping while also supporting generality. Indeed—and differently from available competitors—kANNolo implements state-of-the-art indexing techniques for both dense and sparse vectors, as well as quantization techniques. Specifically, we design kANNolo as a collection of abstract key components such as: 1) the dataset representation (dense/sparse), 2) the quantization method, and 3) the distance/similarity measure. Second, we exploit Rust traits —a mechanism for specifying shared behavior across types, defining a set of methods that implementing types must provide—, to implement the design above in a way that fully matches the potential unlocked by the abstraction. This modular design allows users to easily develop and integrate new indexes/quantizers and test them with minimal effort so to greatly simplify prototyping and experimentation in ANN research. Although being designed for research, kANNolo does not give up on performance. Through comprehensive benchmarks on two publicly available datasets, Sift1M and Ms Marco, we show that kANNolo performs on par or better with the state-of-the-art competitors on both dense and sparse data, with a peak to 11.1\(\times\) and 2.1\(\times\) speedups over the best competitors respectively on dense and sparse data, establishing itself as one of the most competitive ANN search libraries.

2 Design of kANNolo↩︎

kANNolo is built with a modular architecture, consisting of four main components:

• One-Dimensional Arrays: The DArray1 trait provides a unified interface for dense and sparse vectors. This abstraction allows us to build indexes and perform ANN search independently on the kind of vectors we use.

• Quantizer: Quantizers transform high-dimensional data into more compact representations. They are abstracted through a Quantizer trait, enabling flexibility in the type of quantization used. kANNolo also supports an Identity quantizer which leaves the data unchanged, providing a standard interface regardless of whether any vector quantization method is applied.

• Query Evaluator: The QueryEvaluator trait is responsible for computing distances (or similarities) between dataset items and query points, and for ranking the results accordingly. It is tightly integrated with the quantizer, ensuring that all distance computations are conducted through a unified interface. This design abstracts the complexity of handling different data representations or quantization methods.

• Dataset: The Dataset trait represents a collection of one-dimensional arrays equipped with a quantizer. It dynamically integrates with a query evaluator during search operations and provides access to the data by masking the details on the kind of vectors it contains.

To better understand how these components interact, we illustrated the indexing pipeline of kANNolo in Figure 1 and the retrieval process in Figure 2.

In kANNolo, the dataset provides access to the data while the index is meant to pinpoint which vector shall be compared with the query. The indexing method currently implemented in kANNolo is the Hierarchical Navigable Small World graph (HNSW) [6], a graph index with a hierarchical links structure that has proved to be a state-of-the-art method both for dense and sparse retrieval. The quantization method that kANNolo implements is the Product Quantization [7], which quantizes the data into subspaces independently.

3 Experiments↩︎

In this section, we evaluate the performance of kANNolo by comparing it to the best ANN libraries implementing the same methods.

Datasets. For the dense domain, we evaluate kANNolo with Euclidean distance on the widely-known Sift1M dataset [8], consisting of vectors of handcrafted visual descriptors of images. Additionally, we test kANNolo with inner product on two sets of embeddings from the Ms Marco passages dataset [9], produced by the Star [10] and Dragon[11] models. For sparse retrieval, we use inner product on a sparse version of the Ms Marco dataset, where the Splade model generates embeddings [12]. For additional details about the tested datasets refer to Table 1.

Competitors. Dense competitors were selected based on their performance on the wide-recognized benchmark repository ANN benchmarks [13]. Specifically, they are: 1) Faiss, Meta’s library for ANN search with support for a wide range of ANN methods, including HNSW and PQ; 2) hnswlib[6], the original implementation of the HNSW algorithm, part of the nmslib library [1]; 3) N2[14], a lightweight ANN library implementing HNSW.

The sparse competitors are the winner submissions of the “Sparse Track” at NeurIPS 2023 Big ANN challenge [15], namely GrassRMA[16] and PyAnn[17]. These methods implement HNSW with only some minor optimizations, as kANNolo. We leave the comparison with inverted indexes for future work [18].

Reproducibility and Hardware Details. We implemented kANNolo in Rust (version \(1{.}83\)) with the compiler’s highest optimization level enabled. We conduct experiments on a server with one Intel i9-9900K CPU clocked at 3.60GHz, with \(64\) GiB of RAM. We query the indexes using a single thread.

3.1 Experimental Results↩︎

In this section, we experimentally show that kANNolo meets both its goals:

Modularity. The tests on both sparse and dense datasets, with plain and product quantizers, were conducted using the same indexing algorithm, which operates independently of the vector representation, quantizer, and similarity measure used. On the other hand, all our competitors have specialized implementations tailored for the vector type or quantization method used;

Performance: kANNolo achieves an improvement over state-of-the-art libraries in terms of accuracy-speed trade-off (Figure 3). On dense data, kANNolo is competitive with the state-of-the-art libraries on Sift1M dataset, while it outperforms its competitors on Ms Marco. In particular, kANNolo is up to \(11.1\times\) faster than Faiss as it builds the HNSW graph on the original representations of the vectors rather than on the quantized ones. On sparse vectors kANNolo outperforms both competitors, with up to 2.1\(\times\) speedup.

4 Conclusions and Future Work↩︎

We introduced kANNolo, a Rust-based library for approximate nearest neighbors search. It is designed to ease the prototyping and development of new ANN algorithms. Our extensive benchmarking on several public dense/sparse datasets shows that kANNolo achieves genuine modularity while also delivering state-of-the-art performance against well-known competitors. These results confirm that kANNolo is a valuable tool for effectively advancing ANN research.

As future work, we plan to extend kANNolo with additional indexing and quantization methods, thereby providing researchers with a broader experimental playground.

Acknowledgments↩︎

This work was partially supported by the Horizon Europe RIA “Extreme Food Risk Analytics” (EFRA), grant agreement n. 101093026, by the PNRR - M4C2 - Investimento 1.3, Partenariato Esteso PE00000013 - “FAIR - Future Artificial Intelligence Research” - Spoke 1 “Human-centered AI” funded by the European Commission under the NextGeneration EU program, by the PNRR ECS00000017 Tuscany Health Ecosystem Spoke 6 “Precision medicine & personalized healthcare” funded by the European Commission under the NextGeneration EU programme, by the MUR-PRIN 2017 “Algorithms, Data Structures and Combinatorics for Machine Learning”, grant agreement n. 2017K7XPAN_003, and by the MUR-PRIN 2022 “Algorithmic Problems and Machine Learning”, grant agreement n. 20229BCXNW.

References↩︎