Trees for fast location-to-value lookup.

Overview

CI Documentation

HexTree

hextree provides tree structures that represent geographic regions with H3 cells.

The primary structures are:

  • HexTreeMap: an H3 cell-to-value map.
  • HexTreeSet: an H3 cell set for hit-testing.

You can think of HexTreeMap vs. HexTreeSet as HashMap vs. HashSet.

How is this different from HashMap<H3Cell, V>?

The key feature of a hextree is that its keys (H3 cells) are hierarchical. For instance, if you previously inserted an entry for a low-res hex, but later query for a higher-res child hex, the tree returns the value for the lower res hex. Additionally, with compaction, trees can automatically coalesce adjacent high-res hexagons into their parent hex. For very large regions, the compaction process can continue to lowest resolution cells (res-0), possibly removing millions of redundant cells from the tree. For example, a set of 4,795,661 res-7 cells representing North America coalesces into a 42,383 element HexTreeSet.

A hextree's internal structure exactly matches the semantics of an H3 cell. The root of the tree has 122 resolution-0 nodes, followed by 15 levels of 7-ary nodes. The level of an occupied node, or leaf node, is the same as its corresponding H3 cell resolution.

Features

  • serde-support: support for serialization via serde.

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Comments
  • Convert HexSet to be a HexMap

    Convert HexSet to be a HexMap

    This PR is a major change. It turns HexSet into HexMap<Value>. Think of it as a dictionary of Hex → Value, but one that understands the hierarchical nature of H3. You can query a small hex for a value, but possibly get returned the value for a 'complete' parent hex. If all you wanted was a Hex → Value dictionary, a regular HashMap<H3Cell, V> would do.

    What about sets?

    With this change, what we HexSet is represented as a HexMap<()>, where we're using the unit (()) type for values. Unfortunately, this does not optimize into the equivalent of the previous HexSet type and imposes fairly large performance penalties. The performance hits are in the neighborhood of 130% on my 2013 Mac Pro. But keep in mind that means that calls to .contains() now take ~40 ns when they used to take ~17 ns. 40 ns is still pretty damn fast.

    EDIT: I switched to criterion for proper benchmarking and the performance difference is negligible

    Remaining work

    • [x] decide if pluggable compactor is part of the map or only provided with .insert_and_compact()
    • [ ] ability to reduce a hex?
    • [x] update documentation to reflect this major change
    • [ ] ~make HexSet its own type to avoid Value = () perf hit?~ out of scope
    • [x] rename this repo hexmap right before/after merging

    The first point about where the compactor should live has major implications for serialization, the namability of types, etc. For example, what if the user wants to use a closure for compaction? That's currently supported. But if the compactor was a generic member of the HexMap type itself, how do you name it? Hint: you can't name the type of closure.

    On the second point about reduction: what if, instead of getting the value for a Hex, the user wants to perform a reduction/fold on all children for a particular hex? Reduction could be very useful when you want to say, summarize all data for all hexes in a region. That would be hard to do without exposing the internal Node type.

    opened by JayKickliter 5
  • Implement Key/Value iterator

    Implement Key/Value iterator

    Set/maps should implement .iter[_mut]() which returns an iterator over all cells.

    Note to potential implementor: Nodes do not store their keys (cells). It's not necessary, since the structure mimics the semantics of H3. We'll need to reconstruct cell values as part of the tree walk. I suspect this could be a pretty big bottleneck, but it's better than the larger performance hit we'd incur if nodes did store a copy of their cell.

    enhancement help wanted 
    opened by JayKickliter 0
  • Speed up

    Speed up

    This was originally a PR against @Vagabond's adt/refactor branch. After a bunch of messy rebases, it has a bit more than speedup code, but this project is churning so YOLO

    opened by JayKickliter 0
  • Make parse_h3cell faster

    Make parse_h3cell faster

    it looks like parse_h3cell is the biggest bottleneck. This patch makes the test cases almost 3x faster on my machine.

    Additionally, I added a .len() method. With it, I discovered that the - 1 was making an HTree with only 836 leaves instead of the 42383 contained in the source region.

    opened by JayKickliter 0
  • Improve construction speed

    Improve construction speed

    Major goal: it would be awesome it we could both construct a compacted tree and drain it to a vec faster than calling libh3's compact() function. My gut feeling is the bottle neck currently lays non-deterministic alloction of behavior of a hexset. I do have a PR that improves things, but it probably needs some work. See https://github.com/JayKickliter/HexSet/pull/4

    opened by JayKickliter 0
  • Place all nodes in an arena of sorts

    Place all nodes in an arena of sorts

    This is an experimental PR to improve HexSet creation. It appears to halve the time to build up very large sets at the expense of up about slowing down contains() by about 20%. I originally thought this approach could take advance of cache locality to also improve contains, so this PR may be dead in the water.

    opened by JayKickliter 0
Owner
Jay Kickliter
Jay Kickliter
Fast Geospatial Feature Storage API

Hecate OpenStreetMap Inspired Data Storage Backend Focused on Performance and GeoJSON Interchange Hecate Feature Comparison Feature Hecate ESRI MapSer

Mapbox 243 Dec 19, 2022
Blazing fast and lightweight PostGIS vector tiles server

Martin Martin is a PostGIS vector tiles server suitable for large databases. Martin is written in Rust using Actix web framework. Requirements Install

