lsph

Crates.iolsph
lib.rslsph
version0.1.8
sourcesrc
created_at2022-04-18 07:20:40.160353
updated_at2024-04-17 15:02:16.584346
descriptionLearned Spatial HashMap
homepagehttps://github.com/jackson211/lsph
repositoryhttps://github.com/jackson211/lsph
max_upload_size
id569737
size86,979
Jackson Shi (jackson211)

documentation

https://docs.rs/lsph

README

LSPH - Learned SPatial HashMap

fast 2d point query powered by hashmap and statistic model

Github Workflow crates.io version dos.io dependency status

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<f32>, 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);

To Run Benchmark:

cargo bench

License

Licensed under either of

at your option.

Commit count: 101

cargo fmt