kdtree implementation for rust.

Related tags

Machine learning rust kd-tree
Overview

kdtree-rust Build Status Build Status

kdtree implementation for rust.

Implementation uses sliding midpoint variation of the tree. More Info here Implementation uses single Vec to store all its contents, allowing for quick access, and no memory fragmentation.

Usage

Tree can only be used with types implementing trait:

pub trait KdtreePointTrait : Copy  {
    fn dims(&self) -> &[f64];
}

Thanks to this trait you can use any dimension. Keep in mind that the tree currently only supports up to 3D #2.
Examplary implementation would be:

pub struct Point3WithId {
    dims: [f64; 3],
    pub id: i32,
}

impl KdtreePointTrait for Point3WithId {
    #[inline] // the inline on this method is important! as without it there is ~25% speed loss on the tree when cross-crate usage.
    fn dims(&self) -> &[f64] {
        return &self.dims;
    }
}

Where id is just a example of the way in which I carry the data.
With that trait implemented you are good to go to use the tree. Keep in mind that the kdtree is not a self balancing tree, It does support adding the nodes with method 'insert_node' and there is indeed a code to rebuild the tree if depths grows substantially. Basic usage can be found in the integration test, fragment copied below:

let tree = kdtree::kdtree::Kdtree::new(&mut points.clone());

//test points pushed into the tree, id should be equal.
for i in 0 .. point_count {
    let p = &points[i];

    assert_eq!(p.id, tree.nearest_search(p).id );
}

Although not recommended for the kd-tree you can use the insert_node and insert_nodes_and_rebuild functions to add nodes to the tree. insert_node does silly check to check whether the tree should be rebuilt. insert_nodes_and_rebuild Automatically rebuilds the tree.

for now the removal of the nodes is not supported.

Benchmark

cargo bench using travis :)

running 3 tests
test bench_creating_1000_000_node_tree          ... bench: 275,155,622 ns/iter (+/- 32,713,321)
test bench_adding_same_node_to_1000_tree        ... bench:          42 ns/iter (+/- 11)
test bench_creating_1000_node_tree              ... bench:     120,310 ns/iter (+/- 4,746)
test bench_single_lookup_times_for_1000_node_tree ... bench:         164 ns/iter (+/- 139)
test result: ok. 0 passed; 0 failed; 0 ignored; 4 measured

~275ms to create a 1000_000 node tree. << this bench is now disabled.
~120us to create a 1000 node tree.
160ns to query the tree.

Benchmark - comparison with CGAL.

Since raw values arent saying much I've created the benchmark comparing this implementation against CGAL. code of the benchmark is available here: https://github.com/fulara/kdtree-benchmarks

Benchmark                           Time           CPU Iterations
-----------------------------------------------------------------
Cgal_tree_buildup/10             2226 ns       2221 ns     313336
Cgal_tree_buildup/100           18357 ns      18315 ns      37968
Cgal_tree_buildup/1000         288135 ns     287345 ns       2369
Cgal_tree_buildup/9.76562k    3296740 ns    3290815 ns        211
Cgal_tree_buildup/97.6562k   42909150 ns   42813307 ns         12
Cgal_tree_buildup/976.562k  734566227 ns  733267760 ns          1
Cgal_tree_lookup/10                72 ns         72 ns    9392612
Cgal_tree_lookup/100               95 ns         95 ns    7103628
Cgal_tree_lookup/1000             174 ns        174 ns    4010773
Cgal_tree_lookup/9.76562k         268 ns        267 ns    2759487
Cgal_tree_lookup/97.6562k         881 ns        876 ns    1262454
Cgal_tree_lookup/976.562k         993 ns        991 ns     713751
Rust_tree_buildup/10              726 ns        724 ns     856791
Rust_tree_buildup/100            7103 ns       7092 ns      96132
Rust_tree_buildup/1000          84879 ns      84720 ns       7927
Rust_tree_buildup/9.76562k    1012983 ns    1010856 ns        630
Rust_tree_buildup/97.6562k   12406293 ns   12382399 ns         51
Rust_tree_buildup/976.562k  197175067 ns  196763387 ns          3
Rust_tree_lookup/10                62 ns         62 ns   11541505
Rust_tree_lookup/100              139 ns        139 ns    4058837
Rust_tree_lookup/1000             220 ns        220 ns    2890813
Rust_tree_lookup/9.76562k         307 ns        307 ns    2508133
Rust_tree_lookup/97.6562k         362 ns        362 ns    2035671
Rust_tree_lookup/976.562k         442 ns        441 ns    1636130

