Bonsai

Bonsai is a versatile, zero-dependency Rust library that delivers a self-tuning spatial index capable of adapting to the dynamic changes in data and query performance requirements. This library operates transparently, continuously profiling the data and query workload at runtime, and seamlessly switching between various index backends — including R-tree, KD-tree, Quadtree, and Grid — to ensure optimal query performance without requiring intervention from developers.

Features

• Dimensional Flexibility: Supports generic dimensionality from 1 to 8 and allows for both f32 and f64 coordinate types.
• FFI and WASM Support: Comes with a C FFI layer and a WASM target to enhance compatibility with other languages and platforms.
• Zero Mandatory Dependencies: The core functionality of Bonsai has no required external dependencies, making it lightweight and easy to integrate.

Installation

Bonsai can be easily added to Rust projects as a dependency through Cargo. For more details on installation, refer to the crate page.

Usage Examples

To illustrate its capabilities, here are several usage examples:

Basic 2D Example

use bonsai::BonsaiIndex;
use bonsai::types::{BBox, Point};

let mut index = BonsaiIndex::<&str>::builder().build();

index.insert(Point::new([1.0, 2.0]), "alpha");
index.insert(Point::new([3.0, 4.0]), "beta");
index.insert(Point::new([5.0, 6.0]), "gamma");
index.insert(Point::new([7.0, 8.0]), "delta");
index.insert(Point::new([9.0, 0.0]), "epsilon");

let bbox = BBox::new(Point::new([0.0, 0.0]), Point::new([6.0, 6.0]));
let results = index.range_query(&bbox);
println!("range hits: {}", results.len()); // alpha, beta, gamma

Advanced Dimensional Example

// 6D: [x, y, z, roll, pitch, yaw]
let mut index = BonsaiIndex::<String, f64, 6>::builder()
    .initial_backend(bonsai::types::BackendKind::KDTree)
    .reservoir_size(2048)
    .build();

index.insert(Point::new([1.0, 2.0, 3.0, 0.1, 0.2, 0.3]), "pose_a".to_string());

Extensive Configuration Options

Bonsai provides a range of configuration options that cater to the specific needs and performance goals of different applications. For instance, one can adjust the starting backend, tuning thresholds for migration, and other factors.

Integration with Other Languages

Bonsai features an easy-to-use C FFI layer, allowing integration with languages that support C interoperability, such as Python, making it versatile for multi-language projects.

Example in C:

#include <stdio.h>
#include "bonsai.h"

int main(void) {
    BonsaiHandle *idx = bonsai_new();
    // Perform operations such as insertion and queries
    bonsai_free(idx);
    return 0;
}

Use Cases

Bonsai is well-suited for various applications, including but not limited to:

• Gaming and simulation environments where spatial data is constantly changing.
• Geospatial queries for data sets such as GPS traces or postal code searches.
• Data analytics applications, such as exploration of astronomical catalogs.
• Robotics and physics simulations, facilitating real-time collision avoidance and event displays.

Architectural Overview

Bonsai employs a lock-free architecture designed to minimize query blocking during migrations, ensuring high performance and responsiveness.

In conclusion, Bonsai is an advanced spatial indexing solution enabling efficient data querying and adaptability, catering to diverse application domains.