pub struct TreeOptions {
pub num_leaves: u32,
pub num_leaves_to_search: u32,
pub training_sample_size: u64,
pub min_partition_size: u32,
pub training_iterations: u32,
pub spherical: bool,
pub quantize_centroids: bool,
pub random_init: bool,
pub incremental_threshold: Option<IncrementalThreshold>,
pub avq: Option<f64>,
pub soar_lambda: Option<f64>,
pub overretrieve_factor: Option<f64>,
}Expand description
Python: ScannBuilder.tree(). Defaults match Python’s.
Fields§
§num_leaves: u32§num_leaves_to_search: u32§training_sample_size: u64§min_partition_size: u32§training_iterations: u32§spherical: bool§quantize_centroids: bool§random_init: boolRandom center initialization (Python’s default). Upstream’s random
initialization depends on hash-table iteration order, so training
isn’t reproducible run to run; false (k-means++) is.
incremental_threshold: Option<IncrementalThreshold>§avq: Option<f64>Anisotropic vector quantization of the centers (dot product only).
soar_lambda: Option<f64>SOAR spilling (dot product only).
overretrieve_factor: Option<f64>Implementations§
Source§impl TreeOptions
impl TreeOptions
Sourcepub fn new(num_leaves: u32, num_leaves_to_search: u32) -> Self
pub fn new(num_leaves: u32, num_leaves_to_search: u32) -> Self
Examples found in repository?
docs/tutorial/code/rust/glove.rs (line 110)
98fn main() {
99 let dir = std::env::args().nth(1).expect("usage: tutorial_glove <data dir>");
100 let dir = Path::new(&dir);
101 let train = Npy::load(&dir.join("glove_train.npy"));
102 let test = Npy::load(&dir.join("glove_test.npy"));
103 let truth = Npy::load(&dir.join("glove_neighbors.npy"));
104 println!("dataset {} x {}, {} queries", train.rows, train.cols, test.rows);
105 let (dataset, queries, truth_ids) = (train.f32s(), test.f32s(), truth.u32s());
106
107 // The part 3 configuration.
108 let start = Instant::now();
109 let mut built = ConfigBuilder::new(10, DistanceMeasure::DotProduct, train.cols)
110 .tree(TreeOptions::new(2000, 100).training_sample_size(250_000))
111 .score_ah(AhOptions::new(2).anisotropic_quantization_threshold(0.2))
112 .reorder(ReorderOptions::new(100))
113 .build_index(&dataset)
114 .unwrap();
115 println!("built in {:.1} s", start.elapsed().as_secs_f64());
116 evaluate("built in Rust", &mut built, &queries, &truth_ids, truth.cols);
117
118 // The index part7_export.py saved from Python.
119 let start = Instant::now();
120 let mut loaded = ScannIndex::load(dir.join("glove-index")).unwrap();
121 println!("loaded in {:.1} s", start.elapsed().as_secs_f64());
122 evaluate("built in Python, loaded", &mut loaded, &queries, &truth_ids, truth.cols);
123
124 // Concurrent single-query search() from many threads, sharing one index:
125 // ScannIndex is Send + Sync, and there is no interpreter lock.
126 let dim = loaded.dimensionality();
127 let index = &loaded;
128 for threads in [1, 8, 32, 64] {
129 let start = Instant::now();
130 std::thread::scope(|s| {
131 for t in 0..threads {
132 let queries = &queries;
133 s.spawn(move || {
134 // Thread t takes every threads-th query.
135 for q in queries.chunks(dim).skip(t).step_by(threads) {
136 index.search(q, SearchOptions::default()).unwrap();
137 }
138 });
139 }
140 });
141 let qps = (queries.len() / dim) as f64 / start.elapsed().as_secs_f64();
142 println!("concurrent search() from {threads:2} threads: {qps:8.0} QPS");
143 }
144}More examples
examples/rust/quickstart.rs (line 62)
52fn main() -> Result<(), Box<dyn std::error::Error>> {
53 let dataset = make_dataset(N, 1);
54 let queries = make_dataset(5, 2);
55
56 // The same options as the Python
57 // scann.scann_ops_pybind.builder(db, 5, "dot_product")
58 // .tree(num_leaves=200, num_leaves_to_search=20, random_init=False)
59 // .score_ah(2, anisotropic_quantization_threshold=0.2)
60 // .reorder(100).build()
61 let builder = ConfigBuilder::new(5, DistanceMeasure::DotProduct, DIM)
62 .tree(TreeOptions::new(200, 20).random_init(false)) // k-means++: reproducible
63 .score_ah(AhOptions::new(2).anisotropic_quantization_threshold(0.2))
64 .reorder(ReorderOptions::new(100));
65 println!("config:\n{}", builder.build(N as u64)?);
66 let mut index = builder.build_index(&dataset)?;
67 println!("built {index:?}");
68
69 // One query at a time; SearchOptions overrides the config per query.
70 for (q, query) in queries.chunks(DIM).enumerate() {
71 let nn = index.search(query, SearchOptions::default())?;
72 println!("query {q}: {:?} {:?}", nn.indices, nn.distances);
73 }
74 let wide = index.search(&queries[..DIM], SearchOptions::k(10).leaves_to_search(50))?;
75 println!("query 0, k=10 over 50 leaves: {:?}", wide.indices);
76
77 // A batch, and the same batch split across the index's thread pool.
78 let batched = index.search_batched(&queries, SearchOptions::default())?;
79 index.set_num_threads(4)?;
80 let parallel = index.search_batched_parallel(&queries, SearchOptions::default(), 2)?;
81 assert_eq!(batched[0].indices, parallel[0].indices);
82
83 // ScannIndex is Send + Sync: search it from several threads at once.
84 let index_ref = &index;
85 let from_threads: Vec<Vec<u32>> = std::thread::scope(|s| {
86 let handles: Vec<_> = queries
87 .chunks(DIM)
88 .map(|q| s.spawn(move || index_ref.search(q, SearchOptions::k(1)).unwrap().indices))
89 .collect();
90 handles.into_iter().map(|h| h.join().unwrap()).collect()
91 });
92 println!("top-1 per query, searched concurrently: {from_threads:?}");
93
94 // Mutation: add a point (immediately searchable), then delete it.
95 let added = index.add(&queries[..DIM])?;
96 let nn = index.search(&queries[..DIM], SearchOptions::k(1))?;
97 println!("added point {:?}; query 0's nearest neighbour is now {:?}", added, nn.indices);
98 index.delete(&added)?;
99 println!("deleted it again: {} points", index.len());
100
101 // Save and reload. The directory is also loadable from Python with
102 // scann.scann_ops_pybind.load_searcher(dir).
103 let dir = std::env::temp_dir().join("scann-core-rust-quickstart");
104 std::fs::create_dir_all(&dir)?;
105 index.serialize(&dir, true)?;
106 let reloaded = ScannIndex::load(&dir)?;
107 println!("reloaded {reloaded:?} from {}", dir.display());
108 std::fs::remove_dir_all(&dir)?;
109 Ok(())
110}examples/rust/updating.rs (line 93)
87fn main() -> Result<(), Box<dyn std::error::Error>> {
88 let initial = make_data(3000, 1);
89 // The application's ids, one per row: row i of the index is docids[i].
90 let mut docids: Vec<String> = (0..3000).map(|i| format!("doc-{i}")).collect();
91
92 let builder = ConfigBuilder::new(10, DistanceMeasure::DotProduct, DIM)
93 .tree(TreeOptions::new(LEAVES, 10).random_init(false))
94 .score_ah(AhOptions::new(2).anisotropic_quantization_threshold(0.2))
95 .reorder(ReorderOptions::new(100));
96 let mut index = builder.build_index(&initial)?;
97 print_health("built:", &index)?;
98
99 // --- Insert ----------------------------------------------------------
100 // upsert: `None` adds a row, `Some(i)` replaces row i. The result is
101 // each row's index; new rows are appended. batch_size > 1 assigns the
102 // batch to leaves on the index's thread pool. An upsert (or delete) can
103 // trigger incremental maintenance and, when that asks for it, a full
104 // retrain, as in Python.
105 let added = make_data(1000, 2);
106 let added_docids: Vec<String> = (0..1000).map(|i| format!("new-{i}")).collect();
107 let new_rows = index.upsert(&[None; 1000], &added, 256)?;
108 assert_eq!(new_rows, (3000..4000).collect::<Vec<u32>>());
109 docids.extend(added_docids.iter().cloned());
110 assert_eq!(nearest(&index, &docids, &added), added_docids);
111 print_health("after inserting 1000:", &index)?;
112
113 // --- Update ----------------------------------------------------------
114 // Replace row 0's vector; it keeps its index (and so its docid).
115 let moved = make_data(1, 3);
116 index.upsert(&[Some(0)], &moved, 1)?;
117 assert_eq!(nearest(&index, &docids, &moved), ["doc-0"]);
118 assert_ne!(nearest(&index, &docids, &initial[..DIM]), ["doc-0"]);
119 println!("updated doc-0: found at its new vector, not at its old one");
120
121 // An index listed twice in one upsert is rejected before anything
122 // changes, like a repeated docid in Python.
123 let err = index.upsert(&[Some(1), Some(1)], &make_data(2, 4), 1).unwrap_err();
124 assert!(matches!(err, ScannError::InvalidArgument(_)));
125 println!("repeated index rejected: {err}");
126 assert_eq!(index.len(), 4000);
127
128 // --- Delete ----------------------------------------------------------
129 // delete takes indices as they are before the call and returns the
130 // (old index, new index) of every row that moved into a freed slot.
131 // Apply the moves to the id table, then drop its tail.
132 let doomed: Vec<u32> = (1..=500).collect();
133 let moves = index.delete(&doomed)?;
134 for &(from, to) in &moves {
135 docids[to as usize] = docids[from as usize].clone();
136 }
137 docids.truncate(index.len());
138 assert_eq!(index.len(), 3500);
139 println!("deleted {} points; {} others moved to new indices", doomed.len(), moves.len());
140 // The added points still find themselves, under their own docids.
141 assert_eq!(nearest(&index, &docids, &added), added_docids);
142 print_health("after deleting 500:", &index)?;
143
144 // --- Rebalance -------------------------------------------------------
145 // Retrains the tree and AH codebooks on the current data (a full
146 // retrain, as slow as a build) and recomputes the health stats. Indices
147 // don't change.
148 index.rebalance(None)?;
149 print_health("after rebalance:", &index)?;
150 assert_eq!(nearest(&index, &docids, &moved), ["doc-0"]);
151
152 // --- Save over an existing index, reload -----------------------------
153 // serialize replaces an index already in the directory: files are
154 // staged, then renamed into place with the manifest last, so an
155 // interrupted save leaves the old index, the new one, or a directory
156 // that `load` rejects; never a mix. `true`: relative paths, movable.
157 let dir = std::env::temp_dir().join(format!("scann-core-rust-updating-{}", std::process::id()));
158 std::fs::create_dir_all(&dir)?;
159 index.serialize(&dir, true)?;
160 index.add(&make_data(1, 5))?;
161 docids.push("late-arrival".to_string());
162 index.serialize(&dir, true)?;
163
164 let reloaded = ScannIndex::load(&dir)?;
165 assert_eq!(reloaded.len(), docids.len());
166 let queries = make_data(50, 6);
167 let a = index.search_batched(&queries, SearchOptions::default())?;
168 let b = reloaded.search_batched(&queries, SearchOptions::default())?;
169 assert_eq!(a, b);
170 println!("re-saved and reloaded {} points: identical results", reloaded.len());
171 // The ids are the application's to store (Python's scann_docids.pkl is
172 // written only by the Python wrapper).
173 std::fs::remove_dir_all(&dir)?;
174 Ok(())
175}Sourcepub fn training_sample_size(self, n: u64) -> Self
pub fn training_sample_size(self, n: u64) -> Self
Examples found in repository?
docs/tutorial/code/rust/glove.rs (line 110)
98fn main() {
99 let dir = std::env::args().nth(1).expect("usage: tutorial_glove <data dir>");
100 let dir = Path::new(&dir);
101 let train = Npy::load(&dir.join("glove_train.npy"));
102 let test = Npy::load(&dir.join("glove_test.npy"));
103 let truth = Npy::load(&dir.join("glove_neighbors.npy"));
104 println!("dataset {} x {}, {} queries", train.rows, train.cols, test.rows);
105 let (dataset, queries, truth_ids) = (train.f32s(), test.f32s(), truth.u32s());
106
107 // The part 3 configuration.
108 let start = Instant::now();
109 let mut built = ConfigBuilder::new(10, DistanceMeasure::DotProduct, train.cols)
110 .tree(TreeOptions::new(2000, 100).training_sample_size(250_000))
111 .score_ah(AhOptions::new(2).anisotropic_quantization_threshold(0.2))
112 .reorder(ReorderOptions::new(100))
113 .build_index(&dataset)
114 .unwrap();
115 println!("built in {:.1} s", start.elapsed().as_secs_f64());
116 evaluate("built in Rust", &mut built, &queries, &truth_ids, truth.cols);
117
118 // The index part7_export.py saved from Python.
119 let start = Instant::now();
120 let mut loaded = ScannIndex::load(dir.join("glove-index")).unwrap();
121 println!("loaded in {:.1} s", start.elapsed().as_secs_f64());
122 evaluate("built in Python, loaded", &mut loaded, &queries, &truth_ids, truth.cols);
123
124 // Concurrent single-query search() from many threads, sharing one index:
125 // ScannIndex is Send + Sync, and there is no interpreter lock.
126 let dim = loaded.dimensionality();
127 let index = &loaded;
128 for threads in [1, 8, 32, 64] {
129 let start = Instant::now();
130 std::thread::scope(|s| {
131 for t in 0..threads {
132 let queries = &queries;
133 s.spawn(move || {
134 // Thread t takes every threads-th query.
135 for q in queries.chunks(dim).skip(t).step_by(threads) {
136 index.search(q, SearchOptions::default()).unwrap();
137 }
138 });
139 }
140 });
141 let qps = (queries.len() / dim) as f64 / start.elapsed().as_secs_f64();
142 println!("concurrent search() from {threads:2} threads: {qps:8.0} QPS");
143 }
144}pub fn min_partition_size(self, n: u32) -> Self
pub fn training_iterations(self, n: u32) -> Self
Sourcepub fn spherical(self, v: bool) -> Self
pub fn spherical(self, v: bool) -> Self
Spherical k-means. The index then stores unit vectors: rows are L2-normalized at build time and on upsert.
pub fn quantize_centroids(self, v: bool) -> Self
Sourcepub fn random_init(self, v: bool) -> Self
pub fn random_init(self, v: bool) -> Self
Examples found in repository?
examples/rust/quickstart.rs (line 62)
52fn main() -> Result<(), Box<dyn std::error::Error>> {
53 let dataset = make_dataset(N, 1);
54 let queries = make_dataset(5, 2);
55
56 // The same options as the Python
57 // scann.scann_ops_pybind.builder(db, 5, "dot_product")
58 // .tree(num_leaves=200, num_leaves_to_search=20, random_init=False)
59 // .score_ah(2, anisotropic_quantization_threshold=0.2)
60 // .reorder(100).build()
61 let builder = ConfigBuilder::new(5, DistanceMeasure::DotProduct, DIM)
62 .tree(TreeOptions::new(200, 20).random_init(false)) // k-means++: reproducible
63 .score_ah(AhOptions::new(2).anisotropic_quantization_threshold(0.2))
64 .reorder(ReorderOptions::new(100));
65 println!("config:\n{}", builder.build(N as u64)?);
66 let mut index = builder.build_index(&dataset)?;
67 println!("built {index:?}");
68
69 // One query at a time; SearchOptions overrides the config per query.
70 for (q, query) in queries.chunks(DIM).enumerate() {
71 let nn = index.search(query, SearchOptions::default())?;
72 println!("query {q}: {:?} {:?}", nn.indices, nn.distances);
73 }
74 let wide = index.search(&queries[..DIM], SearchOptions::k(10).leaves_to_search(50))?;
75 println!("query 0, k=10 over 50 leaves: {:?}", wide.indices);
76
77 // A batch, and the same batch split across the index's thread pool.
78 let batched = index.search_batched(&queries, SearchOptions::default())?;
79 index.set_num_threads(4)?;
80 let parallel = index.search_batched_parallel(&queries, SearchOptions::default(), 2)?;
81 assert_eq!(batched[0].indices, parallel[0].indices);
82
83 // ScannIndex is Send + Sync: search it from several threads at once.
84 let index_ref = &index;
85 let from_threads: Vec<Vec<u32>> = std::thread::scope(|s| {
86 let handles: Vec<_> = queries
87 .chunks(DIM)
88 .map(|q| s.spawn(move || index_ref.search(q, SearchOptions::k(1)).unwrap().indices))
89 .collect();
90 handles.into_iter().map(|h| h.join().unwrap()).collect()
91 });
92 println!("top-1 per query, searched concurrently: {from_threads:?}");
93
94 // Mutation: add a point (immediately searchable), then delete it.
95 let added = index.add(&queries[..DIM])?;
96 let nn = index.search(&queries[..DIM], SearchOptions::k(1))?;
97 println!("added point {:?}; query 0's nearest neighbour is now {:?}", added, nn.indices);
98 index.delete(&added)?;
99 println!("deleted it again: {} points", index.len());
100
101 // Save and reload. The directory is also loadable from Python with
102 // scann.scann_ops_pybind.load_searcher(dir).
103 let dir = std::env::temp_dir().join("scann-core-rust-quickstart");
104 std::fs::create_dir_all(&dir)?;
105 index.serialize(&dir, true)?;
106 let reloaded = ScannIndex::load(&dir)?;
107 println!("reloaded {reloaded:?} from {}", dir.display());
108 std::fs::remove_dir_all(&dir)?;
109 Ok(())
110}More examples
examples/rust/updating.rs (line 93)
87fn main() -> Result<(), Box<dyn std::error::Error>> {
88 let initial = make_data(3000, 1);
89 // The application's ids, one per row: row i of the index is docids[i].
90 let mut docids: Vec<String> = (0..3000).map(|i| format!("doc-{i}")).collect();
91
92 let builder = ConfigBuilder::new(10, DistanceMeasure::DotProduct, DIM)
93 .tree(TreeOptions::new(LEAVES, 10).random_init(false))
94 .score_ah(AhOptions::new(2).anisotropic_quantization_threshold(0.2))
95 .reorder(ReorderOptions::new(100));
96 let mut index = builder.build_index(&initial)?;
97 print_health("built:", &index)?;
98
99 // --- Insert ----------------------------------------------------------
100 // upsert: `None` adds a row, `Some(i)` replaces row i. The result is
101 // each row's index; new rows are appended. batch_size > 1 assigns the
102 // batch to leaves on the index's thread pool. An upsert (or delete) can
103 // trigger incremental maintenance and, when that asks for it, a full
104 // retrain, as in Python.
105 let added = make_data(1000, 2);
106 let added_docids: Vec<String> = (0..1000).map(|i| format!("new-{i}")).collect();
107 let new_rows = index.upsert(&[None; 1000], &added, 256)?;
108 assert_eq!(new_rows, (3000..4000).collect::<Vec<u32>>());
109 docids.extend(added_docids.iter().cloned());
110 assert_eq!(nearest(&index, &docids, &added), added_docids);
111 print_health("after inserting 1000:", &index)?;
112
113 // --- Update ----------------------------------------------------------
114 // Replace row 0's vector; it keeps its index (and so its docid).
115 let moved = make_data(1, 3);
116 index.upsert(&[Some(0)], &moved, 1)?;
117 assert_eq!(nearest(&index, &docids, &moved), ["doc-0"]);
118 assert_ne!(nearest(&index, &docids, &initial[..DIM]), ["doc-0"]);
119 println!("updated doc-0: found at its new vector, not at its old one");
120
121 // An index listed twice in one upsert is rejected before anything
122 // changes, like a repeated docid in Python.
123 let err = index.upsert(&[Some(1), Some(1)], &make_data(2, 4), 1).unwrap_err();
124 assert!(matches!(err, ScannError::InvalidArgument(_)));
125 println!("repeated index rejected: {err}");
126 assert_eq!(index.len(), 4000);
127
128 // --- Delete ----------------------------------------------------------
129 // delete takes indices as they are before the call and returns the
130 // (old index, new index) of every row that moved into a freed slot.
131 // Apply the moves to the id table, then drop its tail.
132 let doomed: Vec<u32> = (1..=500).collect();
133 let moves = index.delete(&doomed)?;
134 for &(from, to) in &moves {
135 docids[to as usize] = docids[from as usize].clone();
136 }
137 docids.truncate(index.len());
138 assert_eq!(index.len(), 3500);
139 println!("deleted {} points; {} others moved to new indices", doomed.len(), moves.len());
140 // The added points still find themselves, under their own docids.
141 assert_eq!(nearest(&index, &docids, &added), added_docids);
142 print_health("after deleting 500:", &index)?;
143
144 // --- Rebalance -------------------------------------------------------
145 // Retrains the tree and AH codebooks on the current data (a full
146 // retrain, as slow as a build) and recomputes the health stats. Indices
147 // don't change.
148 index.rebalance(None)?;
149 print_health("after rebalance:", &index)?;
150 assert_eq!(nearest(&index, &docids, &moved), ["doc-0"]);
151
152 // --- Save over an existing index, reload -----------------------------
153 // serialize replaces an index already in the directory: files are
154 // staged, then renamed into place with the manifest last, so an
155 // interrupted save leaves the old index, the new one, or a directory
156 // that `load` rejects; never a mix. `true`: relative paths, movable.
157 let dir = std::env::temp_dir().join(format!("scann-core-rust-updating-{}", std::process::id()));
158 std::fs::create_dir_all(&dir)?;
159 index.serialize(&dir, true)?;
160 index.add(&make_data(1, 5))?;
161 docids.push("late-arrival".to_string());
162 index.serialize(&dir, true)?;
163
164 let reloaded = ScannIndex::load(&dir)?;
165 assert_eq!(reloaded.len(), docids.len());
166 let queries = make_data(50, 6);
167 let a = index.search_batched(&queries, SearchOptions::default())?;
168 let b = reloaded.search_batched(&queries, SearchOptions::default())?;
169 assert_eq!(a, b);
170 println!("re-saved and reloaded {} points: identical results", reloaded.len());
171 // The ids are the application's to store (Python's scann_docids.pkl is
172 // written only by the Python wrapper).
173 std::fs::remove_dir_all(&dir)?;
174 Ok(())
175}pub fn incremental_threshold(self, t: IncrementalThreshold) -> Self
pub fn avq(self, eta: f64) -> Self
pub fn soar_lambda(self, lambda: f64) -> Self
pub fn overretrieve_factor(self, f: f64) -> Self
Trait Implementations§
Source§impl Clone for TreeOptions
impl Clone for TreeOptions
Source§impl Debug for TreeOptions
impl Debug for TreeOptions
Source§impl PartialEq for TreeOptions
impl PartialEq for TreeOptions
impl StructuralPartialEq for TreeOptions
Auto Trait Implementations§
impl Freeze for TreeOptions
impl RefUnwindSafe for TreeOptions
impl Send for TreeOptions
impl Sync for TreeOptions
impl Unpin for TreeOptions
impl UnsafeUnpin for TreeOptions
impl UnwindSafe for TreeOptions
Blanket Implementations§
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more