RTree2D is a 2D immutable R-tree with STR (Sort-Tile-Recursive) packing.

Main our requirements was:

• efficiency: we wanted the R-Tree to be able to search millions of points efficiently even in case of highly overlapped entries, also, we needed to be able to quickly rebuild R-tries with a per minute rate producing minimum pressure on GC
• immutability: different threads needed to be able to work with the same R-tree without problems, at the same time some thread can build a new version of the R-tree reusing immutable entries from the previous version

To archive these goals we have used:

• STR packing that is a one of the most efficient packing method which produces balanced R-tree for the specified sequence of entries
• a memory representation and access patterns to it which are aware of a cache hierarchy of contemporary CPUs (while it is not a final version and can be improved further soon)
• efficient implementations of search functions with minimum of virtual calls and allocations (there are versions with zero allocations)

The library is published to JCenter, so please add a resolver for it in your build.sbt file or ensure that it is already added:

resolvers += Resolver.jcenterRepo

Add the library to a dependency list:

libraryDependencies += "com.sizmek.rtree2d" %% "core" % "0.2.0"

Entries of R-tree are represented by RTreeEntry instances which contains payload and 4 coordinates of the minimum bounding rectangle (MBR) for it.

Add import, create entries, build an R-tree from them, and use it for search by point or rectangle requests:

import com.sizmek.rtree2d.core._

val poi1 = RTreeEntry(1.0f, 1.0f, 2.0f, 2.0f, "point of interest 1")
val poi2 = RTreeEntry(2.0f, 2.0f, 3.0f, 3.0f, "point of interest 2")
val entries = Seq(poi1, poi2)

val rtree = RTree(entries)

assert(rtree.entries == entries)
assert(rtree.searchAll(0.0f, 0.0f) == Nil)
assert(rtree.searchAll(1.5f, 1.5f) == Seq(poi1))
assert(rtree.searchAll(2.5f, 2.5f) == Seq(poi2))
assert(rtree.searchAll(1.5f, 1.5f, 2.5f, 2.5f).forall(entries.contains))

Please, check out Scala docs in sources and tests. for other functions which allows no allocations and fast exit from search requests.

Charts below are latest results of benchmarks which compare RTree2D with Archery and David Monten's rtree libraries using JDK 8 on the following environment: Intel® Core™ i7-7700HQ CPU @ 2.8GHz (max 3.8GHz), RAM 16Gb DDR4-2400, Ubuntu 18.04, latest versions of Oracle JDK 8.

Main metric tested by benchmarks is an execution time in nanoseconds. So lesser values are better. Please, check out the Run benchmarks section bellow how to test other metrics like allocations in bytes or number of some CPU events.

Benchmarks have the following parameters:

• size is a number of entries in the R-tree
• shuffle is a flag to turn on/off shuffling of entries before R-tree building
• overlap is a size of entries relative to interval between them

The apply benchmark test building of R-tries from a sequence of entires.

No overlapping of entries (overlap = 0.1):

Entries with lot of overlaps (overlap = 5):

The searchByPoint benchmark test requests that search entries with intersects with the specified point.

No overlapping of entries (overlap = 0.1):

Entries with lot of overlaps (overlap = 5):

Other benchmarks tests searching by rectangles, returning entries back from R-tries, inserting and removing bulk of entries to/from them.

Charts with their results are available in subdirectories of the docs directory.

To compile, run tests, check coverage for different Scala versions use a command:

sbt clean +coverage +test +coverageReport +mimaReportBinaryIssues

Benchmarks are developed in the separated module using Sbt plugin for JMH tool.

Feel free to modify benchmarks and check how it works with your data, JDK, and Scala versions.

To see throughput with allocation rate run benchmarks with GC profiler using the following command:

sbt -no-colors clean 'benchmark/jmh:run -prof gc -rf json -rff rtries.json .*'

It will save benchmark report in benchmark/rtries.json file.

Results that are stored in JSON can be easy plotted in JMH Visualizer by drugging & dropping of your file(s) to the drop zone or using the source or sources parameters with an HTTP link to your file(s) in the URLs: http:https://jmh.morethan.io/?source=<link to json file> or http:https://jmh.morethan.io/?sources=<link to json file1>,<link to json file2>.

Also, there is an ability to run benchmarks and visualize results with a charts command. It adds -rf and -rff options to all passes options and supply them to jmh:run task, then group results per benchmark and plot main score series to separated images. Here is an example how it can be called for specified version of JVM, value of the overlap parameter, and patterns of benchmark names:

sbt 'charts -jvm /usr/lib/jvm/java-8-oracle/bin/java -p overlap=0.1 .*apply.* .*search.*'

Results will be places in a cross-build suffixed subdirectory of the benchmark/target directory in *.png files:

$ ls benchmark/target/scala-2.12/*.*n*

benchmark/target/scala-2.12/apply.png
benchmark/target/scala-2.12/searchByPoint.png
benchmark/target/scala-2.12/benchmark.json

Publish to local Ivy repo:

sbt publishLocal

Publish to local Maven repo:

sbt publishM2

For version numbering use Recommended Versioning Scheme that is used in the Scala ecosystem.

Double check binary and source compatibility, including behavior, and release using the following command (credentials are required):

sbt release

Do not push changes to github until promoted artifacts for the new version are not available for download on jCenter to avoid binary compatibility check failures in triggered Travis CI builds.