Crate granne

Granne (graph-based retrieval of approximate nearest neighbors) provides approximate nearest neighbor search among (typically) high-dimensional vectors. It focuses on reducing memory usage in order to allow indexing billions of vectors.

Note: There is currently a limit on the number of elements that can be indexed: 2^32 - 2 == 4_294_967_294.

Overview

• Granne is the main struct used for querying/searching for nearest neighbors.
• GranneBuilder is used to build Granne indexes.
• Index and Builder are traits implemented for all Granne and GranneBuilder types, since both Granne and GranneBuilder are generic over the type of elements.
• SumEmbeddings support the use case where the element are constructed by summing a smaller number of embeddings.

Memory-mapping

Granne uses memory-mapping for both index and elements. This makes it possible to lazy-load and use the index without loading all of it into memory (or share the index between different process).

Unfortunately, memory-mapping requires unsafe code to load the index/elements. The reason is that Granne cannot guarantee that the underlying file is not modified (by some other thread or process) while being memory-mapped.

For more information on the unsafe:ness of memmap, please see the memmap crate or refer to this discussion on users.rust-lang.org.

Examples

Basic building, saving and loading

For information on how to read/load/create elements see e.g. angular or the glove.rs example.

use granne::{Granne, GranneBuilder, Index, Builder, BuildConfig, angular};

let elements: angular::Vectors = /* omitted */

// building the index
let mut builder = GranneBuilder::new(BuildConfig::default(), elements);
builder.build();

// saving to disk
let mut index_file = tempfile::tempfile()?;
builder.write_index(&mut index_file)?;

let mut elements_file = tempfile::tempfile()?;
builder.write_elements(&mut elements_file)?;

// loading (memory-mapping) index and vectors
let elements = unsafe { angular::Vectors::from_file(&elements_file)? };
let index = unsafe { Granne::from_file(&index_file, elements)? };

// max_search controls how extensive the search is
let max_search = 200;
let res = index.search(&random_vector, max_search, num_results);

assert_eq!(num_results, res.len());

Modules

angular

This module contains element types for angular vectors using f32 as scalars.

angular_int

This module contains element types for quantized angular vectors using i8 as scalars.

embeddings

A module for elements that can be embedded into vector spaces.

Structs

BuildConfig

BuildConfig is used to configure a GranneBuilder.

Granne

An index for fast approximate nearest neighbor search. The index is built by using GranneBuilder and can be stored to disk.

GranneBuilder

A builder for creating an index to be searched using Granne. Configured by BuildConfig.

Traits

Builder

This trait is implemented for any GranneBuilder and contains methods that are common for all element types.

Dist

Dist<Other> - A trait for types E and Other between which a distance can be computed.

ElementContainer

A trait for any type containing elements to be indexed using GranneBuilder and/or used for searching with Granne.

ExtendableElementContainer

A trait for ElementContainers that can be extended with more elements

Index

This trait is implemented for any Granne and contains methods that are common for all element types.

Permutable

A trait for ElementContainers that can be permuted/reordered

Writeable

A trait for types that are writeable to a buffer