4 releases
0.2.2 | Sep 11, 2024 |
---|---|
0.2.1 | Aug 29, 2024 |
0.2.0 | Aug 28, 2024 |
0.1.0 | Dec 25, 2023 |
#352 in Algorithms
252 downloads per month
50KB
982 lines
rindex
Rindex: dynamic spatial index for efficiently maintaining k nearest neighbors graph of multi-dimensional clustered datasets.
Usage
The following example shows how to maintain k nearest neighbors using Rindex:
use rindex::Rindex;
fn main() {
let k = 3; // maintain 3 nearest neighbors for each point
let mut rindex = Rindex::new(k);
// Insert some points
let a = rindex.insert([1.0, 1.0]);
let b = rindex.insert([2.0, 2.0]);
let c = rindex.insert([3.0, 3.0]);
let d = rindex.insert([20.0, 20.0]);
// Check k nearest neighbors of point a
let (neighbors, distances) = rindex.neighbors_of(a);
assert_eq!(neighbors, vec![a, b, c]);
// Remove point b
rindex.delete(b);
// Check k nearest neighbors of point a again
let (neighbors, distances) = rindex.neighbors_of(a);
assert_eq!(neighbors, vec![a, c, d]); // b is not in the result
}
Both insertion and deletion operations dynamically updates the k nearest neighbors for all remaining points efficiently (see the references below).
Update operations
The insertion algorithm returns an id of the newly-inserted point, store it for later usage, e.g. to delete the point:
use rindex::Rindex;
fn main() {
let mut rindex = Rindex::default();
let a = rindex.insert([1.0, 1.0]);
assert_eq!(rindex.num_points(), 1);
rindex.delete(a);
assert_eq!(rindex.num_points(), 0);
}
Nearest neighbor queries
The traditional query operations are supported in addition to the reverse nearest neighbors query:
use rindex::Rindex;
fn main() {
let k = 3;
let mut rindex = Rindex::new(k);
let a = rindex.insert([1.0, 1.0]);
let b = rindex.insert([2.0, 2.0]);
let c = rindex.insert([3.0, 3.0]);
let d = rindex.insert([20.0, 20.0]);
let query_point = [0.0, 0.0];
// Range queries: find all points within query_radius distance
let query_radius = 10.0;
let (neighbors, distances) = rindex.query(&query_point, query_radius);
assert_eq!(neighbors, vec![a, b, c]);
// Nearest neighbors: find 3 nearest neighbors of the query point
let (neighbors, distances) = rindex.query_neighbors(&query_point, 3);
assert_eq!(neighbors, vec![a, b, c]);
// Reverse nearest neighbors: find such points that sees the query point
// as one of their 3 nearest neighbors
let (neighbors, distances) = rindex.query_reverse(&[0.0, 0.0]);
assert_eq!(neighbors, vec![a]);
}
References
Rindex combines the algorithms presented in the following papers:
[1] Beckmann, N., Kriegel, H.P., Schneider, R. and Seeger, B., 1990, May. The R*-tree: An efficient and robust access method for points and rectangles. In Proceedings of the 1990 ACM SIGMOD international conference on Management of data (pp. 322-331).
[2] White, D.A. and Jain, R., 1996, February. Similarity indexing with the SS-tree. In Proceedings of the Twelfth International Conference on Data Engineering (pp. 516-523). IEEE.
[3] Yang, C. and Lin, K.I., 2001, April. An index structure for efficient reverse nearest neighbor queries. In Proceedings 17th International Conference on Data Engineering (pp. 485-492). IEEE.
License
This project is licensed under the Apache License, Version 2.0 - See the LICENSE.md file for details.
Dependencies
~335KB