Rust_tree_lookup has some overhead since the libraries are being invoked from C code into Rust, and there is minor overhead of that in between, my experience indicates around 50 ns overhead.

License

The Unlicense

Comments
  • Add a within command to find all points within a search radius

    Add a within command to find all points within a search radius

    Closed #15 and split it into two commits.

    Side note, can we remove the panic on the creation of the tree and return a result, or allow empty trees to be made? Was so confused until I realized the panic came from the library.

    opened by jkelleyrtp 3
  • Add a within command to find all points within a search radius

    Add a within command to find all points within a search radius

    Addresses #7

    I called it within, though it could be called something different.

    My tests weren't terribly thorough - not sure if midpoint splitting would produce false positives on a linear distribution of points. Hopefully you can tell what's happening.

    I also cargo fmt ted everything.

    My within can take a generic distance function rather than the euclidean currently in use. I think this would be nice to implement everywhere in the crate though it would be a breaking change.

    Yours is also the fastest I've tested so far, so kudos 🎉.

    opened by jkelleyrtp 3
  • jk/directory layout fix

    jk/directory layout fix

    I wasn't happy with having to reexport kdtree from kdtree, so I moved things around and the public API is exposed via lib.

    Then, I bumped rand up a version, added a doc landing page.

    Finally, I changed the benchmarks to criterion and did some perf comparison against nanoflann. Extremely fast. 🚀

    opened by jkelleyrtp 2
  • Create some integrations tests

    Create some integrations tests

    To really test the tree some integrations tests are needed.

    1. Creates random 1000+ points in cube of XXX x XXX x XXX dimensions ( do 3d ). create tree from that. Iterate over every of the 1000 points, and do NN search each NN search should result in the the same point returned from the tree.
    2. Create random 1000+ points in cube of XXX x XXX x XXX dimensions ( do 3d ). create tree from that. For X times create a random point within the cube, and do a NN search. then do linear NN search. the results should be equivalent.
    enhancement 
    opened by fulara 1
  • Add possibility of adding the node trees on the fly.

    Add possibility of adding the node trees on the fly.

    Currently the tree only always single build up. This is how kdtree are meant to work - they should only be created once then queried.

    I dont think there is any problems with adding possibility to create the nodes on the fly. Yes, this leads to unbalanced trees, however that is up to user.

    opened by fulara 0
  • Tree only supports up to 3D.

    Tree only supports up to 3D.

    Because 'bounds' has been changed to use array of 3 elements the tree only allows up to 3d. This is good enough for my requirements. But can be a problem. The best solution would be to wait for Rust to have support in gnerics for values.

    Since I will be using only up to 3 dimension this is not an issue right now. tbf. On hold.

    enhancement 
    opened by fulara 0
Releases(v0.2.0)
Owner
Aleksander
Random programmer. Used C++/C# for past few years. Now falling in love with Rust.
Aleksander
GitHub
Instance Distance is a fast pure-Rust implementation of the Hierarchical Navigable Small Worlds paper

Fast approximate nearest neighbor searching in Rust, based on HNSW index

Instant Domain Search, Inc. 135 Dec 24, 2022
A real-time implementation of "Ray Tracing in One Weekend" using nannou and rust-gpu.

Real-time Ray Tracing with nannou & rust-gpu An attempt at a real-time implementation of "Ray Tracing in One Weekend" by Peter Shirley. This was a per

