Packages
dynamic_rtree
0.2.0
Distributed Dynamic R-tree (DDRT) implementation for Elixir. It's mainly a R-tree. Why dynamic? Because it's optimized to do fast updates at the tree leafs spatial index. Why distributed? Well.. you can run the DDRT on different nodes and they will have the same r-tree data.
Retired package: Renamed - Package name was changed, look for 'ddrt' hex package to get it. https://hex.pm/packages/ddrt
Current section
Files
Jump to
Current section
Files
dynamic_rtree
README.md
README.md
[](https://circleci.com/gh/windfish-studio/rtree/tree/master)
# DynamicRtree
This is the API module of the elixir r-tree implementation where you can do the basic actions.
## Actions provided:
```elixir
- insert/2
- query/2
- query/3
- delete/2
- update_leaf/3
- execute/1
```
## Installation
The package can be installed
by adding `dynamic_rtree` to your list of dependencies in `mix.exs`:
```elixir
def deps do
[
{:dynamic_rtree, "~> 0.1.0"}
]
end
```
## Usage
Everything is well defined and pretty at [documentation](https://hexdocs.pm/dynamic_rtree/0.1.0/Drtree.html).
You can also find the hex package [here](https://hex.pm/packages/dynamic_rtree/0.1.0).
## Benchmarking
### Delete
```elixir
Operating System: macOS
CPU Information: Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
Number of Available Cores: 4
Available memory: 8 GB
Elixir 1.9.0
Erlang 22.0.7
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
inputs: tree [1000], tree [10000], tree [100000]
Estimated total run time: 21 s
Benchmarking delete [random leaf] with input tree [1000]...
Benchmarking delete [random leaf] with input tree [10000]...
Benchmarking delete [random leaf] with input tree [100000]...
##### With input tree [1000] #####
Name ips average deviation median 99th %
delete [random leaf] 102.55 K 9.75 μs ±65.82% 9 μs 60.94 μs
##### With input tree [10000] #####
Name ips average deviation median 99th %
delete [random leaf] 33.06 K 30.25 μs ±3.91% 30 μs 32 μs
##### With input tree [100000] #####
Name ips average deviation median 99th %
delete [random leaf] 40 K 25 μs ±22.63% 25 μs 29 μs
```
### Update
```elixir
Operating System: macOS
CPU Information: Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
Number of Available Cores: 4
Available memory: 8 GB
Elixir 1.9.0
Erlang 22.0.7
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 10 s
memory time: 0 ns
parallel: 1
inputs: tree [1000], tree [10000], tree [100000]
Estimated total run time: 36 s
Benchmarking continuous update with input tree [1000]...
Benchmarking continuous update with input tree [10000]...
Benchmarking continuous update with input tree [100000]...
##### With input tree [1000] #####
Name ips average deviation median 99th %
continuous update 115.17 8.68 ms ±40.88% 7.45 ms 25.37 ms
##### With input tree [10000] #####
Name ips average deviation median 99th %
continuous update 12.70 78.74 ms ±7.45% 76.99 ms 91.57 ms
##### With input tree [100000] #####
Name ips average deviation median 99th %
continuous update 0.93 1.08 s ±7.94% 1.05 s 1.24 s
```
### Query
```elixir
Operating System: macOS
CPU Information: Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
Number of Available Cores: 4
Available memory: 8 GB
Elixir 1.9.0
Erlang 22.0.7
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
inputs: 100x100 box query, 10x10 box query, 1x1 box query, world box query
Estimated total run time: 1.40 min
Benchmarking tree [1000 leafs] with input 100x100 box query...
Benchmarking tree [1000 leafs] with input 10x10 box query...
Benchmarking tree [1000 leafs] with input 1x1 box query...
Benchmarking tree [1000 leafs] with input world box query...
Benchmarking tree [10000 leafs] with input 100x100 box query...
Benchmarking tree [10000 leafs] with input 10x10 box query...
Benchmarking tree [10000 leafs] with input 1x1 box query...
Benchmarking tree [10000 leafs] with input world box query...
Benchmarking tree [100000 leafs] with input 100x100 box query...
Benchmarking tree [100000 leafs] with input 10x10 box query...
Benchmarking tree [100000 leafs] with input 1x1 box query...
Benchmarking tree [100000 leafs] with input world box query...
##### With input 100x100 box query #####
Name ips average deviation median 99th %
tree [1000 leafs] 2786.01 0.36 ms ±42.21% 0.31 ms 0.98 ms
tree [10000 leafs] 263.88 3.79 ms ±71.01% 3.12 ms 14.39 ms
tree [100000 leafs] 27.65 36.16 ms ±31.55% 31.64 ms 100.82 ms
Comparison:
tree [1000 leafs] 2786.01
tree [10000 leafs] 263.88 - 10.56x slower +3.43 ms
tree [100000 leafs] 27.65 - 100.75x slower +35.80 ms
##### With input 10x10 box query #####
Name ips average deviation median 99th %
tree [1000 leafs] 7.56 K 132.32 μs ±268.69% 107 μs 367.48 μs
tree [10000 leafs] 1.52 K 658.95 μs ±175.00% 500 μs 2302.66 μs
tree [100000 leafs] 0.27 K 3728.35 μs ±24.95% 3482 μs 6102.92 μs
Comparison:
tree [1000 leafs] 7.56 K
tree [10000 leafs] 1.52 K - 4.98x slower +526.63 μs
tree [100000 leafs] 0.27 K - 28.18x slower +3596.03 μs
##### With input 1x1 box query #####
Name ips average deviation median 99th %
tree [1000 leafs] 11.80 K 84.77 μs ±208.07% 67 μs 311 μs
tree [10000 leafs] 2.49 K 401.61 μs ±138.07% 289 μs 1539.88 μs
tree [100000 leafs] 0.81 K 1237.44 μs ±66.31% 1051 μs 3267.45 μs
Comparison:
tree [1000 leafs] 11.80 K
tree [10000 leafs] 2.49 K - 4.74x slower +316.84 μs
tree [100000 leafs] 0.81 K - 14.60x slower +1152.67 μs
##### With input world box query #####
Name ips average deviation median 99th %
tree [1000 leafs] 3048.78 0.33 ms ±41.19% 0.29 ms 0.81 ms
tree [10000 leafs] 323.73 3.09 ms ±14.12% 2.94 ms 4.90 ms
tree [100000 leafs] 15.93 62.79 ms ±7.50% 62.05 ms 93.63 ms
Comparison:
tree [1000 leafs] 3048.78
tree [10000 leafs] 323.73 - 9.42x slower +2.76 ms
tree [100000 leafs] 15.93 - 191.43x slower +62.46 ms
```
### Insert
```elixir
Operating System: macOS
CPU Information: Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
Number of Available Cores: 4
Available memory: 8 GB
Elixir 1.9.0
Erlang 22.0.7
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
inputs: 1000 leafs, 10000 leafs, 100000 leafs
Estimated total run time: 42 s
Benchmarking tree [100000] with input 1000 leafs...
Benchmarking tree [100000] with input 10000 leafs...
Benchmarking tree [100000] with input 100000 leafs...
Benchmarking tree [empty] with input 1000 leafs...
Benchmarking tree [empty] with input 10000 leafs...
Benchmarking tree [empty] with input 100000 leafs...
##### With input 1000 leafs #####
Name ips average deviation median 99th %
tree [empty] 33.16 30.16 ms ±57.33% 27.06 ms 175.02 ms
tree [100000] 8.15 122.63 ms ±0.00% 122.63 ms 122.63 ms
Comparison:
tree [empty] 33.16
tree [100000] 8.15 - 4.07x slower +92.47 ms
##### With input 10000 leafs #####
Name ips average deviation median 99th %
tree [empty] 2.44 410.03 ms ±28.11% 363.34 ms 737.25 ms
tree [100000] 2.27 441.37 ms ±0.00% 441.37 ms 441.37 ms
Comparison:
tree [empty] 2.44
tree [100000] 2.27 - 1.08x slower +31.34 ms
##### With input 100000 leafs #####
Name ips average deviation median 99th %
tree [empty] 0.22 4.56 s ±7.30% 4.56 s 4.80 s
tree [100000] 0.158 6.35 s ±0.00% 6.35 s 6.35 s
Comparison:
tree [empty] 0.22
tree [100000] 0.158 - 1.39x slower +1.78 s
```