Crate hash_rstar 

hash-rstar

A concurrent spatial index combining geohash and R-tree data structures for efficient geographic point queries. This library provides thread-safe operations and optional persistence support.

Features

• Concurrent spatial indexing using thread-safe DashMap
• Geohash-based spatial partitioning
• R-tree for efficient spatial queries within partitions
• Optional persistence using sled database
• Two nearest neighbor search strategies
• Async loading support

Usage

use hash_rstar::{AABB, GeohashRTree, GeohashRTreeObject, PointDistance, RTreeObject};
use geo::{Distance, Haversine};

#[derive(Debug, PartialEq, Clone, bincode::Encode, bincode::Decode)]
struct Location {
    id: String,
    x_coordinate: f64,
    y_coordinate: f64,
}

impl GeohashRTreeObject for Location {
    fn unique_id(&self) -> String {
        self.id.clone()
    }

    fn x_y(&self) -> (f64, f64) {
        (self.x_coordinate, self.y_coordinate)
    }
}

impl RTreeObject for Location {
    type Envelope = AABB<[f64; 2]>;
    fn envelope(&self) -> Self::Envelope {
        AABB::from_point([self.x_coordinate, self.y_coordinate])
    }
}

impl PointDistance for Location {
    fn distance_2(&self, point: &[f64; 2]) -> f64 {
        let self_geo_point = geo::point!(x: self.x_coordinate, y: self.y_coordinate);
        let target_geo_point = geo::point!(x: point[0], y: point[1]);
        Haversine::distance(self_geo_point, target_geo_point)
    }
}

let tree: GeohashRTree<Location> = GeohashRTree::new(5, None).unwrap();

let location = Location {
    id: "1".into(),
    x_coordinate: 116.400357,
    y_coordinate: 39.906453,
};

tree.insert(location.clone()).unwrap();

if let Some(nearest) = tree.adjacent_cells_nearest(&location).unwrap() {
    println!("Found nearest point: {:?}", nearest);
}

Search Strategies

The library provides two nearest neighbor search strategies:

1. adjacent_cells_nearest: Fast approximate search

   • Searches current and 8 adjacent geohash cells
   • Best for evenly distributed points
   • Quickest response time

2. sorted_cells_nearest: Exact search

   • Searches cells in order of increasing distance
   • Guarantees finding true nearest neighbor
   • Best for unevenly distributed points

Persistence

Optional persistence is supported using sled database:

use std::path::PathBuf;

let tree = GeohashRTree::new(6, Some(PathBuf::from("data.db"))).unwrap();

Thread Safety

All operations are thread-safe, allowing concurrent access from multiple threads:

• Concurrent reads and writes using DashMap
• Thread-safe persistence with Arcsled::Db
• Async loading support

Performance Considerations

• Geohash precision affects partition size and query performance
• Higher precision = smaller cells = more precise but slower searches
• Lower precision = larger cells = faster but less precise searches
• Choose based on data distribution and query patterns

Structs

AABB

An n-dimensional axis aligned bounding box (AABB).

GeohashRTree

A concurrent geohash-based R-tree structure for spatial indexing.

Enums

GeohashRTreeError

Traits

GeohashRTreeObject

PointDistance

Defines objects which can calculate their minimal distance to a point.

RTreeObject

An object that can be inserted into an r-tree.