#approximate-nearest-neighbor-search #hnsw #instant #distance

instant-distance

Fast minimal implementation of HNSW maps for approximate nearest neighbors searches

10 releases (5 breaking)

0.6.0 Aug 1, 2022
0.5.1 Mar 28, 2022
0.5.0 May 20, 2021
0.4.0 Apr 30, 2021
0.1.3 Feb 17, 2021

#1 in #approximate-nearest-neighbor-search

Download history 510/week @ 2022-10-05 274/week @ 2022-10-12 261/week @ 2022-10-19 401/week @ 2022-10-26 735/week @ 2022-11-02 87/week @ 2022-11-09 12/week @ 2022-11-16 6/week @ 2022-11-23 41/week @ 2022-11-30 93/week @ 2022-12-07 135/week @ 2022-12-14 44/week @ 2022-12-21 36/week @ 2022-12-28 64/week @ 2023-01-04 100/week @ 2023-01-11 59/week @ 2023-01-18

259 downloads per month

MIT/Apache

36KB
826 lines

Cover logo

Instant Distance: fast HNSW indexing

Build status License: MIT License: Apache 2.0

Instance Distance is a fast pure-Rust implementation of the Hierarchical Navigable Small Worlds paper by Malkov and Yashunin for finding approximate nearest neighbors. This implementation powers the InstantDomainSearch.com backend services used for word vector indexing.

What it does

Instant Distance is an implementation of a fast approximate nearest neighbor search algorithm. The algorithm is used to find the closest point(s) to a given point in a set. As one example, it can be used to make simple translations.

Using the library

Rust

[dependencies]
instant-distance = "0.5.0"

Example

use instant_distance::{Builder, Search};

fn main() {
    let points = vec![Point(255, 0, 0), Point(255, 0, 0), Point(255, 0, 0)];
    let values = vec!["red", "green", "blue"];

    let map = Builder::default().build(points, values);
    let mut search = Search::default();

    let cambridge_blue = Point(163, 193, 173);

    let closest_point = map.search(&cambridge_blue, &mut search).next().unwrap();

    println!("{:?}", closest_point.value);
}

#[derive(Clone, Copy, Debug)]
struct Point(isize, isize, isize);

impl instant_distance::Point for Point {
    fn distance(&self, other: &Self) -> f32 {
        // Euclidean distance metric
        (((self.0 - other.0).pow(2) + (self.1 - other.1).pow(2) + (self.2 - other.2).pow(2)) as f32)
            .sqrt()
    }
}

Testing

Rust:

cargo t -p instant-distance --all-features

Python:

make test-python

Dependencies

~2–6.5MB
~106K SLoC