meilisearch/arroy

What it solves

Arroy is a Rust library designed for approximate nearest neighbor (ANN) search. It allows users to find vectors in a high-dimensional space that are closest to a target vector, specifically addressing the problem of memory-bound searches when dealing with millions of documents in high-dimensional spaces (e.g., 768 or 1536 dimensions).

How it works

Arroy uses random projections to build a forest of trees. At each node, a random hyperplane divides the space into two subspaces. This process is repeated multiple times to create a forest. To handle Dot Product distance, it transforms vectors from dot space to a query-friendly cosine space.

Who it’s for

It is intended for developers building applications that require efficient, low-memory vector search, particularly those using Rust and those who need to share the index across multiple processes via LMDB.

Highlights

• LMDB-based storage: Uses a memory-mapped key-value store to allow multiple processes to share the same data and perform atomic modifications.
• Low memory footprint: Optimized for small memory usage, enabling the indexing of large datasets that exceed available RAM.
• Multiple distance metrics: Supports Euclidean, Manhattan, cosine, and Dot (Inner) Product distances.
• Concurrent access: Supports multithreaded tree building using rayon and allows lookups to occur while another index is being modified.
• Enhanced features: Includes filtering during queries and the ability to incrementally update the tree without a full rebuild.