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

Making geo joins faster with H3 indexes

floedb.ai

Post reply on HN
Print view View original

31–40 of 70 posts

Re: Making geo joins faster with H3 indexes

#31

Post by urschrei »

TacticalCoder wrote: post #17
jandrewrogers wrote: post #2

There is a lot of literature on join operations using discrete global grid systems (DGGS). H3 is a widely used DGGS optimized for visualization. If joins are a critical performance-sensitive operation, the most important property of a DGGS is congruency . H3 is not congruent it was optimized for visualization, where congruency doesn’t matter, rather than analytical computation. For example, the article talks about de…

> If joins are a critical performance-sensitive operation, the most important property of a DGGS is congruency. Not familiar with geo stuff / DGGS. Is H3 not congruent because hexagons, unlike squares or triangles, do not tile the plane perfectly? I mean: could a system using hexagons ever be congruent?

Hexagons do tile the Euclidean plane perfectly. They are the largest of the three n-gons that do so.

Re: Making geo joins faster with H3 indexes

#32

Post by vouwfietsman »

mgaunard wrote: post #28
cpa wrote: post #27

Earlier quoted context omitted.

The big reason is that H3 is data independant. You put your data in predefined bins and then join on them, whereas kd/r trees depend on the data and building the trees may become prohibitive or very hard (especially in distributed systems).

Indices are meant to depend on the data yes, not exactly rocket science. Updating an R-tree is log(n) just like any other index.

I think the key is in the distributed nature, h3 is effectively a grid so can easily be distributed over nodes. A recursive system is much harder to handle that way. R-trees are great if you are OK with indexing all data on one node, which I think for a global system is a no-go.

This is all speculation, but intuitively your criticism makes sense.

Also, mapping 147k cities to countries should not take 16 workers and 1TB of memory, I think the example in the article is not a realistic workload.

Re: Making geo joins faster with H3 indexes

#33

Post by cyanydeez »

boxed wrote: post #30
galkk wrote: post #26

Ohh, every geo join/spatial thing with picture that consists of those small cells over map is such pet peeve of mine. Facebook marketplace, craigslist, tinder, any app with “proximity search”. No, this city isn’t 4 miles from my city. There is a literal lake between us. It’s 10+ miles. Please, invent something, do precompute, but just avoid naive-ish searches.

Is this related to the article?

Hes just angry hes not a crow.

Re: Making geo joins faster with H3 indexes

#34

Post by nextaccountic »

penteract wrote: post #25
anacoluthe wrote: post #20

Earlier quoted context omitted.

Beware that the parent hexagon does not contain its children...

No idea if they are doing this, but you can use Gosper islands ( https://en.wikipedia.org/wiki/Gosper_curve ) which are close to hexagons, but can be exactly decomposed into 7 smaller copies.

Can Gosper islands tile the sphere though?

Re: Making geo joins faster with H3 indexes

#36

Post by cpa »

mgaunard wrote: post #28
cpa wrote: post #27

Earlier quoted context omitted.

The big reason is that H3 is data independant. You put your data in predefined bins and then join on them, whereas kd/r trees depend on the data and building the trees may become prohibitive or very hard (especially in distributed systems).

Indices are meant to depend on the data yes, not exactly rocket science. Updating an R-tree is log(n) just like any other index.

To add to sibling comment, if you have streaming data you have to update the whole index every time with r/kd trees whereas with H3 you just compute the bin, O(1) instead of O(log n).

Not rocket science but different tradeoffs, that’s what engineering is all about.

Re: Making geo joins faster with H3 indexes

#38

Post by pb060 »

twelvechairs wrote: post #21
feverzsj wrote: post #15

Earlier quoted context omitted.

Yes. And it should be faster. They may forget to create spatial index.

Agree with this. They are re-solving a problem that has been solved better by others before (with R-trees). They may well be using some data storage where spatial indexing is not possible or standard. Geoparquet is a common one now - a great format in many ways but spatial indexing isnt there. Postgres may be out of fashion but still an old fashioned postgis server is the simplest solution sometimes.

Why do you consider Postgres + PostGIS out of fashion? What are people using for spatial data these days?

Re: Making geo joins faster with H3 indexes

#39

Post by cullenking »

freakynit wrote: post #16
cullenking wrote: post #10

We do something similar for some limited geospatial search using elastic search. We make a set of h3 indexes for each of the hundreds of millions of gps recordings on our service, and store them in elastic search. Geospatial queries become full text search queries, where a point is on the line if the set of h3 indexes contains the point. You can do queries on how many cells overlap, which lets you match geospatial tr…

Does this effect writes negatively?

Not any differently than another indexed text field

Re: Making geo joins faster with H3 indexes

#40

Post by cullenking »

jillesvangurp wrote: post #13
cullenking wrote: post #10

We do something similar for some limited geospatial search using elastic search. We make a set of h3 indexes for each of the hundreds of millions of gps recordings on our service, and store them in elastic search. Geospatial queries become full text search queries, where a point is on the line if the set of h3 indexes contains the point. You can do queries on how many cells overlap, which lets you match geospatial tr…

Elastisearch and Opensearch have a built in geo_shape type that is a bit more optimal for queries like this. Before that existed (pre 1.0 actually), I did something similar with geohashes, which are similar to h3 but based on simple string encoded quad trees. I indexed all the street segments in openstreetmap with that (~800 million at the time) and implemented a simple reverse geocoder. Worked shockingly well. The g…

Doesn’t meet all our product requirements unfortunately. We used returned hexes in certain queries, and we also hacked in directionality of line using least significant 12 bits of the hex (didn’t need that level of hex precision), and we are doing direction oriented matching and counting. For simpler use cases it’s definitely a better option. thanks for reminding me and other people reading my comment!
Post reply on HN