41–50 of 70 posts
Notably A5, which has the property that each cell covers exactly the same area, even when stretched towards the north and south pole. Useful for certain spatial analysis where you need every cell to have the same size.
Why does H3 use a nonoverlapping set of hexagons? A square grid would make it even simpler and faster to calculate. I am perfectly happy to believe that a hex grid works better for some reason but what is that reason?
- Generate z-values for spatial objects. Points -> a single z-value at the highest resolution of the space. Non-points -> multiple z-values. Each z-value is represented by a single integer, (I use 64 bit z-values, which provide for space resolution of 56 bits.) Each integer represents a 1-d range. E.g. 0x123 would represent 0x123000 through 0x123fff
- Spatial join is basically a merge of these z-values. If you are joining one spatial object with a collection of N spatial objects, the time is logN. If you are joining two collections, then it's more of a linear-time merge.
For more information: PROBE Spatial Data Modeling and Query Processing in an Image Database Application. IEEE Trans. Software Eng. 14(5): 611-629 (1988)
An open source java implementation: https://github.com/geophile/geophile. (The documentation includes a number of corrections to the published algorithm.)
Earlier quoted context omitted.
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…
H3 is optimized for equal-area point aggregates. Congruency does not matter for these aggregates because there is only a single resolution. To your point, in H3 these are implemented as simple scalar counting aggregates -- little computational geometry required. Optimized implementations can generate these aggregates more or less at the speed of memory bandwidth. Ideal for building heat maps!
H3 works reasonably for sharding spatial joins if all of the cell resolutions have the same size and are therefore disjoint. The number of records per cell can be highly variable so this is still suboptimal; adjusting the cell size to get better distribution just moves the suboptimality around. There is also the complexity if polygon data is involved.
The singular importance of congruence as a property is that it enables efficient and uniform sharding of spatial data for distributed indexes, regardless of data distribution or geometry size. The practical benefits follow from efficient and scalable computation over data stored in cells of different size, especially for non-point geometry.
Some DGGS optimized for equal-area point aggregates are congruent, such as HEALPix[0]. However, that congruency comes at high computational cost and unreasonably difficult technical implementation. Not recommended for geospatial use cases.
Congruence has an important challenge that most overlook: geometric relationships on a 2-spheroid can only be approximated on a discrete computer. If you are not careful, quantization to the discrete during computation can effectively create tiny gaps between cells or tiny slivers of overlap. I've seen bugs in the wild from when the rare point lands in one of these non-congruent slivers. Mitigating this can be costly.
This is how we end up with DGGS that embed the 2-spheroid in a synthetic Euclidean 3-space. Quantization issues on the 2-spheroid become trivial in 3-space. People tend to hate two things about these DGGS designs though, neither of which is a technical critique. First, these are not equal area designs like H3; cell size does not indicate anything about the area on the 2-sphere. Since they are efficiently congruent, the resolution can be locally scaled as needed so there are no technical ramifications. It just isn't intuitive like tiling a map or globe. Second, if you do project the cell boundaries onto the 2-sphere and then project that geometry into something like Web Mercator for visualization, it looks like some kind of insane psychedelic hallucination. These cells are designed for analytic processing, not visualization; the data itself is usually WGS84 and can be displayed in exactly the same way you would if you were using PostGIS, the DGGS just doesn't act as a trivial built-in visualization framework.
Taking data stored in a 3-space embedding and converting it to H3-ified data or aggregates on demand is simple, efficient, and highly scalable. I often do things this way even when the data will only ever be visualized in H3 because it scales better.
There are some competing grid systems with similar features and benefits as well. Notably A5, which has the property that each cell covers exactly the same area, even when stretched towards the north and south pole. Useful for certain spatial analysis where you need every cell to have the same size. https://a5geo.org/
Why does H3 use a nonoverlapping set of hexagons? A square grid would make it even simpler and faster to calculate. I am perfectly happy to believe that a hex grid works better for some reason but what is that reason?
There are some competing grid systems with similar features and benefits as well. Notably A5, which has the property that each cell covers exactly the same area, even when stretched towards the north and south pole. Useful for certain spatial analysis where you need every cell to have the same size. https://a5geo.org/
That is a nicely designed DGGS, a lot of attention paid to the details. I hadn't seen it before.
I don't like what scrolling this site does to my browser history.
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.
Why do you consider Postgres + PostGIS out of fashion? What are people using for spatial data these days?
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 focus - they bring other tech stacks so something like postgis can seem like duplication if they already use another database, data storage format or data processing pipeline. Also some of the proliferation of other software and file formats have made some uses cases easier without postgis.
Really Id say the most common path ive seen for people who dont have an explicit geospatial background who are starting to implement it is to avoid postgis until it becomes absolutely clear that they need it.