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

11–20 of 70 posts

Re: Making geo joins faster with H3 indexes

#11

Post by ajfriend »

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…

Very cool! And the prefix queries you mention are what I was trying to get at in another comment, but you explained it better :)

Re: Making geo joins faster with H3 indexes

#12

Post by jandrewrogers »

mdasen wrote: post #7
jandrewrogers wrote: post #5

Earlier quoted context omitted.

Yes, S2 is a congruent DGGS. Unfortunately, it kind of straddles the analytics and visualization property space, being not particularly good at either. It made some design choices, like being projective, that limit its generality as an analytic DGGS. In fairness, its objectives were considerably more limited when it was created. The potential use cases have changed since then.

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 metric for the synthetic 3-space is usually defined to be both binary and as a whole multiple of meters. The main objection is that it is not an “equal area” DGGS, so not good for a pretty graphic, but it is trivially projected into it as needed so it doesn’t matter that much. The main knobs you might care about is the spatial resolution and how far the 3-space extends e.g. it is common to include low-earth orbit in the addressable space.

I was working with a few countries on standardizing one such design but we never got it over the line. There is quite a bit of literature on this, but few people read it and most of it is focused on visualization rather than analytic applications.

Re: Making geo joins faster with H3 indexes

#13

Post by jillesvangurp »

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 geo_shape type uses a bkd tree in binary format. It's heavily optimized for this type of intersects/overlaps queries at scale. Basically does the same thing but using a lot less disk space and memory. It's similar to what you would find in proper GIS databases. Elasticsearch/opensearch also support h3 and geohash grid aggregations on top of geo_shape or geo_point types.

I'm guessing the author is using something like postgresql which of course has similar geospatial indexing support via post gis.

Re: Making geo joins faster with H3 indexes

#14

Post by jandrewrogers »

ajfriend wrote: post #8
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…

I agree that the lack of congruency in H3 hexagons can cause weird overlaps and gaps if you plot mixed resolutions naively, but there are some workarounds that work pretty well in practice. For example, if you have mixed resolutions from compacted H3 cells but a single “logical” target resolution underneath, you can plot the coarser cells not with their native geometry, but using the outline of their children. When y…

In a highly optimized system, spatial joins are often bandwidth bound.

Congruency allows for much more efficient join schedules and maximizes selectivity. This minimizes data motion, which is particularly important as data becomes large. Congruent shards also tend to be more computationally efficient generally, which does add up.

The other important aspect not raised here, is that congruent DGGS have much more scalable performance when using them to build online indexes during ingestion. This follows from them being much more concurrency friendly.

Re: Making geo joins faster with H3 indexes

#16

Post by freakynit »

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?

Re: Making geo joins faster with H3 indexes

#17

Post by TacticalCoder »

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?

Re: Making geo joins faster with H3 indexes

#18

Post by avereveard »

nice writeup, terrible website garbling the page history

I wonder how it compare with geohashing, I know it is not as efficient in term of partitioning and query end up weird since you need to manage decoding neighbor cells but finding all element of a cell is a "starts with" query which allow to put data effectively on most nosql databases with some sort of text sorting

Re: Making geo joins faster with H3 indexes

#19

Post by ajfriend »

jandrewrogers wrote: post #14
ajfriend wrote: post #8

Earlier quoted context omitted.

I agree that the lack of congruency in H3 hexagons can cause weird overlaps and gaps if you plot mixed resolutions naively, but there are some workarounds that work pretty well in practice. For example, if you have mixed resolutions from compacted H3 cells but a single “logical” target resolution underneath, you can plot the coarser cells not with their native geometry, but using the outline of their children. When y…

In a highly optimized system, spatial joins are often bandwidth bound. Congruency allows for much more efficient join schedules and maximizes selectivity. This minimizes data motion, which is particularly important as data becomes large. Congruent shards also tend to be more computationally efficient generally, which does add up. The other important aspect not raised here, is that congruent DGGS have much more scalab…

I appreciate the reply! So, I might be wrong here, but I think we may be talking about two different layers. I’m also not very familiar with the literature, so I’d be interested if you could point me to relevant work or explain where my understanding is off.

To me, the big selling point of H3 is that once you’re "in the H3 system", many operations don’t need to worry about geometry at all. Everything is discrete. H3 cells are nodes in a tree with prefixes that can be exploited, and geometry or congruency never really enter the picture at this layer.

Where geometry and congruency do come in is when you translate continuous data (points, polygons, and so on) into H3. In that scenario, I can totally see congruency being a useful property for speed, and that H3 is probably slower than systems that are optimized for that conversion step.

However, in most applications I’ve seen, the continuous-to-H3 conversion happens upstream, or at least isn’t the bottleneck. The primary task is usually operating on already "hexagonified" data, such as joins or other set operations on discrete cell IDs.

Am I understanding the bottleneck correctly?

Re: Making geo joins faster with H3 indexes

#20

Post by anacoluthe »

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