Graph-based Approximate Nearest Neighbor Search

Overview

granne*

Crates.io documentation license

granne (graph-based retrieval of approximate nearest neighbors) is a Rust library for approximate nearest neighbor search based on Hierarchical Navigable Small World (HNSW) graphs and is used in Cliqz Search. It focuses on reducing memory usage in order to allow indexing billions of vectors.

Features

  • Memory-mapped
  • Multithreaded index creation
  • Extensible indexes (add elements to an already built index)
  • Python bindings
  • Dense float or int8 elements (cosine distance)

Installation

Requirements

You will need to have Rust installed. This can be done by calling:

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

Or by visiting https://rustup.rs/ and following the instructions there.

Rust

# build
cargo build --release

# test
cargo test

# bench
cargo +nightly bench

Python

See Python Bindings.

Optional Requirements

granne can use BLAS (https://en.wikipedia.org/wiki/Basic_Linear_Algebra_Subprograms) to improve speed of some computations. On Debian/Ubuntu both libblas-dev and libopenblas-dev should work, with the latter being significantly faster.

BLAS can be enabled by passing the blas feature during compilation, e.g.

cargo build --release --features "blas"

On Mac OS there seems to be some issue (maybe this one) with the default BLAS library. A workaround is to install e.g. openblas and link to that instead.


*granne is Swedish and means neighbor

Comments
  • Error Compiling Granne

    Error Compiling Granne

    I am attempting to move over to the new v0.5.0 release but am encountering this error while trying to get it setup:

    $ pip install -e git://github.com/granne/[email protected]#egg=granne
    Obtaining granne from git+git://github.com/granne/[email protected]#egg=granne
      Updating /home/gabe/Envs/granne-test/src/granne clone (to revision v0.5.0)
      Running command git fetch -q --tags
      Running command git reset --hard -q 662656d2cb0aa43558d826e7f1e7568afb2ea36d
      Installing build dependencies ... done
      Getting requirements to build wheel ... done
      Installing backend dependencies ... done
        Preparing wheel metadata ... done
    Installing collected packages: granne
      Running setup.py develop for granne
        ERROR: Command errored out with exit status 1:
         command: /home/gabe/Envs/granne-test/bin/python3 -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'/home/gabe/Envs/granne-test/src/granne/setup.py'"'"'; __file__='"'"'/home/gabe/Envs/granne-test/src/granne/setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' develop --no-deps
             cwd: /home/gabe/Envs/granne-test/src/granne/
        Complete output (123 lines):
        running develop
        running egg_info
        writing granne.egg-info/PKG-INFO
        writing dependency_links to granne.egg-info/dependency_links.txt
        writing top-level names to granne.egg-info/top_level.txt
        writing manifest file 'granne.egg-info/SOURCES.txt'
        running build_ext
        running build_rust
               Fresh autocfg v1.0.0
               Fresh cfg-if v0.1.10
               Fresh lazy_static v1.4.0
               Fresh scopeguard v1.1.0
               Fresh regex-syntax v0.6.17
               Fresh smallvec v1.2.0
               Fresh ppv-lite86 v0.2.6
               Fresh adler32 v1.0.4
               Fresh itoa v0.4.5
               Fresh stable_deref_trait v1.1.1
               Fresh either v1.5.3
               Fresh thread_local v1.0.1
               Fresh lock_api v0.3.3
           Compiling granne v0.5.0 (/home/gabe/Envs/granne-test/src/granne)
             Running `/home/gabe/Envs/granne-test/src/granne/target/debug/build/granne-3065d63cc7adb6bb/build-script-build`
               Fresh libc v0.2.68
               Fresh maybe-uninit v2.0.0
               Fresh byteorder v1.3.4
               Fresh ryu v1.0.3
               Fresh serde v1.0.105
               Fresh memchr v2.3.3
               Fresh crc32fast v1.2.0
               Fresh num-traits v0.2.11
               Fresh getrandom v0.1.14
               Fresh num_cpus v1.12.0
               Fresh time v0.1.42
               Fresh parking_lot_core v0.7.0
               Fresh memmap v0.7.0
               Fresh madvise v0.1.0
               Fresh miniz_oxide v0.3.6
               Fresh owning_ref v0.4.1
               Fresh crossbeam-utils v0.7.2
               Fresh memoffset v0.5.4
               Fresh crossbeam-queue v0.2.1
               Fresh rand_core v0.5.1
               Fresh rand_chacha v0.2.2
               Fresh ordered-float v1.0.2
               Fresh aho-corasick v0.7.10
               Fresh crossbeam-epoch v0.8.2
               Fresh pbr v1.0.2
               Fresh parking_lot v0.10.0
               Fresh flate2 v1.0.14
               Fresh stream-vbyte v0.3.2
               Fresh serde_json v1.0.48
               Fresh fxhash v0.2.1
               Fresh regex v1.3.5
               Fresh crossbeam-deque v0.7.3
               Fresh rand v0.7.3
               Fresh rayon-core v1.7.0
               Fresh rayon v1.3.0
               Fresh python3-sys v0.4.1
               Fresh cpython v0.4.1
             Running `rustc --crate-name granne --edition=2018 src/lib.rs --error-format=json --json=diagnostic-rendered-ansi --crate-type lib --emit=dep-info,metadata,link -C debuginfo=2 --cfg 'feature="default"' -C metadata=7d4dec9265969171 -C extra-filename=-7d4dec9265969171 --out-dir /home/gabe/Envs/granne-test/src/granne/target/debug/deps -C incremental=/home/gabe/Envs/granne-test/src/granne/target/debug/incremental -L dependency=/home/gabe/Envs/granne-test/src/granne/target/debug/deps --extern byteorder=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libbyteorder-0a48faa69a27c0a8.rmeta --extern flate2=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libflate2-5c9df00987ebb4d3.rmeta --extern fxhash=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libfxhash-a9584c0803658a1c.rmeta --extern madvise=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libmadvise-2bff7c02f1d9a0f6.rmeta --extern memmap=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libmemmap-3467cfb5935cea6b.rmeta --extern ordered_float=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libordered_float-49b58c9dad452031.rmeta --extern owning_ref=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libowning_ref-88449d183d98535d.rmeta --extern parking_lot=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libparking_lot-e29d0e72287e3d37.rmeta --extern pbr=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libpbr-df0b03d13e7090cb.rmeta --extern rand=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/librand-34f070eb1e7a7deb.rmeta --extern rayon=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/librayon-da71c033c21c80ff.rmeta --extern serde_json=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libserde_json-5fd5b5f28b6a28d5.rmeta --extern stream_vbyte=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libstream_vbyte-92918a05764be3c1.rmeta`
        error[E0308]: mismatched types
          --> src/elements/dense_vector.rs:86:17
           |
        86 |                 Self(self.0.into_owned())
           |                 ^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
           |
          ::: src/elements/angular.rs:53:1
           |
        53 | dense_vector!(f32);
           | ------------------- in this macro invocation
           |
           = note: expected struct `elements::angular::Vectors<'static>`
                      found struct `elements::angular::Vectors<'a>`
        note: the lifetime `'a` as defined on the impl at 40:14...
          --> src/elements/dense_vector.rs:40:14
           |
        40 |         impl<'a> Vectors<'a> {
           |              ^^
           |
          ::: src/elements/angular.rs:53:1
           |
        53 | dense_vector!(f32);
           | ------------------- in this macro invocation
           = note: ...does not necessarily outlive the static lifetime
           = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)
        
        error[E0308]: mismatched types
          --> src/elements/dense_vector.rs:86:17
           |
        86 |                 Self(self.0.into_owned())
           |                 ^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
           |
          ::: src/elements/angular_int.rs:17:1
           |
        17 | dense_vector!(i8);
           | ------------------ in this macro invocation
           |
           = note: expected struct `elements::angular_int::Vectors<'static>`
                      found struct `elements::angular_int::Vectors<'a>`
        note: the lifetime `'a` as defined on the impl at 40:14...
          --> src/elements/dense_vector.rs:40:14
           |
        40 |         impl<'a> Vectors<'a> {
           |              ^^
           |
          ::: src/elements/angular_int.rs:17:1
           |
        17 | dense_vector!(i8);
           | ------------------ in this macro invocation
           = note: ...does not necessarily outlive the static lifetime
           = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)
        
        error: aborting due to 2 previous errors
        
        For more information about this error, try `rustc --explain E0308`.
        error: could not compile `granne`.
        
        Caused by:
          process didn't exit successfully: `rustc --crate-name granne --edition=2018 src/lib.rs --error-format=json --json=diagnostic-rendered-ansi --crate-type lib --emit=dep-info,metadata,link -C debuginfo=2 --cfg 'feature="default"' -C metadata=7d4dec9265969171 -C extra-filename=-7d4dec9265969171 --out-dir /home/gabe/Envs/granne-test/src/granne/target/debug/deps -C incremental=/home/gabe/Envs/granne-test/src/granne/target/debug/incremental -L dependency=/home/gabe/Envs/granne-test/src/granne/target/debug/deps --extern byteorder=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libbyteorder-0a48faa69a27c0a8.rmeta --extern flate2=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libflate2-5c9df00987ebb4d3.rmeta --extern fxhash=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libfxhash-a9584c0803658a1c.rmeta --extern madvise=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libmadvise-2bff7c02f1d9a0f6.rmeta --extern memmap=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libmemmap-3467cfb5935cea6b.rmeta --extern ordered_float=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libordered_float-49b58c9dad452031.rmeta --extern owning_ref=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libowning_ref-88449d183d98535d.rmeta --extern parking_lot=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libparking_lot-e29d0e72287e3d37.rmeta --extern pbr=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libpbr-df0b03d13e7090cb.rmeta --extern rand=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/librand-34f070eb1e7a7deb.rmeta --extern rayon=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/librayon-da71c033c21c80ff.rmeta --extern serde_json=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libserde_json-5fd5b5f28b6a28d5.rmeta --extern stream_vbyte=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libstream_vbyte-92918a05764be3c1.rmeta` (exit code: 1)
        cargo rustc --lib --manifest-path py/Cargo.toml --features cpython/extension-module cpython/python3-sys --verbose -- --crate-type cdylib
        error: cargo failed with code: 101
        
        ----------------------------------------
    ERROR: Command errored out with exit status 1: /home/gabe/Envs/granne-test/bin/python3 -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'/home/gabe/Envs/granne-test/src/granne/setup.py'"'"'; __file__='"'"'/home/gabe/Envs/granne-test/src/granne/setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' develop --no-deps Check the logs for full command output.
    
    

    I don't know rust so I'm a little lost with how to debug this.

    opened by os-gabe 3
  • Update cpython version & build updates

    Update cpython version & build updates

    Done:

    • Use default toolchain, instead of nightly (because cpython=0.6 doesn't requires nightly)
    • Get rid py35, add py38, py39, py310
    • Replace manylinux1_x86_64 -> manylinux2010_x86_64
    • Bump version to 0.5.2
    opened by menshikh-iv 2
  • How is reorder meant to be used?

    How is reorder meant to be used?

    Hello, I'm wondering what the intended use for the reorder method of Granne is. I would like to take advantage of better cache locality but I'm not quite sure when/how to use it. How can I incorporate this into my indexing workflow which currently looks like:

    DIMENSION = 512
    ELEMENT_TYPE = "angular"
    
    builder = granne.GranneBuilder("angular")
    metadata = []
    for _ in range(100000):
        metadata.append("some metadata about this element")
        vec = np.random.rand(DIMENSION) - 0.5
        builder.append(vec)
    
    builder.build()
    builder.save_index(fname_idx)
    builder.save_elements(fnames_elem)
    
    opened by os-gabe 2
  • Error building Python module with nightly

    Error building Python module with nightly

    First of all: Great work with Granne, absolutely impressive performance!

    Unfortunately I have been getting an error trying to build the Python module with the latest commits.

    error[E0308]: mismatched types
          --> src/elements/dense_vector.rs:86:17
           |
        86 |                 Self(self.0.into_owned())
           |                 ^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
           |
          ::: src/elements/angular.rs:53:1
           |
        53 | dense_vector!(f32);
           | ------------------- in this macro invocation
           |
           = note: expected struct `elements::angular::Vectors<'static>`
                      found struct `elements::angular::Vectors<'a>`
        note: the lifetime `'a` as defined on the impl at 40:14...
          --> src/elements/dense_vector.rs:40:14
           |
        40 |         impl<'a> Vectors<'a> {
           |              ^^
           |
          ::: src/elements/angular.rs:53:1
           |
        53 | dense_vector!(f32);
           | ------------------- in this macro invocation
           = note: ...does not necessarily outlive the static lifetime
           = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)
        
        error[E0308]: mismatched types
          --> src/elements/dense_vector.rs:86:17
           |
        86 |                 Self(self.0.into_owned())
           |                 ^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
           |
          ::: src/elements/angular_int.rs:17:1
           |
        17 | dense_vector!(i8);
           | ------------------ in this macro invocation
           |
           = note: expected struct `elements::angular_int::Vectors<'static>`
                      found struct `elements::angular_int::Vectors<'a>`
        note: the lifetime `'a` as defined on the impl at 40:14...
          --> src/elements/dense_vector.rs:40:14
           |
        40 |         impl<'a> Vectors<'a> {
           |              ^^
           |
          ::: src/elements/angular_int.rs:17:1
           |
        17 | dense_vector!(i8);
           | ------------------ in this macro invocation
           = note: ...does not necessarily outlive the static lifetime
           = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)
        
        error: aborting due to 2 previous errors
        
        For more information about this error, try `rustc --explain E0308`.
        error: could not compile `granne`.
    

    I could narrow it down to 7de618b09b8b68d04270d4ac9036b392dc098e6a. It seems that there is an issue with using nightly, as cargo +nightly bench gives a similar error already with earlier commits. I would love to get deeper into this but alas my knowledge of Rust is definitely only superficial.

    opened by tillbey 2
  • Rust panic when using large number of layers

    Rust panic when using large number of layers

    When running the build_and_search.py example I get the following error after changing the configuration to

    DIM = 256
    NUM_VECTORS = 100000
    NUM_LAYERS = 100
    
    Saving to disk
    thread '<unnamed>' panicked at 'assertion failed: metadata.len() <= METADATA_LEN', /tmp/pip-req-build-xonb6jzo/src/hnsw/io.rs:71:5
    stack backtrace:
       0: backtrace::backtrace::libunwind::trace
                 at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.37/src/backtrace/libunwind.rs:88
       1: backtrace::backtrace::trace_unsynchronized
                 at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.37/src/backtrace/mod.rs:66
       2: std::sys_common::backtrace::_print_fmt
                 at src/libstd/sys_common/backtrace.rs:76
       3: <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt
                 at src/libstd/sys_common/backtrace.rs:60
       4: core::fmt::write
                 at src/libcore/fmt/mod.rs:1030
       5: std::io::Write::write_fmt
                 at src/libstd/io/mod.rs:1412
       6: std::sys_common::backtrace::_print
                 at src/libstd/sys_common/backtrace.rs:64
       7: std::sys_common::backtrace::print
                 at src/libstd/sys_common/backtrace.rs:49
       8: std::panicking::default_hook::{{closure}}
                 at src/libstd/panicking.rs:196
       9: std::panicking::default_hook
                 at src/libstd/panicking.rs:210
      10: std::panicking::rust_panic_with_hook
                 at src/libstd/panicking.rs:473
      11: std::panicking::begin_panic
      12: granne::hnsw::io::save_index_to_disk
      13: granne::hnsw::HnswBuilder<Elements,Element>::save_index_to_disk
      14: granne::HnswBuilder::save_index
      15: cpython::objects::string::<impl cpython::conversion::RefFromPyObject for str>::with_extracted
      16: std::panicking::try::do_call
      17: __rust_maybe_catch_panic
                 at src/libpanic_unwind/lib.rs:80
      18: cpython::function::handle_callback
      19: granne::HnswBuilder::create_instance::init::wrap_instance_method
      20: PyCFunction_Call
      21: PyEval_EvalFrameEx
      22: <unknown>
      23: PyEval_EvalCode
      24: <unknown>
      25: PyRun_FileExFlags
      26: PyRun_SimpleFileExFlags
      27: Py_Main
      28: main
      29: __libc_start_main
      30: _start
    note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
    Traceback (most recent call last):
      File "examples/py/build_and_search.py", line 32, in <module>
        builder.save_index(INDEX_PATH)
    SystemError: Rust panic
    

    I guess a separate question is how to choose an appropriate number of layers.

    opened by os-gabe 2
  • Error running build_and_search.py

    Error running build_and_search.py

    When running granne/examples/py/build_and_search.py I get the following error:

    thread '<unnamed>' panicked at 'assertion failed: metadata.len() <= METADATA_LEN', /tmp/pip-req-build-3bq0acsr/src/hnsw/io.rs:71:5
    ---------------------------------------------------------------------------
    SystemError                               Traceback (most recent call last)
    <ipython-input-8-1b56a13d105e> in <module>()
         30 
         31 print("Saving to disk")
    ---> 32 builder.save_index(INDEX_PATH)
         33 builder.save_elements(ELEMENTS_PATH)
         34 
    
    SystemError: Rust panic
    

    I'm on Ubuntu 18.04. Let me know what other debug info would be useful.

    opened by os-gabe 2
  • Query the distance between two elements

    Query the distance between two elements

    Is there a way, from Python, to query the distance between any two arbitrary elements? I know I can retrieve the vectors and compute the distance myself but I want to be sure the distance is computed with exactly the same metric that granne uses internally.

    opened by os-gabe 1
  • rw_builder/mod.rs has incorrect `RwLock` guard usage

    rw_builder/mod.rs has incorrect `RwLock` guard usage

    A lock guard needs to be assigned to a binding that's not _ because doing otherwise creates a guard that's dropped immediately, releasing the lock. In other words:

    let _ = my_lock.write().unlock();
    

    is equivalent to

    my_lock.write().unwrap();
    

    I noticed this purely by accident while exploring this repo a bit, after seeing it linked from https://0x65.dev/blog/2019-12-06/building-a-search-engine-from-scratch.html

    opened by vitalyd 1
  • HNSW for biology

    HNSW for biology

    Dear granny team,

    This is Jianshu, a bioinformatics phd student at Georgia Tech. I am writing to you to ask your interest to form a new collaboration. Specifically, applying HNSW into genome classification problems, that is to find the closest genome in a big genome database to see the close related ones in the database so that enivronmental microbiologist can tell what taxonomy the query genome is. This will have a very big impact on the field and will definitely have a lot of citations. I want to completely rely on rust for this project without using any other language considering the advantages compared to C++ and python. I am not an expert in rust but have been using it for 2 years. The biology needed and taxonomy related information will be my strong part. I also know all the classification software in this field and have benign using/modifying them for my master and half of my Ph.D I am confident that HNSW in rust will greatly improved the speed of genome classifiers. Hopefully we can come up with a paper in the end. My email is [email protected]

    Let me know if you are interest and if something I mentioned above is not clear.

    Many thanks,

    Jianshu

    opened by jianshu93 0
  • setup.py attempts to import setuptools_rust before installing it

    setup.py attempts to import setuptools_rust before installing it

    On master setup.py imports Binding and RustExtension on line 2 even though setuptools_rust is a dependency of granne so it is not guaranteed it will be installed yet.

    This caused the the following error for me:

    pip install -e .
        Complete output (5 lines):
        Traceback (most recent call last):
          File "<string>", line 1, in <module>
          File "/home/gabe/code/granne/setup.py", line 2, in <module>
            from setuptools_rust import Binding, RustExtension
        ImportError: No module named 'setuptools_rust'
        ----------------------------------------
    ERROR: Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.
    

    I'll submit a PR with a fix shortly.

    opened by os-gabe 0
  • Question: best way to store a vector ID?

    Question: best way to store a vector ID?

    Is there a recommended best practice for storing an ID along with a vector?

    My use case is sentence embedding. I have many passages of text, and I'd like to be able to search that embedding.

    However, the problem is I'm trying to think of an optimal strategy to link a vector back to the original text. Near as I can tell, the IDs returned when running a search() are related to the order of insertion (i.e. first inserted index 0, second has index 1, etc.).

    Some ideas I thought of:

    • storing the vector ID in another database to provide mapping, but this would be a lot of boilerplate and complexity. I expect to need to remove items from the index from time to time as well which further complicates.
    • add a column in my embedding vector to store a numerical ID (but this might affect accuracy, if there's stray data)

    Any recommendations?

    opened by mmisiewicz 3
  • other distance metric

    other distance metric

    Hello granne team, I am wondering whether the angular distance by default can be any other metric distance like L1, L2, Cosine, Jaccard, Hamming distance? Another HNSW implementation provide such distances:https://github.com/jean-pierreBoth/hnswlib-rs

    Thanks,

    Jianshu

    opened by jianshu93 0
  • Deadlock on index building

    Deadlock on index building

    I got an deadlock on index building using python bindings on pytest. This reproduced only with specific test order (that's wired).

    I can't share full tests (sorry for that), but can mention important parts

    Granne version: 0.5.2 Python version: 3.8

    Code called in both tests looks like

    import granne
    
    index_builder = granne.GranneBuilder('angular', 500)
    for v in vectors:  # no matters how much `vectors` or dimensions
        index_builder.append(v)
    
    index_builder.build()  # < - deadlock happens here
    

    I traced them using py-spy and got stack that looks like

    Thread 73895 (idle): "MainThread"
        pthread_cond_wait@@GLIBC_2.3.2 (libpthread-2.31.so)
        core::sync::atomic::atomic_load::h40d363a33a87228c (atomic.rs:2353)
        core::sync::atomic::AtomicBool::load::h98755e393c876abe (atomic.rs:378)
        std::sys_common::poison::Flag::get::hf277343eec2966e7 (poison.rs:44)
        std::sync::condvar::Condvar::wait::h14c20325128edf7e (condvar.rs:189)
        rayon_core::latch::LockLatch::wait_and_reset::h1c8244bf740f09b9 (latch.rs:240)
        rayon_core::registry::Registry::in_worker_cold::_$u7b$$u7b$closure$u7d$$u7d$::hc01231cc1f5776b3 (registry.rs:475)
        std::thread::local::LocalKey$LT$T$GT$::try_with::hcb9dc379c39268fa (local.rs:272)
        std::thread::local::LocalKey$LT$T$GT$::with::h340944f8b882cf1f (local.rs:248)
        rayon_core::registry::Registry::in_worker_cold::hd65bc2a269d982ed (registry.rs:458)
        rayon_core::registry::in_worker::ha625d863b1ab5202 (registry.rs:877)
        rayon::iter::plumbing::bridge_producer_consumer::helper::h161e56cd8915cee0 (mod.rs:436)
        _$LT$$LT$rayon..iter..skip..Skip$LT$I$GT$$u20$as$u20$rayon..iter..IndexedParallelIterator$GT$..with_producer..Callback$LT$CB$GT$$u20$as$u20$rayon..iter..plumbing..ProducerCallback$LT$T$GT$$GT$::callback::hbff8b682fd113b73 (skip.rs:85)
        _$LT$$LT$rayon..iter..enumerate..Enumerate$LT$I$GT$$u20$as$u20$rayon..iter..IndexedParallelIterator$GT$..with_producer..Callback$LT$CB$GT$$u20$as$u20$rayon..iter..plumbing..ProducerCallback$LT$I$GT$$GT$::callback::h12880f40ae46697b (enumerate.rs:79)
        _$LT$alloc..raw_vec..RawVec$LT$T$C$A$GT$$u20$as$u20$core..ops..drop..Drop$GT$::drop::h3a55feac6c8e7771 (raw_vec.rs:498)
        core::ptr::drop_in_place$LT$alloc..raw_vec..RawVec$LT$lock_api..rwlock..RwLock$LT$parking_lot..raw_rwlock..RawRwLock$C$$RF$mut$u20$$u5b$u32$u5d$$GT$$GT$$GT$::hc1e4faf2b4194c14 (mod.rs:179)
        core::ptr::drop_in_place$LT$alloc..vec..Vec$LT$lock_api..rwlock..RwLock$LT$parking_lot..raw_rwlock..RawRwLock$C$$RF$mut$u20$$u5b$u32$u5d$$GT$$GT$$GT$::hb58aa88a82306982 (mod.rs:179)
        granne::index::GranneBuilder$LT$Elements$GT$::index_elements::h00507be69e0b3db2 (mod.rs:783)
        granne::index::GranneBuilder$LT$Elements$GT$::index_elements_in_last_layer::h0c3bc587b9a5cb50 (mod.rs:693)
        _$LT$granne..index..GranneBuilder$LT$Elements$GT$$u20$as$u20$granne..index..Builder$GT$::build_partial::hd77479376bbc9da5 (mod.rs:392)
        granne::GranneBuilder::build::ha4747e7418026a87 (lib.rs)
        granne::GranneBuilder::create_instance::init::wrap_instance_method::_$u7b$$u7b$closure$u7d$$u7d$::h5afe2b0665ab803c (members.rs:99)
        cpython::function::handle_callback::_$u7b$$u7b$closure$u7d$$u7d$::h403681d837d8438a (function.rs:218)
        std::panicking::try::do_call::h62939ca7a79bd0c1 (panicking.rs:379)
        std::panicking::try::h38c9f96318d0de5c (panicking.rs:343)
        std::panic::catch_unwind::h814cfa00d891a4c7 (panic.rs:431)
        cpython::function::handle_callback::hc27b96a79fdcc7de (function.rs:215)
        granne::GranneBuilder::create_instance::init::wrap_instance_method::hcadb94cd6edba93c (members.rs:103)
        ...
        <..... HIDDEN ........>
        ...
        _process_worker (concurrent/futures/process.py:239)
        run (multiprocessing/process.py:108)
        _bootstrap (multiprocessing/process.py:315)
        _launch (multiprocessing/popen_fork.py:75)
        __init__ (multiprocessing/popen_fork.py:19)
        _Popen (multiprocessing/context.py:277)
        start (multiprocessing/process.py:121)
        _adjust_process_count (concurrent/futures/process.py:608)
        _start_queue_management_thread (concurrent/futures/process.py:584)
        submit (concurrent/futures/process.py:645)
        ...
        <..... HIDDEN ........>
        ...
        call_fixture_func (_pytest/fixtures.py:791)
        pytest_fixture_setup (_pytest/fixtures.py:936)
        _multicall (pluggy/callers.py:187)
        <lambda> (pluggy/manager.py:84)
        _hookexec (pluggy/manager.py:93)
        __call__ (pluggy/hooks.py:286)
        execute (_pytest/fixtures.py:894)
        _compute_fixture_value (_pytest/fixtures.py:587)
        _get_active_fixturedef (_pytest/fixtures.py:502)
        getfixturevalue (_pytest/fixtures.py:479)
        _fillfixtures (_pytest/fixtures.py:469)
        fillfixtures (_pytest/fixtures.py:296)
        setup (_pytest/python.py:1468)
        prepare (_pytest/runner.py:362)
        pytest_runtest_setup (_pytest/runner.py:116)
        _multicall (pluggy/callers.py:187)
        <lambda> (pluggy/manager.py:84)
        _hookexec (pluggy/manager.py:93)
        __call__ (pluggy/hooks.py:286)
        <lambda> (_pytest/runner.py:198)
        from_call (_pytest/runner.py:226)
        call_runtest_hook (_pytest/runner.py:197)
        call_and_report (_pytest/runner.py:173)
        runtestprotocol (_pytest/runner.py:87)
        pytest_runtest_protocol (_pytest/runner.py:78)
        _multicall (pluggy/callers.py:187)
        <lambda> (pluggy/manager.py:84)
        _hookexec (pluggy/manager.py:93)
        __call__ (pluggy/hooks.py:286)
        pytest_runtestloop (_pytest/main.py:271)
        _multicall (pluggy/callers.py:187)
        <lambda> (pluggy/manager.py:84)
        _hookexec (pluggy/manager.py:93)
        __call__ (pluggy/hooks.py:286)
        _main (_pytest/main.py:250)
        wrap_session (_pytest/main.py:206)
        pytest_cmdline_main (_pytest/main.py:243)
        _multicall (pluggy/callers.py:187)
        <lambda> (pluggy/manager.py:84)
        _hookexec (pluggy/manager.py:93)
        __call__ (pluggy/hooks.py:286)
        main (_pytest/config/__init__.py:82)
        <module> (pytest:8)
    

    Deadlock related to https://github.com/granne/granne/blob/fe2fe5aca4be879be8cbaf4fc34a5abf6ed2593d/src/index/mod.rs#L774 par_iter call (not itself call, but rayon usage) and most probably related to https://github.com/rayon-rs/rayon/issues/592.

    After I set default = ["singlethreaded"] in https://github.com/granne/granne/blob/master/Cargo.toml#L26, deadlock goes away

    Unfortunately, I can't provide fully reproducible code sample for that, but will be glad to answer to any question.

    opened by menshikh-iv 4
  • Failed to compile: lifetime mismatch

    Failed to compile: lifetime mismatch

    Hi folks, seeing the below error when I add granne = "0.5.0" to my Cargo.toml. No code, just a failure to install the package. Settings:

    Brads-MacBook-Pro:thistle bradwindsor$ rustup show
    Default host: x86_64-apple-darwin
    rustup home:  /Users/bradwindsor/.rustup
    
    installed toolchains
    --------------------
    
    stable-x86_64-apple-darwin (default)
    nightly-x86_64-apple-darwin
    
    active toolchain
    ----------------
    
    stable-x86_64-apple-darwin (default)
    rustc 1.51.0 (2fd73fabe 2021-03-23)
    

    Error:

    error[E0308]: mismatched types
      --> /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/dense_vector.rs:86:17
       |
    86 |                 Self(self.0.into_owned())
       |                 ^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
       | 
      ::: /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/angular.rs:53:1
       |
    53 | dense_vector!(f32);
       | ------------------- in this macro invocation
       |
       = note: expected struct `angular::Vectors<'static>`
                  found struct `angular::Vectors<'a>`
    note: the lifetime `'a` as defined on the impl at 40:14...
      --> /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/dense_vector.rs:40:14
       |
    40 |         impl<'a> Vectors<'a> {
       |              ^^
       | 
      ::: /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/angular.rs:53:1
       |
    53 | dense_vector!(f32);
       | ------------------- in this macro invocation
       = note: ...does not necessarily outlive the static lifetime
       = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)
    
    error[E0308]: mismatched types
      --> /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/dense_vector.rs:86:17
       |
    86 |                 Self(self.0.into_owned())
       |                 ^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
       | 
      ::: /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/angular_int.rs:17:1
       |
    17 | dense_vector!(i8);
       | ------------------ in this macro invocation
       |
       = note: expected struct `angular_int::Vectors<'static>`
                  found struct `angular_int::Vectors<'a>`
    note: the lifetime `'a` as defined on the impl at 40:14...
      --> /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/dense_vector.rs:40:14
       |
    40 |         impl<'a> Vectors<'a> {
       |              ^^
       | 
      ::: /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/angular_int.rs:17:1
       |
    17 | dense_vector!(i8);
       | ------------------ in this macro invocation
       = note: ...does not necessarily outlive the static lifetime
       = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)
    
    error: aborting due to 2 previous errors
    
    For more information about this error, try `rustc --explain E0308`.
    error: could not compile `granne`
    
    
    opened by bwindsor22 0
  • suggest a paper use multi store ,  a good trade off between DRAM,billions capacity and lattency

    suggest a paper use multi store , a good trade off between DRAM,billions capacity and lattency

    Paper 1:GRIP Paper 2:Zoom

    The recently published paper GRIP:Multi-Store capacity-optimized high-performace nearest neighbor search for vector search engine.

    opened by hudengjunai 0
  • Rust panic on build

    Rust panic on build

    When going to build an index I experienced the following:

    thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
      left: `4294967295`,
     right: `1`', /rustc/38114ff16e7856f98b2b4be7ab4cd29b38bed59a/src/libstd/macros.rs:16:9
    note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
    Traceback (most recent call last):
      File "xxx", line 292, in <module>
        builder.build()
    SystemError: Rust panic
    

    Unfortunately this doesn't seem to be happening reproducibly. @jacktasia

    opened by os-gabe 2
Releases(v0.5.2)
Owner
null
🚀 efficient approximate nearest neighbor search algorithm collections library written in Rust 🦀 .

?? efficient approximate nearest neighbor search algorithm collections library written in Rust ?? .

Hora-Search 2.3k Jan 3, 2023
Nearest neighbor search algorithms including a ball tree and a vantage point tree.

petal-neighbors Nearest neighbor search algorithms including a ball tree and a vantage point tree. Examples The following example shows how to find tw

Petabi 6 Oct 19, 2022
Hamming Weight Tree from the paper Online Nearest Neighbor Search in Hamming Space

hwt Hamming Weight Tree from the paper Online Nearest Neighbor Search in Hamming Space To understand how the data structure works, please see the docs

Rust Computer Vision 7 Oct 9, 2021
Rust-port of spotify/annoy as a wrapper for Approximate Nearest Neighbors in C++/Python optimized for memory usage.

Rust-port of spotify/annoy as a wrapper for Approximate Nearest Neighbors in C++/Python optimized for memory usage.

Arthur·Thomas 13 Mar 10, 2022
Rust-port of spotify/annoy as a wrapper for Approximate Nearest Neighbors in C++/Python optimized for memory usage.

Fareast This library is a rust port of spotify/annoy , currently only index serving is supported. It also provides FFI bindings for jvm, dotnet and da

Arthur·Thomas 13 Mar 10, 2022
A neural network model that can approximate any non-linear function by using the random search algorithm for the optimization of the loss function.

random_search A neural network model that can approximate any non-linear function by using the random search algorithm for the optimization of the los

ph04 2 Apr 1, 2022
Rust implementation of multi-index hashing for neighbor searches on binary codes in the Hamming space

mih-rs Rust implementation of multi-index hashing (MIH) for neighbor searches on binary codes in the Hamming space, described in the paper Norouzi, Pu

Shunsuke Kanda 8 Sep 23, 2022
C library for finding nearest (most similar) element in a set

VP-tree nearest neighbor search A relatively simple and readable Rust implementation of Vantage Point tree search algorithm. The VP tree algorithm doe

Kornel 28 Aug 20, 2022
A simple url checker for finding fraud url(s) or nearest url

urlchecker A simple url checker for finding fraud url(s) or nearest url while being fast (threading) Eg:- use std::collections::HashMap; use urlchecke

Subconscious Compute 2 Aug 7, 2022
Program implementing the approximate version of DBSCAN introduced by Gan and Tao

appr_dbscan_rust Rust implementation of the approximate version of DBSCAN introduced by Gan and Tao in this paper Notice An upated version of this lib

Ivano Donadi 1 May 18, 2021
An approximate K-NN written in Rust.

small_knn This library is an approximate K-nearest neighbor search based on Hierarchical Navigable Small World (https://arxiv.org/pdf/1603.09320.pdf).

null 2 Nov 22, 2022
Label Propagation Algorithm by Rust. Label propagation (LP) is graph-based semi-supervised learning (SSL). LGC and CAMLP have been implemented.

label-propagation-rs Label Propagation Algorithm by Rust. Label propagation (LP) is graph-based semi-supervised learning (SSL). A simple LGC and a mor

vaaaaanquish 4 Sep 15, 2021
A suite of benchmarks to test e-graph extraction algorithms

Extraction Gym A suite of benchmarks to test e-graph extraction algorithms. Add your algorithm in src/extract and then add a line in src/main.rs. To r

null 7 Jul 1, 2023
Qdrant - vector similarity search engine with extended filtering support

Vector Similarity Search Engine with extended filtering support Qdrant (read: quadrant ) is a vector similarity search engine. It provides a productio

qdrant 3.5k Dec 30, 2022
Machine learning framework for building object trackers and similarity search engines

Similari Similari is a framework that helps build sophisticated tracking systems. The most frequently met operations that can be efficiently implement

In-Sight 71 Dec 28, 2022
Rust based Cross-GPU Machine Learning

HAL : Hyper Adaptive Learning Rust based Cross-GPU Machine Learning. Why Rust? This project is for those that miss strongly typed compiled languages.

Jason Ramapuram 83 Dec 20, 2022
Rust crate to create Anki decks. Based on the python library genanki

genanki-rs: A Rust Crate for Generating Anki Decks With genanki-rs you can easily generate decks for the popular open source flashcard platform Anki.

Yannick Funk 63 Dec 23, 2022
Narwhal and Tusk A DAG-based Mempool and Efficient BFT Consensus.

This repo contains a prototype of Narwhal and Tusk. It supplements the paper Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus.

Facebook Research 134 Dec 8, 2022
A Rust🦀 implementation of CRAFTML, an Efficient Clustering-based Random Forest for Extreme Multi-label Learning

craftml-rs A Rust implementation of CRAFTML, an Efficient Clustering-based Random Forest for Extreme Multi-label Learning (Siblini et al., 2018). Perf

Tom Dong 15 Nov 6, 2022