kd-tree-comparison

This project benchmarks a few different k-d tree libraries in different scenarios. It measures construction time as well as query time, across a matrix of tree sizes, dimensionality, and underlying data type.

Comments and contributions are welcome.

Data Visualization

A companion webapp to this test suite exists where the results can be explored interactively, at https://sdd.github.io/kd-tree-comparison-webapp/.

The repository for the visualisation webapp is at https://github.com/sdd/kd-tree-comparison-webapp

Libraries tested

(full disclosure: I'm the author of Kiddo)

• Kiddo v5.x
• Kiddo v3.x
• Kiddo v2.x
• Kiddo v1.x / v0.2.x
• FNNTW v0.2.3
• nabo-rs v0.2.1
• pykdtree v1.3.4
• sklearn.neighbours.KDTree v1.2.2
• scipy.spatial.KDTree v1.10.1

Running the benchmarks to generate NDJSON

cargo criterion --message-format json > all-benchmarks.ndjson

Converting the criterion NDJSON into a convenient JSON object

jq -s '.[] | select(.reason == "benchmark-complete") | with_entries(select([.key] | inside(["id", "mean"])))'  < all-benchmarks.ndjson | jq -s > all-benchmarks.json

Benchmark System Details

• Processor: Ryzen 5900X (12/24 core)
• Memory: 32Gb DDR4, 3600MHz