H3: Uber’s Hexagonal Hierarchical Spatial Index

https://eng.uber.com/h3/

by johnny313 • 8 years ago

70 13 8 years ago

eng.uber.com

oggyhead• 8 years ago

I wonder how does the math of this stack up against using space-filling curves in Google's S2?

Well other than the fact that it's impossible to tesselate a sphere with hexagons it really depends what you're interested in. Space filling curves would necessarily behave badly in some areas, but could be simpler.

Not sure why they didn't use squares.

scrollaway• 8 years ago

They go into it a bit in the article.

A lot of the reasons seem reminiscent of why hexagons are awesome in video games: https://www.redblobgames.com/grids/hexagons/

splonk• 8 years ago

For comparison, Google uses S2 cells in their maps, which is a tiling of quadrilaterals formed by projecting a cube onto a sphere, with a clever addressing system. Here's a good summary of how those work: http://s2geometry.io/devguide/s2cell_hierarchy.html

I'm not an expert on this, but off the top of my head I can see a couple obvious tradeoffs. I'd love to hear some feedback from someone who's worked with H3 and S2 about the differences.

- S2 cells end up being sort of diamond shaped and all oriented in the same direction after being projected onto a sphere, so their radius varies a lot more than an H3 cell. I wouldn't be surprised if H3 cells are on average more useful for doing local data analysis, since they're closer to a circle. For example, a collection of events are probably clustered together more in an H3 cell than an equivalently sized S2 cell.

- S2 cells tile perfectly - each one is comprised of 4 smaller S2 cells. An H3 cell is approximated by 7 smaller H3 cells.

- Related to above, S2 cell addresses are in some sense "strict" - you can cut off the lowest significant bit to get the address of the parent S2 cell, which will fully contain the child cell. An H3 cell is not necessarily fully contained by its parent cell - judging by the pictures, the center cell is, but the 6 edge cells will overlap a bit. Probably the H3 cells are more annoying to work with for certain cases requiring exact numbers.

- As mentioned in the writeup, H3 needs to include a few pentagons in their tiling. They mention that they're oriented the grid so that the pentagons are over water, so it's probably not a big deal in day to day work.

malandrew2• 8 years ago

That's the jist of it.

h3 cells have the benefit of no boundary conditions as all neighbor edges are the same shape and you can only cross boundaries. With s2, the problem is that four edges are long and then there are four vertices you can cross to get into the adjacent diamonds at each corner. The tradeoff is what you described, s2 cells nest perfectly at different resolutions, but h3 cells are only approximate.

They are both great tools useful in different circumstances. It you have to move between resolutions and don't care about movement between cells, s2 is a better choice. If you care only about one resolution for your work or care about movement/flow between neighboring cells, h3 is a better choice.

s2 I believe also goes down to a smaller resolution (like 1 cm or so) and h3 goes down to like 1 meter. That said, there aren't many use cases that need greater than 1-meter resolution.

notroot• 8 years ago

Why hexagons?

* Neighbor traversal

simplicity of neighbors; triangles 3 classes of neighbors, squares 2 classes of neighbors, hexagons only one class of neighbor!

* Subdivisions

Squares obviously do this pretty well but by alternating cw, cww rotations and allowing not quite perfect coverage they get to shard with different resolutions/hex sizes.

* Distortion

"most important" Basically the use case here is visualizations that maintain basic unit appearance. They even pick the location of their vertices to be over water minimizing land distortions.

source: https://youtu.be/ay2uwtRO3QE?t=11m53s

p.s. as `contravariant` said you can't tessellate a sphere with hexagons so they project onto a icosohedron with pentagons at each of the twelve vertices (positioned over water) https://youtu.be/ay2uwtRO3QE?t=23m00s

sseth• 8 years ago

Is there an equivalent index where the icosahedron vertices are over land and not sea (at least for the most part)? I presume for marine requirements, such an index would reduce distortion over sea?

magicbuzz• 8 years ago

Very interesting. At a glance, the binding libs seem to transform from lat/lon to a hex index. For storage then, conceivably you would just index by hex and transform lat / loc queries to hex on the fly.

Also, it seems there is no map data attribution for Australia. I doubt Uber built their own maps.

malandrew2• 8 years ago

It says at the bottom that for this blog post, they used MapBox. That said, yes, Uber is building their own maps.

FullyFunctional• 8 years ago

This is very interesting. The video does a good job at motivating it. I'm puzzled though that they include some demos on the page (I presume emscripten could compile it) as this figuratively begs for interactive demos.

akskos• 8 years ago

Papa bless uber!

H3: Uber’s Hexagonal Hierarchical Spatial Index

Related Stories