1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236
//! # lsh-rs (Locality Sensitive Hashing) //! //! Locality sensitive hashing can help retrieving Approximate Nearest Neighbors in sub-linear time. //! //! For more information on the subject see: //! * [Introduction on LSH](http://people.csail.mit.edu/gregory/annbook/introduction.pdf) //! * [Section 2. describes the hash families used in this crate](https://arxiv.org/pdf/1411.3787.pdf) //! * [LSH and neural networks](https://www.ritchievink.com/blog/2020/04/07/sparse-neural-networks-and-hash-tables-with-locality-sensitive-hashing/) //! //! ### //! //! ## Implementations //! //! * **Base LSH** //! - Signed Random Projections *(Cosine similarity)* //! - L2 distance //! - MIPS *(Dot products/ Maximum Inner Product Search)* //! - MinHash *(Jaccard Similarity)* //! * **Multi Probe LSH** //! - **Step wise probing** //! - SRP (only bit shifts) //! - **Query directed probing** //! - L2 //! - MIPS //! * Generic numeric types //! //! ## Features //! * "blas" //! * "sqlite" //! //! ## Getting started //! //! ```rust //! use lsh_rs::prelude::*; //! // 2 rows w/ dimension 3. //! let p = &[vec![1., 1.5, 2.], //! vec![2., 1.1, -0.3]]; //! //! // Do one time expensive preprocessing. //! let n_projections = 9; //! let n_hash_tables = 30; //! let dim = 10; //! let dim = 3; //! let mut lsh = LshMem::new(n_projections, n_hash_tables, dim) //! .srp() //! .unwrap(); //! lsh.store_vecs(p); //! //! // Query in sublinear time. //! let query = &[1.1, 1.2, 1.2]; //! lsh.query_bucket(query); //! ``` //! //! ## Signed Random Projections //! LSH for maximum cosine similarity search. //! ```rust //! # use lsh_rs::prelude::*; //! # let n_projections = 9; //! # let n_hash_tables = 30; //! # let dim = 10; //! let mut lsh = LshMem::<_, f32>::new(n_projections, n_hash_tables, dim) //! .srp() //! .unwrap(); //! ``` //! //! ## L2 //! LSH for minimal L2 distance search. //! //! ``` //! // hyper parameter r in https://arxiv.org/pdf/1411.3787.pdf (eq. 8) //! # use lsh_rs::prelude::*; //! # let bucket_width = 2.2; //! # let n_projections = 9; //! # let n_hash_tables = 10; //! # let dim = 10; //! let mut lsh = LshMem::<_, f32>::new(n_projections, n_hash_tables, dim) //! .l2(bucket_width) //! .unwrap(); //! ``` //! //! ## Jaccard Index //! LSH for the Jaccard Index //! ```rust //! # use lsh_rs::prelude::*; //! # let n_projections = 14; //! // length of the shingles vector //! let dim = 2500; //! # let n_hash_tables = 10; //! let mut lsh = LshSqlMem::<_, u16>::new(n_projections, n_hash_tables, dim) //! .minhash() //! .unwrap(); //! ``` //! //! ## Maximum Inner Product (MIPS) //! LSH for maximum inner product search. //! ```rust //! # use lsh_rs::prelude::*; //! let bucket_width = 2.2; //! // l2(x) < U < 1.0 //! let U = 0.83; //! let r = 4.; //! // number of concatenations //! let m = 3; //! let n_projections = 15; //! let n_hash_tables = 10; //! let dim = 10; //! let mut lsh = LshMem::<_, f32>::new(n_projections, n_hash_tables, dim) //! .mips(r, U, m) //! .unwrap(); //! ``` //! //! ## Seed //! Random projections are used to generate the hash functions. The default seeding of randomness //! is taken from the system. If you want to have reproducable outcomes, you can set a manual seed. //! //! ```rust //! # use lsh_rs::prelude::*; //! # let n_projections = 9; //! # let n_hash_tables = 10; //! # let dim = 10; //! let mut lsh = LshMem::<_, f32>::new(n_projections, n_hash_tables, dim) //! .seed(12) //! .srp() //! .unwrap(); //! ``` //! //! ## Unique indexes //! Instead of storing data points as vectors. Storing `L` copies of the data points (one in every //! hash table). You can choose to only store unique indexes of the data points. The index ids are //! assigned in chronological order. This will drastically decrease the required memory. //! ```rust //! # use lsh_rs::prelude::*; //! # let n_projections = 9; //! # let n_hash_tables = 10; //! # let dim = 10; //! let mut lsh = LshMem::<_, f32>::new(n_projections, n_hash_tables, dim) //! .only_index() //! .srp() //! .unwrap(); //! ``` //! //! ## Builder pattern methods //! The following methods can be used to change internal state during object initialization: //! * [only_index](struct.LSH.html#method.only_index) //! * [seed](struct.LSH.html#method.seed) //! * [set_database_file](struct.LSH.html#method.set_database_file) //! * [multi_probe](struct.LSH.html#method.multi_probe) //! * [increase_storage](struct.LSH.html#method.increase_storage) //! * [fit (only for MIPS)](struct.MIPS.html#method.fit) //! //! ## Backends //! The [LSH struct](struct.LSH.html) is exposed with multiple backends that store the hashes. //! * in memory (fastest / can save state with serialization) [LshMem](type.LshMem.html) //! * SQLite (slower due to disk io, but automatic state preservation between sessions) [LshSql](type.LshSql.html) //! * in memory SQLite (can backup to SQLite when processing is done) [LshSqlMem](type.LshSqlMem.html) //! //! ## Hash primitives //! The hashers in this crate will produces hashes of type `Vec<T>`. Where `T` should be one of `i8`, //! `i16`, `i32` or `i64`. This concrete primitive value can be set by choosing on of the utillity types //! in the following sub-modules: //! * [hi8](prelude/hi8/index.html) //! * [hi16](prelude/hi16/index.html) //! * [hi32](prelude/hi32/index.html) //! * [hi64](prelude/hi64/index.html) //! //! Using smaller primitives for the hash values, will result in less space requirements and greater //! performance. However this may lead to panics if the hash value doesn't fit the chosen primitive //! due to buffer overflow. //! //! *Note: the hash primitive cannot be set for every Hash family that has implemented //! [VecHash](trait.VecHash.html). For instance, [SignRandomProjections](struct.SignRandomProjections.html) //! will allways use `i8` as hash primitive.* //! //! ```rust //! # use lsh_rs::prelude::*; //! # let n_projections = 9; //! # let n_hash_tables = 10; //! # let dim = 10; //! // use i8 hash values: //! let lsh_i8 = hi8::LshMem::<_, u8>::new(n_projections, n_hash_tables, dim) //! .minhash() //! .unwrap(); //! // use i64 hash values: //! let lhs_i8 = hi64::LshMem::<_, u8>::new(n_projections, n_hash_tables, dim) //! .minhash() //! .unwrap(); //! ``` //! //! ## BLAS support //! Utilizing [BLAS](https://en.wikipedia.org/wiki/Basic_Linear_Algebra_Subprograms) will heavily increase //! performance. To make use of BLAS, install `lsh-rs` with `"blas"` feature and reinstall `ndarray` with `"blas"` support. //! <br> //! <br> //! **Cargo.toml:** //! ```toml //! lsh-rs = {version ="x.x"}, features=["blas"]} //! ndarray = {version = "0.13", features=["blas"]} //! # Or any other blas backend. //! blas-src = { version = "0.6", defeault-features = false, features = ["openblas"]} //! ``` //! //! ## Need your own hashers? //! The LSH struct can easily be extended with your own hashers. Your own hasher structs need //! to implement [VecHash<N, K>](trait.VecHash.html). `N` and `K` are generic types of the input //! and output numbers respectively. //! //! ## Need you own backend? //! If you need another backend, you can extend you backend with the [HashTables<N, K>](trait.HashTables.html) trait. #![allow(dead_code, non_snake_case)] #[cfg(feature = "blas")] extern crate blas_src; extern crate ndarray; mod hash; mod lsh { pub mod lsh; mod test; } pub mod dist; mod multi_probe; mod table { pub mod general; pub mod mem; pub mod sqlite; pub mod sqlite_mem; } mod constants; mod error; mod utils; pub use hash::VecHash; pub use multi_probe::{QueryDirectedProbe, StepWiseProbe}; pub use table::{general::HashTables, mem::MemoryTable}; #[cfg(feature = "sqlite")] pub use table::{sqlite::SqlTable, sqlite_mem::SqlTableMem}; pub mod data; pub mod prelude; pub mod stats;