Hexagons and Hilbert curves – The headaches of distributed spatial indices
1–10 of 30 posts
Re: Hexagons and Hilbert curves – The headaches of distributed spatial indices
#2I knew about hexagons but not about R-trees and Hilbert curves, and then combining the two. Even though that was an inbound content article, it was at least informative.
Re: Hexagons and Hilbert curves – The headaches of distributed spatial indices
#3I experimented with geospatial Hilbert Curves as a Postgres extension [0] for PostGIS using the S2 [1] spherical geometry library. S2 uses a scale free cell coverage pattern that is numbered using six interlocking space filling Hilbert Curves [2]. This approach is similar to what is used in this article. S2 doesn't use hexagons but a different cell structure but the idea is generally the same.
By having both high level (cell) and low level (cell id) geometries it was a very powerful library which allowed projection from the hilbert space into a Postgres spatial index (spgist) including various trees, like noted in this article. It appears to be still quite active in development.
Re: Hexagons and Hilbert curves – The headaches of distributed spatial indices
#4It would be interesting to know what other solutions exist in this space and why they weren’t chosen.
I know of at least one, GeoMesa, which seems like it could at least provide the building blocks to achieve what they are trying to do.
Re: Hexagons and Hilbert curves – The headaches of distributed spatial indices
#5> a vehicle with a Hilbert Curve position of 0.34 is really close to one with 0.35 and really far from one with 0.89
But points with a large difference in their single curve coordinate can be either far apart or close together. E.g. on this 16 point Hilbert curve
__. .__
__| |__
| __ |
|__| |__|
Re: Hexagons and Hilbert curves – The headaches of distributed spatial indices
#6I experimented with geospatial Hilbert Curves as a Postgres extension [0] for PostGIS using the S2 [1] spherical geometry library. S2 uses a scale free cell coverage pattern that is numbered using six interlocking space filling Hilbert Curves [2]. This approach is similar to what is used in this article. S2 doesn't use hexagons but a different cell structure but the idea is generally the same. By having both high lev…
Ah - I've used S2 in the past. Great work. It scales really well for larger datasets.
Interesting that you mention the use of multiple hilbert curves as well. We also experimented with two Hilbert Curves, rotated by 90 degrees. This helps to get around what we've dubbed the "Hilbert Equator" problem where two objects are quite far on the curve because they are placed close to one of the major fault lines in the fractal (for lack of a better word)
Re: Hexagons and Hilbert curves – The headaches of distributed spatial indices
#7> a vehicle with a Hilbert Curve position of 0.34 is really close to one with 0.35 and really far from one with 0.89 But points with a large difference in their single curve coordinate can be either far apart or close together. E.g. on this 16 point Hilbert curve __. .__ __| |__ | __ | |__| |__| the '.' marked points at 1/16th and 15/16th along the curve are adjacent.
It's an important point. We've ended up using two Hilbert curves, rotated by 90 degrees to tackle this problem. If it is close on either, it is close in 2D space
Re: Hexagons and Hilbert curves – The headaches of distributed spatial indices
#8I've recently implemented a map of the Internet using a similar technique: https://reversedns.space/
In ClickHouse, we have almost every mentioned technique: H3 and S2, geohashes, and indexing by space-filling curves.
Re: Hexagons and Hilbert curves – The headaches of distributed spatial indices
#9I experimented with geospatial Hilbert Curves as a Postgres extension [0] for PostGIS using the S2 [1] spherical geometry library. S2 uses a scale free cell coverage pattern that is numbered using six interlocking space filling Hilbert Curves [2]. This approach is similar to what is used in this article. S2 doesn't use hexagons but a different cell structure but the idea is generally the same. By having both high lev…
Ah - I've used S2 in the past. Great work. It scales really well for larger datasets. Interesting that you mention the use of multiple hilbert curves as well. We also experimented with two Hilbert Curves, rotated by 90 degrees. This helps to get around what we've dubbed the "Hilbert Equator" problem where two objects are quite far on the curve because they are placed close to one of the major fault lines in the fract…
Tackling these boundary problems are the literal "edge cases" in geospatial indexing and they exist everywhere, so this i a good reason for using an existing library as the authors have already solved them.
Hexagons are cool, but they are not necessarily the bestagon for a spherical geometry since you cannot break a hexagon into smaller hexagons, whereas an S2 cell is a "cube" with spherical sides or HEALPix uses a rhombic dodecahedron [0] both of which can be split into smaller divisions of themselves.
Not to discourage you from your experimentation, it's all trade offs and you might find a good one. Good luck!
Re: Hexagons and Hilbert curves – The headaches of distributed spatial indices
#10> a vehicle with a Hilbert Curve position of 0.34 is really close to one with 0.35 and really far from one with 0.89 But points with a large difference in their single curve coordinate can be either far apart or close together. E.g. on this 16 point Hilbert curve __. .__ __| |__ | __ | |__| |__| the '.' marked points at 1/16th and 15/16th along the curve are adjacent.
It's an important point. We've ended up using two Hilbert curves, rotated by 90 degrees to tackle this problem. If it is close on either, it is close in 2D space
Interesting. So one might think that being close together in 2D space corresponds to being close on
BOTH cartesian coordinates / EITHER Hilbert coordinate
And that being far apart in 2D space corresponds to being far apart on
EITHER cartesian coordinate / BOTH Hilbert coordinates
But if we consider the two commas below which are close together in 2D space, we see they are far apart in any rotation of this Hilbert curve?!
__ __ __ __
|__| __| |__ |__|
__ |__ __| __
| |__ __| ;__ __| |
|__ __,__ __ __|
__| |__ __| |__
| __ | | __ |
|__| |__| |__| |__|