Urbica 921 Jan 7, 2023
Fast 2D Delaunay triangulation in Rust. A port of Delaunator.

delaunator-rs A very fast static 2D Delaunay triangulation library for Rust. A port of Delaunator. Documentation Example use delaunator::{Point, trian

Vladimir Agafonkin 123 Dec 20, 2022
Fast shortest path calculations for Rust

Fast Paths The most famous algorithms used to calculate shortest paths are probably Dijkstra's algorithm and A*. However, shortest path calculation ca

Andi 226 Jan 2, 2023
A fast R-tree for Rust. Ported from an implementation that's designed for Tile38.

rtree.rs A fast R-tree for Rust. Ported from an implementation that's designed for Tile38. Features Optimized for fast inserts and updates. Ideal for

Josh Baker 102 Dec 30, 2022
A fast, offline, reverse geocoder

Rust Reverse Geocoder A fast reverse geocoder in Rust. Inspired by Python reverse-geocoder. Links Crate Changelog Latest Docs v2.0 Docs v1.0 Docs Desc

Grant Miner 82 Dec 3, 2022
Easy c̵̰͠r̵̛̠ö̴̪s̶̩̒s̵̭̀-t̶̲͝h̶̯̚r̵̺͐e̷̖̽ḁ̴̍d̶̖̔ ȓ̵͙ė̶͎ḟ̴͙e̸̖͛r̶̖͗ë̶̱́ṉ̵̒ĉ̷̥e̷͚̍ s̷̹͌h̷̲̉a̵̭͋r̷̫̊ḭ̵̊n̷̬͂g̵̦̃ f̶̻̊ơ̵̜ṟ̸̈́ R̵̞̋ù̵̺s̷̖̅ţ̸͗!̸̼͋

Rust S̵̓i̸̓n̵̉ I̴n̴f̶e̸r̵n̷a̴l mutability! Howdy, friendly Rust developer! Ever had a value get m̵̯̅ð̶͊v̴̮̾ê̴̼͘d away right under your nose just when

null 294 Dec 23, 2022
A number of collections, such as linked-lists, binary-trees, or B-Trees are most easily implemented with aliasing pointers.

StaticRc is a safe reference-counted pointer, similar to Rc or Arc, though performing its reference-counting at compile-time rather than run-time, and

null 372 Dec 19, 2022
K-dimensional tree in Rust for fast geospatial indexing and lookup

kdtree K-dimensional tree in Rust for fast geospatial indexing and nearest neighbors lookup Crate Documentation Usage Benchmark License Usage Add kdtr

Rui Hu 152 Jan 2, 2023
K-dimensional tree in Rust for fast geospatial indexing and lookup

kdtree K-dimensional tree in Rust for fast geospatial indexing and nearest neighbors lookup Crate Documentation Usage Benchmark License Usage Add kdtr

Rui Hu 154 Jan 4, 2023
CLI utility to move (or rename) your files to a new location and redirect all of its symbolic links, to the new path

Move Links CLI utility to move (or rename) your files to a new location and redirect all of its symbolic links, to the new path (or name). Usage execu

Ben Mefteh 18 May 22, 2022
A small tool to clone git repositories to a standard location, organised by domain name and path.

A small tool to clone git repositories to a standard location, organised by domain name and path. Runs on BSD, Linux, macOS, Windows, and more.

Wesley Moore 68 Dec 19, 2022
A program written in Rust, that allows the user to find the current location of the International Space Station and see it on a map.

ISS Location ViewFinder A program written in Rust, that allows the user to find the current location of the International Space Station and see it on

Suvaditya Mukherjee 2 Nov 8, 2021
Wraps cargo to move target directories to a central location [super experimental]

targo Wraps cargo to move target directories to a central location [super experimental] To use, cargo install --git https://github.com/sunshowers/targ

Rain 18 Jan 7, 2023
Persist game settings like music volume or graphic settings in a nice toml file in the right location.

Bevy Settings The goal of this project is to store settings in a resource throughout game launches. Currently this crate supports Linux, Mac and Windo

Tobias Kriebisch 9 Feb 25, 2023
General basic key-value structs for Key-Value based storages

General basic key-value structs for Key-Value based storages

Al Liu 0 Dec 3, 2022
A Quest to Find a Highly Compressed Emoji :shortcode: Lookup Function

Highly Compressed Emoji Shortcode Mapping An experiment to try and find a highly compressed representation of the entire unicode shortcodes-to-emoji m

Daniel Prilik 13 Nov 16, 2021
Library + CLI-Tool to measure the TTFB (time to first byte) of HTTP requests. Additionally, this crate measures the times of DNS lookup, TCP connect and TLS handshake.

TTFB: CLI + Lib to Measure the TTFB of HTTP/1.1 Requests Similar to the network tab in Google Chrome or Mozilla Firefox, this crate helps you find the

Philipp Schuster 24 Dec 1, 2022
Experimenting with Rust implementations of IP address lookup algorithms.

This repository contains some very rough experimentation with Rust implementations of IP address lookup algorithms, both my own and comparison with th

Ximon Eighteen 0 Jan 10, 2022
Kepler is a vulnerability database and lookup store and API currently utilising National Vulnerability Database and NPM Advisories as data sources

Kepler — Kepler is a vulnerability database and lookup store and API currently utilising National Vulnerability Database and NPM Advisories as data so

Exein.io 101 Nov 12, 2022