Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

eng.uber.com

Post reply on HN
Print view View original

61–70 of 76 posts

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#61

Post by alluro2 »

ant6n wrote: post #44
na85 wrote: post #41

Earlier quoted context omitted.

That link is a great example of why I stopped using stack exchange. The OP asked a question about tiling spheres with pentagons and the third response is basically "you can tile a sphere if it's not a sphere." I had analogous experiences every time I asked a question there. One would ask a very clear question like, say, "how do I print to stdout in C?" And the first or second answer you get is inevitably about taking…

Maybe people just like to hijack threads and change the topic to what they like to talk about.

Ouch :) Thanks for that, nice one :)

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#62

Post by alanbernstein »

jacobolus wrote: post #35
jpab wrote: post #34

Earlier quoted context omitted.

You can't make a sphere entirely out of hexagons; the math doesn't work [1]. In the article they note that they include 12 pentagons too, to solve this problem. Neatly, they arrange to have all the pentagons in areas of water where they presumably won't have to analyse traffic patterns for a while. (I mention it mostly because I think it's an interesting little mathematical factoid.) [1] https://math.stackexchange.co…

One thing you can do though is tile an octahedron by just hexagons. At each of the 6 corners you end up with 2 hexagons which border each-other along 2 edges (instead of the usual 1). If you blow this octahedron up into a sphere those hexagons appear to be pentagons, because two of their edges are colinear (i.e. the same great-circle arc). This can be nicer in some cases: the edge case your hexagon-grid algorithms ha…

Would you care to explain this? When you mention tiling an octahedron with hexagons, the first thing I imagine is a truncated octahedron, which is composed of hexagons and squares.

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#63

Post by malandrew »

phkahler wrote: post #47
seanhandley wrote: post #26

Earlier quoted context omitted.

You get more aesthetic visuals from H3. S2 cells distort quite heavily depending on which part of the globe you're mapping.

I think this is the real answer. I've like hex tiles for a long time, but they don't nest properly like squares in a quadtree. I think someone at Uber decided to "make it work" because it looks cool. They traded one set of problems for another, and I think from a technical point of view they made a poor choice.

> I think from a technical point of view they made a poor choice.

based on what criteria? H3 vs S2 is a tradeoff.

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#64

Post by phkahler »

malandrew wrote: post #63
phkahler wrote: post #47

Earlier quoted context omitted.

I think this is the real answer. I've like hex tiles for a long time, but they don't nest properly like squares in a quadtree. I think someone at Uber decided to "make it work" because it looks cool. They traded one set of problems for another, and I think from a technical point of view they made a poor choice.

> I think from a technical point of view they made a poor choice. based on what criteria? H3 vs S2 is a tradeoff.

>> based on what criteria?

Well for one, the fact that they don't nest properly. They mention that you can get the address of the parent hexagon by truncating that of the current one. The problem is that doesn't actually work all the way up because certain tiles on the border will flip back and forth in strange ways. They had to do something to deal with this, just like the would have had to do something else with squares having two kinds ot neighbors. The squares issues are more obvious though and the code to deal with it will probably be very localized.

I mean, don't make a nested spatial index with spacial regions that don't actually nest. The structure fails at its primary claim.

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#65

Post by jacobolus »

alanbernstein wrote: post #62
jacobolus wrote: post #35

Earlier quoted context omitted.

One thing you can do though is tile an octahedron by just hexagons. At each of the 6 corners you end up with 2 hexagons which border each-other along 2 edges (instead of the usual 1). If you blow this octahedron up into a sphere those hexagons appear to be pentagons, because two of their edges are colinear (i.e. the same great-circle arc). This can be nicer in some cases: the edge case your hexagon-grid algorithms ha…

Would you care to explain this? When you mention tiling an octahedron with hexagons, the first thing I imagine is a truncated octahedron, which is composed of hexagons and squares.

You can start with 4 hexagons, each one covering an octant and a third of the neighboring octants.

Or another way to say this: if you start with 4 hexagons, with each glued together with each other along two adjacent edges, and you add the appropriate folds, you can make an octahedron.

Then you can subdivide each of those starting hexagons into n hexagons for any of these numbers, https://oeis.org/A003136 (power-of-4 sizes may be the most convenient among these, so that the overall grid has 2^n by 2^n size)

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#66

Post by mtrovo »

twic wrote: post #46
HelloNurse wrote: post #43

Earlier quoted context omitted.

Subdividing tiles can be more important than everything else: knowing in which tile a point lies is a fundamental operation for a spatial indexing system and it has to be very easy and efficient.

It's also vital for correct aggregation: if you sum up some quantity over all the subdivisions of some area, you really want that sum to be equal to the quantity in that area. With this hexagonal pseudo-subdivision, it isn't.

I think as long as you're adding the leaves on the same resolution level it should be fine. the problem is when your storing objects in different levels as it would be possible on a KDB tree.

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#68

Post by malandrew »

phkahler wrote: post #64
malandrew wrote: post #63

Earlier quoted context omitted.

> I think from a technical point of view they made a poor choice. based on what criteria? H3 vs S2 is a tradeoff.

>> based on what criteria? Well for one, the fact that they don't nest properly. They mention that you can get the address of the parent hexagon by truncating that of the current one. The problem is that doesn't actually work all the way up because certain tiles on the border will flip back and forth in strange ways. They had to do something to deal with this, just like the would have had to do something else with sq…

Maybe nesting wasn't considered important for the use case?

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#69

Post by AlchemistCamp »

mtrovo wrote: post #38
jillesvangurp wrote: post #29

I did some indexing using elasticsearch and some home grown stuff based on geohashes about seven years ago. At the time Elasticsearch was just adding support for geoshape indexing as well. Initially this was also based on geohashes. Later they added proper quad tree support (instead of indexing the geohash as a term), and recently they revamped the implementation using BKD trees. The current implementation is way fas…

They go into some detail on this talk https://youtu.be/ay2uwtRO3QE?t=712 . What I get from their explanation is that hexagon is a better shape for map grids because they are the most complex shape that can tesselate (the other two are triangles and squares). As they are more close to a circle, distances within a cell are more stable, also computing the distance from a cell center to its neighbours is stable in hexago…

The Techzing podcast talked about the origin of this several years ago, back when one of the hosts had a critical role in its creation. Good stuff.

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#70

Post by sroussey »

jillesvangurp wrote: post #58
sroussey wrote: post #57

Earlier quoted context omitted.

geohashes are cool, and lopping off a letter reduces precision. But if you look at have they overlay London, you get quite a split higher up and two next to each other don’t look like they are and so I can see where the number of terms would get big. The new ElasticSearch implementation is now the default and I think they are deprecating the prefix versions like geohash. Too bad their stuff is not embeddable into an…

This is all part of Lucene and not specific to Elasticsearch as far as I understand. Update with link: https://lucene.apache.org/core/7_1_0/core/org/apache/lucene/...

Nice! Thanks for the link. I was hoping more for an embeddable lib for mobile apps
Post reply on HN