### 3 releases

0.9.2 | Feb 5, 2021 |
---|---|

0.9.1 | Feb 3, 2021 |

0.9.0 | Feb 3, 2021 |

#**1629** in Algorithms

**Apache-2.0**

13KB

134 lines

# Anti-R

Anti-R contains a alternative spatial data structure that outperforms R-Trees for low amounts of nodes.

# Performance:

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.

# Contributing

See README.md at the root of the repository.