|0.9.2||Feb 5, 2021|
|0.9.1||Feb 3, 2021|
|0.9.0||Feb 3, 2021|
#1629 in Algorithms
Anti-R contains a alternative spatial data structure that outperforms R-Trees for low amounts of nodes.
R-Trees and anti-r have the same O(n) complexity for all operations, log(n) for searching and updating, n*log(n) for creation.
They only differ by constant factors, either x or y in O(log_b(n+x)+y) and the base of the logarithm, which is 2 for Anti-R and configurable for R-Tree, generally 3-6.
Anti-R is always faster at updating all elements and bulk-loading by a constant factor, therefore it is more noticeable for small n.
Full updates and bulk-loads are equivalent in speed for Anti-R. For R-Trees full updates are never worth it, a full reconstruction is simply faster.
Zero to a bit more than 10_000 elements are faster to bounding box-query for Anti-R. Zero to about 1000 elements are faster to distance-query for Anti-R.
R-Trees might be catching up quicker if the elements are weirdly distributed.
See the bench directory and the output of cargo bench (target/criterion) for more details.
Notice that this has been benched against the rstar crate, which might not be the fastest implementation of an R-Tree in existence. The benchmark results are exactly as expected though.
See README.md at the root of the repository.