null 89 Dec 23, 2022
A neural network, and tensor dynamic automatic differentiation implementation for Rust.

Corgi A neural network, and tensor dynamic automatic differentiation implementation for Rust. BLAS The BLAS feature can be enabled, and requires CBLAS

Patrick Song 20 Nov 7, 2022
Flexible, reusable reinforcement learning (Q learning) implementation in Rust

Rurel Rurel is a flexible, reusable reinforcement learning (Q learning) implementation in Rust. Release documentation In Cargo.toml: rurel = "0.2.0"

Milan Boers 60 Dec 29, 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
Barnes-Hut t-SNE implementation written in Rust.

bhtsne Barnes-Hut implementation of t-SNE written in Rust. The algorithm is described with fine detail in this paper by Laurens van der Maaten. Instal

Francesco Iannelli 48 Dec 27, 2022
An implementation of the Pair Adjacent Violators algorithm for isotonic regression in Rust

Pair Adjacent Violators for Rust Overview An implementation of the Pair Adjacent Violators algorithm for isotonic regression. Note this algorithm is a

Ian Clarke 3 Dec 25, 2021
Generic k-means implementation written in Rust

RKM - Rust k-means A simple Rust implementation of the k-means clustering algorithm based on a C++ implementation, dkm. This implementation is generic

Nick Sarten 8 Sep 25, 2021
Rust implementation for DBSCANSD, a trajectory clustering algorithm.

DBSCANSD Rust implementation for DBSCANSD, a trajectory clustering algorithm. Brief Introduction DBSCANSD (Density-Based Spatial Clustering of Applica

Nick Gu 2 Mar 14, 2021
A naive DBSCAN implementation in Rust

DBSCAN Density-Based Spatial Clustering of Applications with Noise Wikipedia link DBSCAN is a density-based clustering algorithm: given a set of point

Alan K 2 Dec 23, 2022
A random forest implementation in Rust

randomforest A random forest implementation in Rust. Examples use randomforest::criterion::Mse; use randomforest::RandomForestRegressorOptions; use ra

Takeru Ohta 3 Nov 19, 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
Rust implementation of user-based collaborative filtering

Rucommender Recommendation system written in Rust Overview An implementation in Rust of a collaborative filtering recommendations algorithm with a use

null 0 Sep 15, 2018
This repository features a simple Kalman filter and RTS smoother (KFS) implementation in Rust by using the ndarray library.

Kalman filter and RTS smoother in Rust (ndarray) This repository features a simple Kalman filter and RTS smoother (KFS) implementation in Rust by usin

SPDEs 3 Dec 1, 2022
Python+Rust implementation of the Probabilistic Principal Component Analysis model

Probabilistic Principal Component Analysis (PPCA) model This project implements a PPCA model implemented in Rust for Python using pyO3 and maturin. In

FindHotel 11 Dec 16, 2022
TopK algorithm implementation in Rust (Filtered Space-Saving)

TopK TopK algorithm implementation in Rust. This crate currently provides the Filtered Space-Saving algorithm. Version numbers follow the semver conve

null 6 Feb 24, 2023
Rust+OpenCL+AVX2 implementation of LLaMA inference code

RLLaMA RLLaMA is a pure Rust implementation of LLaMA large language model inference.. Supported features Uses either f16 and f32 weights. LLaMA-7B, LL

Mikko Juola 344 Apr 16, 2023
A rust implementation of the csl-next model.

Vision This is a project to write the CSL-Next typescript model and supporting libraries and tools in Rust, and convert to JSON Schema from there. At

Bruce D'Arcus 4 Jun 13, 2023
Rust implementation of @Qdrant/fastembed.

FastEmbed-rs ?? Rust implementation of @Qdrant/fastembed ?? Features Supports synchronous usage. No dependency on Tokio. Uses @huggingface/tokenizers

Anush 35 Oct 30, 2023