13 releases (7 breaking)

0.8.2 Aug 1, 2020
0.8.1 Jun 19, 2020
0.8.0 May 25, 2020
0.7.1 Jan 16, 2020
0.1.0 Nov 22, 2018

#61 in Data structures

Download history 3642/week @ 2020-08-07 3125/week @ 2020-08-14 3307/week @ 2020-08-21 3622/week @ 2020-08-28 3967/week @ 2020-09-04 5150/week @ 2020-09-11 4716/week @ 2020-09-18 6369/week @ 2020-09-25 5168/week @ 2020-10-02 4992/week @ 2020-10-09 4949/week @ 2020-10-16 4702/week @ 2020-10-23 4963/week @ 2020-10-30 5304/week @ 2020-11-06 4702/week @ 2020-11-13 3189/week @ 2020-11-20

16,357 downloads per month
Used in 51 crates (16 directly)

MIT/Apache

145KB
3K SLoC

rstar

A flexible, n-dimensional r*-tree implementation for the rust ecosystem.

Features

  • A flexible r*-tree written in safe rust
  • Supports custom point types
  • Supports the insertion of user defined types
  • Supported operations:
    • Insertion
    • Rectangle queries
    • Nearest neighbor
    • Nearest neighbor iteration
    • Locate at point
    • Element removal
    • efficient bulk loading
  • Features geometric primitives that can readily be inserted into an r-tree:
    • Points (arrays with a constant size)
    • Lines
    • Rectangles
  • Small number of dependencies
  • Serde support with the serde feature

Benchmarks

All benchmarks are performed on a i7-8550U CPU @ 1.80Ghz and with uniformly distributed points. The underlying point type is [f64; 2].

Benchmark Tree size Time
bulk loading 2000 229.82 us
sequentially loading 2000 1.4477 ms
nearest neighbor (bulk loaded tree) 100k 1.32 us
nearest neighbor (sequential tree) 100k 1.56 us
successful point lookup 100k 177.32 ns
unsuccessful point lookup 100k 273.51 ns

Project state

The project is being actively developed, feature requests and PRs are welcome!

Documentation

The documentation is hosted on docs.rs.

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Dependencies

~0.8–1MB
~23K SLoC