Giter VIP home page Giter VIP logo

arroy's Introduction

arroy

License Crates.io Docs dependency status Build

Arroy (Approximate Rearest Reighbors Oh Yeah) is a Rust library with the interface of the Annoy Python library to search for vectors in space that are close to a given query vector. It is based on LMDB, a memory-mapped key-value store, so many processes may share the same data and atomically modify the vectors.

Background

There are some other libraries to do nearest neighbor search. However, most of them are memory-bound, and none use LMDB for their storage. Annoy considered using LMDB as a backend since 2015. We built Meilisearch on top of LMDB; therefore, it was an obvious choice. As Annoy highly inspires it, we benefit from the same low memory footprint.

Why is this useful? If you want to find the nearest neighbors and have many CPUs, you only need to build the index once. Any thread will be able to query the LMDB-based index and will be able to do lookups immediately, even while another index is modifying it.

We use it inside Meilisearch. This library helps our users search for similar documents. Our users have many millions of them in a high-dimensional space (i.e., 768 on average and 1536 for OpenAI), so memory usage is a prime concern.

Arroy was built by @Kerollmops and @irevoire with the help of @dureuill in a week by porting the original C++ source code of Annoy.

Summary of features

  • Euclidean distance, Manhattan distance, cosine distance, or Dot (Inner) Product distance
  • Cosine distance is equivalent to Euclidean distance of normalized vectors i.e., sqrt(2-2*cos(u, v))
  • Works better if you don't have too many dimensions (like <100) but seems to perform surprisingly well even up to 1,000 dimensions
  • Small memory usage
  • Lets you share memory between multiple processes using LMDB
  • Index creation is separate from lookup (in particular, you can not add more items once the tree has been created)
  • Build index on disk to enable indexing big datasets that won't fit into memory using LMDB
  • Multithreaded tree building using rayon
  • Additional features compared to Annoy
    • Filter when querying
    • Incrementally update the tree without rebuilding it from scratch
    • Store and modify different indexes atomically using LMDB (indexes are identified by an u16)
    • Modify the items list in place while performing queries using LMDB
    • Storage based on LMDB using LMDB
    • Safer to use API, i.e., check dimensions, distances, etc
    • The database size does not depend on the highest item ID but on the number of items
    • Generic over your random number generator

Missing features

  • No Python support
  • No Hamming distance support
  • Generally slower due to the log(n) lookups and non-aligned vectors due to LMDB

Tradeoffs

Only two main parameters are needed to tune Arroy: the number of trees n_trees and the number of nodes to inspect during searching search_k.

  • n_trees is provided during build time and affects the build time and the index size. A larger value will give more accurate results but larger indexes.
  • search_k is provided in runtime and affects the search performance. A larger value will give more accurate results but will take a longer time to return.

If search_k is not provided, it will default to n * n_trees where n is the number of approximate nearest neighbors. Otherwise, search_k and n_trees are roughly independent, i.e., the value of n_trees will not affect search time if search_k is held constant and vice versa. Basically, it's recommended to set n_trees as large as possible given the amount of memory you can afford, and it's recommended to set search_k as large as possible given the time constraints you have for the queries.

How does it work

Using random projections and by building up a tree. At every intermediate node in the tree, a random hyperplane is chosen, which divides the space into two subspaces. This hyperplane is determined by sampling two points from the subset and taking the hyperplane equidistant from them.

We do this k times so that we get a forest of trees. k has to be tuned to your needs by looking at what tradeoff you have between precision and performance.

Dot Product distance (originally contributed by @psobot and @pkorobov) reduces the provided vectors from dot (or "inner-product") space to a more query-friendly cosine space using a method by Bachrach et al., at Microsoft Research, published in 2014.

Source code

It's all written in Rust and based on LMDB without a handful of ugly optimizations for performance and memory usage. You have been warned :)

The code should support Windows, thanks to LMDB and the Rust programming language.

Big thanks to the open-source community

  • Thanks to Qdrant for their SIMD distances functions
  • Thanks to Spotify for the original idea of Annoy

arroy's People

Contributors

curquiza avatar dureuill avatar irevoire avatar kerollmops avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

arroy's Issues

Make it possible to filter directly from arroy

At Meilisearch, we must ensure documents or vectors are hidden from some queries. The first version of the vector store feature was to iterate on the best results in the order found in the HNSW and conditionally ignore them. The complexity was O(n), which is not great when the user filters the results on a couple, e.g., 5, 10, 100.

We can do better than that now that we control the whole source code. There are two main solutions to implement:

  • When there is a fairly small number of selected items, compute the distance without going through the whole tree/graph. However, we need to define a correct threshold.
  • The algorithm must be more clever when many more items are selected. We will filter the items from the Descendant variant when "iterating" over the tree nodes in the nns_by_item/by_vector. We can barely not even touch the build phase. However, it would also be great to store bitmaps instead of lists of u32s in the Descendant nodes to be able to perform faster intersections.

We will also probably need to provide a nss_builder to reduce the number of conditional parameters to specify. For example, we can provide the RoaringBitmap to filter with, the number of trees to explore, and maybe two methods to query the database: with and without the distances (is it useful?).

TODO

  • Update the README's feature list

The `Side` function behave strangely on two dimensions

I wrote a visualizer of every iteration of two_means + the final repartition between the left children and right children on a split node.

At the very end of the split node function, we found two pretty good centroids:
image

But the final result we chose is this one:
image

The more dimensions we add, the less the issue shows.

Support binary quantization

