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

51–60 of 70 posts

Re: Making geo joins faster with H3 indexes

#51

Post by rockinghigh »

urschrei wrote: post #31
TacticalCoder wrote: post #17

Earlier quoted context omitted.

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

That's not true when tiling the Earth though. You need 12 pentagons to close the shape on every zoom level, you can't tile the Earth with just hexagons. That's also why footballs stitch together pentagons and hexagons.

Re: Making geo joins faster with H3 indexes

#52

Post by rockinghigh »

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.

I wouldn't say R-trees solve the problem better. Joining multiple spatial dataset indexed with r-trees is more complex as the nodes are dynamic and data dependent. Neighborhood search is also more complicated because parent nodes overlap.

Re: Making geo joins faster with H3 indexes

#53

Post by rockinghigh »

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.

How do you join two datasets using r-trees? In a business setting, having a static and constant projection is critical. As long as you agree on zoom level, joining two datasets with S2 and H3 is really easy.

Re: Making geo joins faster with H3 indexes

#54

Post by galkk »

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?

Yes. The pictures with those small grids that ignore highways, rivers and mountains is what bothers me

Re: Making geo joins faster with H3 indexes

#55

Post by twelvechairs »

rockinghigh wrote: post #52
twelvechairs wrote: post #21

Earlier quoted context omitted.

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.

I wouldn't say R-trees solve the problem better. Joining multiple spatial dataset indexed with r-trees is more complex as the nodes are dynamic and data dependent. Neighborhood search is also more complicated because parent nodes overlap.

Its a well researched area. My understanding is for most use cases and data like this R trees outperform as bounding box comparisons are fast to run and the bounding boxes tend to be well organised to chunk data efficiently. H3 is a looser area and you may find lots of your points are clustered in a few grids so you end up doing more expensive detailed intersection calculations. Of course it all depends a little on your data, use case and to some extent the parameters chosen for the spatial index. But I think safe to say now based on industry experience that r trees do a very good job 99.9% of the time.

You can of course also use h3 in postgis directly as well as r trees. Its helps significantly for heatmap creation and sometimes for neighbourhood searches.

Re: Making geo joins faster with H3 indexes

#57

Post by ajfriend »

nextaccountic wrote: post #34
penteract wrote: post #25

Earlier quoted context omitted.

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?

Yes! A Gosper Island in H3 is just the outline of all the descendants of a cell at a some resolution. The H3 cells at that resolution tile the sphere, and the Gosper Islands are just non-overlapping subsets of those cells, which means they tile the sphere.

Re: Making geo joins faster with H3 indexes

#59

Post by mgaunard »

rockinghigh wrote: post #53
mgaunard wrote: post #28

Earlier quoted context omitted.

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.

How do you join two datasets using r-trees? In a business setting, having a static and constant projection is critical. As long as you agree on zoom level, joining two datasets with S2 and H3 is really easy.

Spatial indices simply partition your data in N-dimensional space the same way a binary tree does it in 1-dimensional space.

The whole advantage over a static partition is that it will allow you to properly deal with data that is irregularly distributed.

Those data structures can definitely be merged if that's what you're asking.

Re: Making geo joins faster with H3 indexes

#60

Post by touisteur »

twelvechairs wrote: post #50
pb060 wrote: post #38

Earlier quoted context omitted.

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

For use cases like this - long term geospatial people still use postgis as foundational - mainly for its speed at scale and spatial indexing. For the wider tech world - I would say postgres suffers from being "old tech" and somewhat "monolithic". There have been a lot of trends against it (e.g. nosql, fleeing the monolith, data lakes). But also more practically for a lot of businesses geospatial is not their primary…

But what would they use before bringing in postgis ? I'm curious about the alternatives. MongoDB for example doesn't seem to have a geospatial ecosystem, apart from basic 2d features. Clickhouse ?
Post reply on HN