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

21–30 of 70 posts

Re: Making geo joins faster with H3 indexes

#21

Post by twelvechairs »

feverzsj wrote: post #15
febed wrote: post #9

Wouldn’t having a spatial index give you most of the performance gains talked about here without needing H3?

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.

Re: Making geo joins faster with H3 indexes

#22

Post by analytically » 

  At 500 stations:
  - H3: 218µs, 4.7KB, 109 allocs
  - Fallback: 166µs, 1KB, 37 allocs
  - Fallback is 31% faster

  At 1000 stations:
  - H3: 352µs, 4.7KB, 109 allocs
  - Fallback: 312µs, 1KB, 37 allocs
  - Fallback is 13% faster

  At 2000 stations:
  - H3: 664µs, 4.7KB, 109 allocs
  - Fallback: 613µs, 1KB, 37 allocs
  - Fallback is 8% faster

  At 4500 stations (real-world scale):
  - H3: 1.40ms, 4.7KB, 109 allocs
  - Fallback: 1.34ms, 1KB, 37 allocs
  - Fallback is 4% faster

  Conclusion: The gap narrows as station count increases. At 4500 stations they're nearly equivalent. H3 has fixed overhead (~4.7KB/109 allocs for k=2 ring), while fallback scales linearly. The crossover point where H3 wins is likely
  around 10-20K entries.

Re: Making geo joins faster with H3 indexes

#23

Post by srean »

jandrewrogers wrote: post #12
mdasen wrote: post #7

Earlier quoted context omitted.

Is there a congruent DGGS that you would recommend?

None that are well-documented publicly. There are a multitude of DGGS, often obscure, and they are often designed to satisfy specific applications. Most don’t have a public specification but they are easy to design. If the objective is to overfit for high-performance scalable analytics, including congruency, the most capable DGGS designs are constructed by embedding a 2-spheroid in a synthetic Euclidean 3-space. The…

Pointers to the literature please. I don't work in this space but love geometry.

Re: Making geo joins faster with H3 indexes

#25

Post by penteract »

anacoluthe wrote: post #20
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…

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.

Re: Making geo joins faster with H3 indexes

#26

Post by galkk »

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.

Re: Making geo joins faster with H3 indexes

#27

Post by cpa »

mgaunard wrote: post #24

Why doesn't it use k-d trees or r-trees?

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

Re: Making geo joins faster with H3 indexes

#28

Post by mgaunard »

cpa wrote: post #27
mgaunard wrote: post #24

Why doesn't it use k-d trees or r-trees?

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.

Re: Making geo joins faster with H3 indexes

#29

Post by chrisweekly »

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…

Awesome comment, thanks for sharing the details. I love this kind of pragmatic optimization. Also, one dev's "total hack* job" [e.g. yourself, in the past] is another's stroke of genius.

* I'd frame it as "kludge", reserving "hack" for the positive HN sense. :)

Re: Making geo joins faster with H3 indexes

#30

Post by boxed »

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?
Post reply on HN