Harder, Better, Faster, Stronger Version of Uber H3 in Rust

https://grim7reaper.github.io/blog/2023/01/09/the-hydronium-project/

by ashergill • 9 months ago

112 40 9 months ago

grim7reaper.github.io

krapht• 9 months ago

This is cool. Not personally going to switch because I want to stay with the official implementation, but I appreciate the effort involved in porting libraries.

ramon156• 9 months ago

This is pretty big for WASM projects

serjester2• 9 months ago

H3o is an awesome piece of work. I created polars bindings for it(another reason I love polars) and last time I benchmarked it, it had 5X better performance than even duckdb’s C++ implementation.

https://github.com/Filimoa/polars-h3

grim7reaper7• 9 months ago

I really want to do a DuckDB extension someday, I think it would be pretty cool. I had looked into it 2 years ago but didn't dig further.

Now that H3 provides one, maybe I should take another look at it.

grim7reaper7• 9 months ago

Author here!

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 :)

pheelicks2• 9 months ago

Very impressive results, cool to see innovation in this space! I’d definitely be interested in a follow up post going into the details of the geometric algorithms.

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

grim7reaper7• 9 months ago

Ha, yeah, I remember reading about your project back in April (I think someone shared it on the GeoRust Discord). Really cool stuff you have here!

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 ^^

ajfriend• 9 months ago

h3o-zip is really impressive! I've been wanting to play around with it more, and I've been meaning to ask you if you have any good references for that encoding approach. I understand how it works in h3o-zip, but I'd be interested to know more about where else that approach has been used.

grim7reaper7• 9 months ago

I’m pretty sure the approach isn’t that novel, but I really rediscovered it on my own while exploring several compressions approaches (generic compressions with tailored dict like zstd, integer packing/compressions, compressed bitmap, …: I probably have my notes about these somewhere)

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.

websiteapi• 9 months ago

who is using uber h3 and what for? (besides uber of course)

Audiolite2• 9 months ago

As one example, the U.S. Federal Communications Commission uses it in its Broadband Data Collection program. You can see some of how it's been implemented here: https://broadbandmap.fcc.gov/

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

maxnoe• 9 months ago

I cannot... Geoblockig European IPs?

simonw• 9 months ago

That's really neat. Here's a screenshot for people who can't access that URL: https://gist.github.com/simonw/eb31ec34af16a1e19ee0d7ca90e8a...

zX41ZdbW2• 9 months ago

H3 was integrated into ClickHouse in 2019, and since then, I have heard many interesting stories. There are unusual ones, e.g., when it is used not to map data on Earth, but for astronomy (stars, galaxies).

grim7reaper7• 9 months ago

I'm curious about those interesting stories ^^ Care to share a bit more?

jandrewrogers3• 9 months ago

H3 is commonly used for creating visualization aggregates e.g. creating visual summaries of data distribution. That was its primary design case.

justanotherunit• 9 months ago

I’ve used h3 for a game. Since they align with an unique hex, I can ensure that one cell grid aligns and is placed on the same place in the world, where players could then compete on.

grim7reaper7• 9 months ago

amo is using it quite a lot, mainly for the scratch map feature in the Bump Map application, but not only.

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).

killme2008• 9 months ago

Hi. I am from GreptimeDB team. We use h3o library to implement h3 functions:

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.

zigzag312• 9 months ago

Overture maps docs use it to visualize the coverage of Overture address data.

https://docs.overturemaps.org/guides/addresses/

Picture url: https://docs.overturemaps.org/assets/images/address-coverage...

seanlane2• 9 months ago

We use it at Neighbor.com for a lot of data analysis in our marketplace, things like our price recommendations, supply and demand balances, etc.

misiti3780• 9 months ago

my company uses it for displays buildings in our geospatial product.

kj4211cash• 9 months ago

we have used it at my last 2 companies for most geospatial data analyses. defining and visualizing catchment areas. making maps dividing up service areas. picking out high demand density areas. etc. before h3, both companies were using zipcodes and more ad-hoc data transformations. i'm not saying h3 is perfect. i wouldn't know. but it definitely beats zipcodes.

jiggawatts• 9 months ago

I never understood why anyone would prefer the H3 hex tiles over Google’s much simpler S2 system: http://s2geometry.io/

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.

grim7reaper7• 9 months ago

They have a page about pros and cons: https://h3geo.org/docs/comparisons/s2/

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.

vladimirzaytsev• 9 months ago

H3 is preferred for geo analytics because it produces a more uniform spatial index with low distortion and consistent distances between cells

Its primary use case was efficient spatial aggregation for applications like pricing, demand forecasting, positioning etc.

seanlane2• 9 months ago

Some of the original developers of H3 gave a presentation about it that goes over the tradeoffs between those different systems, would recommend watching it.

https://www.youtube.com/watch?v=wDuKeUkNLkQ

brookman64k• 9 months ago

It also uses pentagons in some places because a hexagonal grid can‘t tile a sphere. They made sure that the pentagons are located in water, but this feels like it will add even more edge cases to handle.

chillchilla• 9 months ago

S2 is attractive, but the corpus of use cases outside the Pokemon Go community is quite small. The sheer number of companies and hobbyists using H3 for analytics across a wide spectrum makes it much more attractive than S2. H3 functions are built directly into Snowflake DB for example, and h3 extensions / plugins are widely available. I tried and tried to use S2 in my company but the lack of available use cases and examples made it tough to adopt.

mattrighetti• 9 months ago

TIL! What are the advantages of hexagonal spatial indexing compared to e.g. quad trees, r-trees?

ashergill2• 9 months ago

The main advantages of hexagons are that the distance to each neighbour is always the same, and the distortion across the globe is much less, because of the way H3 creates its grid (compared to the earlier Google S2 which uses squares and distorts a lot). There’s an excellent Uber blog post about this, I’ll see if I can find the link.

ashergill2• 9 months ago

(here’s the blog post: https://www.uber.com/en-GB/blog/h3/ )

jandrewrogers3• 9 months ago

The main advantage of hexagonal spherical tiling systems is that they are roughly equal area at a given resolution. This makes them particularly suitable for generating visualizable aggregates when you primarily care about spatial distribution rather than specific boundaries (like borders).

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.

pheelicks2• 9 months ago

It is a common misconception that h3 is equal area. At any resolution level the cell size varies by a factor of 2, which is (roughly) the same as S2.

See the following visualizations for an illustration:

https://a5geo.org/examples/area

https://a5geo.org/examples/airbnb

serjester2• 9 months ago

One of the big ones that hasn't been mentioned is all of a hexagon's neighbors are equidistant. As a result, h3 is a better fit for flow modeling - stuff like telematics. This has some nice properties for ML too.

You can see one of my jupyter notebooks that dives deep into this with h3 here: https://drive.google.com/file/d/18jIVEbE_1QbwTbHdMqj0AVqguf2...

cozzyd• 9 months ago

I wonder why healpix never made a footing outside of cosmology. I suppose nobody likes spherical harmonics as much as physicists.

Harder, Better, Faster, Stronger Version of Uber H3 in Rust

Related Stories