Harder, Better, Faster, Stronger Version of Uber H3 in Rust(grim7reaper.github.io) |
Harder, Better, Faster, Stronger Version of Uber H3 in Rust(grim7reaper.github.io) |
Funny to see this on the front page xD
That was the blog post for the initial release, and a lot of things have changed since then (definitely deserves a new blog post ^^).
The first big change happened six months after the release, when I rewrote most of the geometrical algorithms (leveraging the excellent geo crate) and got a massive boost in speed and reduction in memory usage which made it applicable at high resolutions and country-scale levels (e.g. some computation went from 15h to 7min, and from 18GB of RAM to 100MB). I also added support for alternative coverage methods (back then H3 only offered centroid containment).
Since then, the reference implementation has caught up in term of coverage predicate and even provides a new experimental coverage algorithm addressing some performance issue. I haven’t implemented yet but, IIRC, my current implementation still outperforms theirs (but less dramatically so).
I’ve also developed a little ecosystem of libraries around h3o: - Tailored compression algorithm with h3o-zip (in optimal cases I’ve observed reductions from ~2GB to 100KB) - Compact data structure for fast lookup with h3o-ice (based on FST) - Map rendering with h3o-mvt
Most of these things run in production at Amo, where one of the main use cases is powering the Scratchmap feature, both client and server side, in the Bump app. I’ve also seen adoption from other projects (bindings for R, Erlang, Polars, ...) and enterprises :)
I’m working on my own DGGS, A5, the first (and only) to use pentagons. It offers true equal area cells and a much higher cell fidelity (below 1cm compared to 1m for H3).
I’m looking for contributors to get involved and you seem to have the perfect skill set. It would be amazing to have you join the project :) https://a5geo.org/ https://github.com/felixpalmer/a5
Can't say I understand all the math behind it, as it's not my forte (even for H3, for the more numerical parts, I rely on the work of the original authors: I could never have come up with this myself), but your doc is really great!
For the follow-up article, I hope I can get to it eventually. But spare time is a rare currency ^^
As such, I don’t have any name/papers to give you nor point you to similar application. But I would also be interested ^^
But don’t hesitate to reach out if you work on something similar and wanna discuss about it.
Now that H3 provides one, maybe I should take another look at it.
You can see one of my jupyter notebooks that dives deep into this with h3 here: https://drive.google.com/file/d/18jIVEbE_1QbwTbHdMqj0AVqguf2...
The main disadvantage of non-congruent tiling systems like H3 is poor scalability and performance when running analytical computations. In most cases you wouldn't want to shard your underlying data this way even if this is how you want to visualize it.
It is easy to get the best of both worlds. You can shard data models as 3-space spherical embeddings (efficient for large-scale analytic computation) and convert query results to an H3 tiling at wire speed on demand.
See the following visualizations for an illustration:
Sure, hex tiles make certain circular nearest neighbour searches slightly more accurate… but still have an error.
And then… everything else that’s inconvenient with hex tiling, like that issue that subdivisions of a cell leak into the neighbouring cells and hence don’t add up to 100% of the parent! This makes many database queries return lies, or the queries need very complex and slow(!) code to compensate.
Its primary use case was efficient spatial aggregation for applications like pricing, demand forecasting, positioning etc.
For my use case, the visual distortion of S2 was quite a no-go.
As for DB queries, it really depends on your use case and how you store your data, but you can get some good results. But yeah, if you really need exact parent-child containment, S2 is easier to work with.
Edit: It seems some people get a blocked message when visiting the base url. The home path may work better? https://broadbandmap.fcc.gov/home
https://docs.overturemaps.org/guides/addresses/
Picture url: https://docs.overturemaps.org/assets/images/address-coverage...
Use cases are: - data storage - data aggregation/clustering - spatial indexing - geometrical computation (as long as you're OK with approximation, you can speed up a lot of things by working with CellID instead of actual geometries) - data visualization
I've seen it used by Databend, Helium, Breakroom (they did an Erlang binding on top of h3o), beaconDB, Greptime, Meilisearch. But I don't exactly know what they are using it for (just that they pulled h3o in their projects).
https://docs.greptime.com/reference/sql/functions/geo/#h3
These functions encode and decode latitude/longitude to H3 cells and provide utilities for querying cell properties, neighborhoods, distances, and relationships.
