Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Hexagons and Hilbert curves – The headaches of distributed spatial indices

hivekit.io

Post reply on HN
Print view View original

21–30 of 30 posts

Re: Hexagons and Hilbert curves – The headaches of distributed spatial indices

#21

Post by durkie »

michelpp wrote: post #3

I 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…

any idea why postgis hasn't formally incorporated S2 cell functions? It seems like it'd be right up their alley.

Re: Hexagons and Hilbert curves – The headaches of distributed spatial indices

#22

Post by feverzsj »

The purpose of using space-filling curves is to convert coordinates into 1 dimensional data, thus they can be indexed by ordinary database index, no matter distrusted or not. The problem is it's much slower than a "real" spatial index like R-tree, and the supported queries are rather limited.

On the other hand, spatial data can be easily partitioned, rendering the aforementioned method less useful. Also, I've never seen anyone needed more than a single instance of postgres to index all the spatial data, unless you are dealing with spatial temporal data, which can grow infinitely large. Then again, spatial temporal data can be easily partitioned.

Re: Hexagons and Hilbert curves – The headaches of distributed spatial indices

#23

Post by [deleted] »

feverzsj wrote: post #22

The purpose of using space-filling curves is to convert coordinates into 1 dimensional data, thus they can be indexed by ordinary database index, no matter distrusted or not. The problem is it's much slower than a "real" spatial index like R-tree, and the supported queries are rather limited. On the other hand, spatial data can be easily partitioned, rendering the aforementioned method less useful. Also, I've never s…

[deleted]

Re: Hexagons and Hilbert curves – The headaches of distributed spatial indices

#24

Post by Lichtso »

Here is one of the recent advancements in performing similarity (including nearest neighbor) search on sparse high dimensional data using learned indices: https://arxiv.org/abs/2204.10028

The paper basically deals with the most adverse case but the approach should work in lower dimensions and in data with a non-uniform density distribution as well.

Re: Hexagons and Hilbert curves – The headaches of distributed spatial indices

#25

Post by eh_why_not »

spenczar5 wrote: post #17

Oh boy, this gives me a chance to talk about one of the gems of astronomy software which deserves to be better known: HEALPixel tesselation! HEALPixels stand for 'Hierarchical Equal-Area Iso-latitudinal Pixels'. It is a scheme that was developed to analyze signals that cover the entire sky, but with variable density. Like HTM or Hilbert curves, this can be used to organize spatial data. The tesselation looks kind of…

Gem indeed! Here's its wikipedia page:

https://en.wikipedia.org/wiki/HEALPix

Re: Hexagons and Hilbert curves – The headaches of distributed spatial indices

#30

Post by Nevermark »

michelpp wrote: post #9
max_sendfeld wrote: post #6

Earlier quoted context omitted.

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 r…

> you cannot break a hexagon into smaller hexagons

Actually you can.

1. Think of hexagons as six equilateral triangles sharing a center point.

2. Place one smaller vertically flipped equilateral triangle, in each original triangle.

3. Each original hexagon center point is now the center of a smaller (1/2 linear dimension, 1/4 area) hexagon.

4. New small hexagons replace each of the six original hexagon's edges. Since edges are shared, this is an increase a 3x increase in number of hexagons.

So each new hexagon has 1/4 the area of the original ones (and 1/2 the linear dimensions). This results in 2x the linear dimension resolution, 4x the area resolution.

Grids could also be increased in scale the same way. By retaining a half-sized (in linear terms) square at the center of each original square, and turning each original edge and corner into new squares. With the same 1/2 and 1/4 ratios of linear and area scaling.

Post reply on HN