Crate lsph

Source
Expand description

This crate implements the Learned SPatial HashMap(LSPH), a high performance spatial index uses HashMap with learned model.

The original paper of LSPH can be found here.

The LSPH uses a learned model such as a linear regression model as the hash function to predict the index in a hashmap. As a result, the learned model is more fitted to the data that stored in the hashmap, and reduces the chance of hashing collisions. Moreover, if the learned model is monotonic function(e.g. linear regression), the hash indexes are increasing as the input data increases. This property can be used to create a sorted order of buckets in a hashmap, which allow us to do range searches in a hashmap.

The LSPH supports:

  • Point Query
  • Rectange Query
  • Radius Range Query
  • Nearest Neighbor Query

Example:

use lsph::{LearnedHashMap, LinearModel};
let point_data = vec![[1., 1.], [2., 1.], [3., 2.], [4., 4.]];
let (mut map, points) = LearnedHashMap::<LinearModel<f64>, f64>::with_data(&point_data).unwrap();

assert_eq!(map.get(&[1., 1.]).is_some(), true);
assert_eq!(map.get(&[3., 1.]).is_none(), true);
assert_eq!(map.range_search(&[0., 0.], &[3., 3.]).is_some(), true);
assert_eq!(map.radius_range(&[2., 1.], 1.).is_some(), true);
assert_eq!(map.nearest_neighbor(&[2., 1.]).is_some(), true);

§License

Licensed under either of

at your option.

Re-exports§

pub use geometry::*;
pub use hasher::*;
pub use map::*;
pub use models::*;

Modules§

geometry
hasher
map
models

Macros§

assert_delta
assert_empty
assert_eq_len