LSPH - Learned SPatial HashMap (LSPH)

fast 2d point query powered by hashmap and statistic 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<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);

Running Demos

LSPH includes two comprehensive demo applications to showcase its capabilities:

Geographic Data Demo

A command-line demo using real Melbourne geographic data (6,361 points):

cd examples/demo
cargo run --release

Features:

• Real-world geographic data processing
• Performance benchmarking and analysis
• Interactive nearest neighbor queries
• Range query demonstrations
• Memory usage and throughput metrics

Interactive GUI Demo

A graphical demonstration with visual spatial operations:

cd examples/interactive_demo
cargo run --release

Interactive demo showing nearest neighbor search with responsive UI and visual feedback

Features:

• Visual point addition and management
• Interactive nearest neighbor search
• Range query visualization
• Real-time performance metrics

To Run Benchmark:

cargo bench

License

Licensed under either of

• Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.