It would be great to support binary quantization in arroy. The main principle is to convert the dimensions values x <= 0 to 0 and x > 0 to 1. This way, we can represent the quantized vector with 32x less space and compute the distances in a much faster and CPU-friendly. We are currently limited to something like 15M (float 32bit, 768dims) on a 63GiB machine, but with binary quantization, we can go up to 480M vectors on the same machine.

Here is an example of implementing the Euclidean distance with binary data. Here is the formula: $\sqrt{(p1-q1)^2+(p2-q2)^2}$.
This means that computing the difference at the power of two is equivalent to a xor:
$(0-1)^2 = (-1)^2 = 1$
$(1-0)^2 = 1^2 = 1$
$(0-0)^2 = 0$
$(1-1)^2 = 0$

Ultimately, the Euclidean operation is the sum of the XORed dimensions of both vectors squared: $\sqrt{(p1 \bigoplus q1)+(p2 \bigoplus q2)}$. All the necessary operations can be SIMD-optimized or maybe using the u8::BitXor and u8::count_ones methods will be SIMD-optimized by itself 🤔

Improve the deletion of `tmp_nodes`

Sometimes we need to delete new nodes previously inserted in the tmp_nodes.
From my understanding, it was always either the last one or the last last one, but it looks like it's not.

It would be good to check measure if we often do a lot of iterations, and if that's the case try to optimize it.

if let Some(el) = self.ids.iter_mut().rev().take(2).find(|i| **i == item) {

Update the pre-processor

  • About preprocess:
    • We can probably compute the max-norm on the fly while adding the items
    • If the max-norm doesn't change (from a doc addition OR deletion), then we don't need to run the second part of

Implement incremental updates

By keeping a list of unreachable_items that corresponds to the newly added or modified items we can make sure that the Writer::build method keeps track of them and insert them incrementally into all of the trees.

However, it must keep the split plane balanced and therefore recompute some of the normal along the way.

It must also make sure that the tree depth is growing with the number of items too. By appending new split plane if necessary and reducing the branch size. That could be a rebuild method that erase everything and start from the beginning to keep a good balance.

Measure and improve the constant numbers used when building the tree

We must take three parameters into account:

  1. Time to build the tree
  2. Relevancy of the searches
  3. Time to search in the tree

Fun fact: the lowest in the tree you are, the less impact a dummy plane has on the search cost.


arroy/src/writer.rs

Lines 248 to 259 in 7fc6031

if split_imbalance(children_left.len(), children_right.len()) < 0.95
|| remaining_attempts == 0
{
break normal;
}
remaining_attempts -= 1;
};
// If we didn't find a hyperplane, just randomize sides as a last option
// and set the split plane to zero as a dummy plane.
while split_imbalance(children_left.len(), children_right.len()) > 0.99 {

fn split_imbalance(left_indices_len: usize, right_indices_len: usize) -> f64 {
    let ls = left_indices_len as f64;
    let rs = right_indices_len as f64;
    let f = ls / (ls + rs + f64::EPSILON); // Avoid 0/0
    f.max(1.0 - f)
}

fn main() {
    dbg!(split_imbalance(29464, 18394));
    dbg!(split_imbalance(30000, 30000));
    dbg!(split_imbalance(30000, 1580));
}

Do not use the vector dimensions as the number of items in a descendant node

When porting the build tree functions from Annoy, we kept the constant value for the number of descendants we could fit into a descendant node. The reason why they were doing that is because they needed constant-length nodes. However, our system no longer needs this, as LMDB entries can have any length.

Appending items no longer works

It is no longer possible to append items in the database because we are updating the updated item IDs that live after the item entries. We could move the metadata information before the item entries. We must add a test for this method.

arroy/src/writer.rs

Lines 166 to 176 in 19e0a07

let mut updated = self
.database
.remap_data_type::<RoaringBitmapCodec>()
.get(wtxn, &Key::updated(self.index))?
.unwrap_or_default();
updated.insert(item);
self.database.remap_data_type::<RoaringBitmapCodec>().put(
wtxn,
&Key::updated(self.index),
&updated,
)?;

Look into binary indexes

One of our customers is interested in binary Indexes. It could be interesting to look into this. We can potential find a good fit with this.

BIN_FLAT
This index is exactly the same as FLAT except that this can only be used for binary embeddings.

For vector similarity search applications that require perfect accuracy and depend on relatively small (million-scale) datasets, the BIN_FLAT index is a good choice. BIN_FLAT does not compress vectors, and is the only index that can guarantee exact search results. Results from BIN_FLAT can also be used as a point of comparison for results produced by other indexes that have less than 100% recall.

BIN_FLAT is accurate because it takes an exhaustive approach to search, which means for each query the target input is compared to every vector in a dataset. This makes BIN_FLAT the slowest index on our list, and poorly suited for querying massive vector data. There are no parameters for the BIN_FLAT index in Milvus, and using it does not require data training or additional storage.

BIN_IVF_FLAT
This index is exactly the same as IVF_FLAT except that this can only be used for binary embeddings.

BIN_IVF_FLAT divides vector data into nlist cluster units, and then compares distances between the target input vector and the center of each cluster. Depending on the number of clusters the system is set to query (nprobe), similarity search results are returned based on comparisons between the target input and the vectors in the most similar cluster(s) only — drastically reducing query time.

By adjusting nprobe, an ideal balance between accuracy and speed can be found for a given scenario. Query time increases sharply as both the number of target input vectors (nq), and the number of clusters to search (nprobe), increase.

BIN_IVF_FLAT is the most basic BIN_IVF index, and the encoded data stored in each unit is consistent with the original data.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.