Space-filling curves, constructively | Hacker News Reader

Space-filling curves, constructively

math.andrej.com

113 pointsluu27 comments

An interesting variant of space-filling curves + dimensionality reduction is Geohash (https://en.wikipedia.org/wiki/Geohash, http://geohash.org/) which takes a lon/lat and uses a Z-curve approach to produce a hash such as `u4pruydqqvj` representing the location. This hash value is basically "how far along the space-filling curve is the lon/lat located". You're reducing two dimensions (lon/lat) into one dimension (how far along the space-filling curve).

There's a unique side-effect to Geohashes in that the value (`u4pruydqqvj`) can have it's end "lopped off" (i.e. cut down to `u4pru`) and it still represents a less precise, but generally accurate representation of the original lon/lat in most cases (when the curve isn't near the edge of the 2d map!). This allows you to index locations (lat/lon) using a string ('u4pru') which opens you up to doing b-tree, range queries, etc. in traditional database, with one field.

Just a rad math quirk! I'm not an expert, and it's a very dense book, but if someone really wants to get into this kind of stuff the "Bible" is "Foundations of Multidimensional and Metric Data Structures" by Hanan Samet.

The thing about SFC addressing is that two places near each other always share a prefix, and the closer they are, the longer the common prefix. It's sort of like Gray coding. Quadtree addressing, for example, also has the property that you mentioned (as do, of course, normal lat/long coordinates!) but two adjacent locations may not have similar addresses at all if they happen to straddle a subdivision boundary. (Again, compare to "normal" numbers where, say, |2000-1999| = 1 but there's no common prefix at all!)

The same happens, in fact, for space-filling curves. Sure, in _most_ of the area covered by the curve, closeness of points means closeness on the curve. But in this Hilbert curve:

https://upload.wikimedia.org/wikipedia/commons/7/7c/Hilbert-...

Consider the two points on the curve straddling the middle of the top edge of the square. They are very close together, but their 1D addresses on the curve are very far apart (one close-ish to the beginning, and one close-ish to the end)!

There ain't no free lunch.

Yes, you’re right, of course.

The boustrophedonic version of Rosenberg-Strong function is my favorite because it doesn't have any such jumps and has better locality preserving qualities than most alternatives.

See https://hbfs.wordpress.com/2018/08/07/moeud-deux/.

They're also useful for representing IPv4 space. Tom7 had a nice video where he does this after pinging the whole (IPv4) internet [0]

[0] https://www.youtube.com/embed/JcJSW7Rprio at about 6 minutes, though I recommend the whole thing.

Protomaps (https://protomaps.com/) uses this for their PMTiles HTTP range request lookups too right (https://docs.protomaps.com/pmtiles/)?

> [I]t's a very dense book, but if someone really wants to get into this kind of stuff the "Bible" is "Foundations of Multidimensional and Metric Data Structures" by Hanan Samet.

You're not Kidding! 1022 pages, with a TOC that nests 4 layers deep. In particular, section 2.1.1.2 "Ordering Space" covers space-filling curves, and true to your description it covers every point brought up in the comments so far:

- Peano-Hilbert curve of OP

- Z-order curve mentioned

- "Reverse locality" issues

- Performance considerations of the mapping function

- Even 11 exercises for this section alone!

What a beastly reference. Thank you for sharing.

Geohash just appears to be obfuscated zorder/morton, and being able to truncate the bits etc is just normal SFC stuff.

Space filling curves like Hilbert sound esoteric but they’re actually useful in for high performance database indexing.

DuckDB has a Hilbert index.

https://github.com/rustyconover/duckdb-lindel-extension

It’s not just DuckDB. SQL server and Postgres support Hilbert too.

The big idea is that you can project tuples e.g (lat, long) or just about any other tuple structure (string or floats) in a single integer, ordered in a way that is locality preserving.

Because most queries tend to lookup data close to each other, this can lead to performance gains. Parquet statistics can be built to be locality sensitive (locality defined broadly, not just numbers).

If you index on Hilbert, you can specific compute a max min of the Hilbert range of your predicate and eliminate looking outside that range, speeding up query performance.

"Liquid Clustering" from Databricks also uses Hilbert curves.

I read an entire book on applications of space filling curves, and none of the applications seemed to actually work as advertised (though perhaps they did at the time the book was written, I am skeptical).

All the stuff about database indexing and cache locality seems to have become obsolete with improvements in compilers; the overhead of computing the Hilbert curve indices is just too high. The indexing method that people seem to actually use is the Z-order/Morton order, which just interleaves bits and is mathematically less interesting [1].

[1]: https://en.wikipedia.org/wiki/Z-order_curve

Agreed. There are few practical applications of Space-Filling Curves, but readers may enjoy implementing Z-like and other curves in higher dimensions. Doing it efficiently can be one of those “weekend projects” that takes much longer in practice.

I use hilbert curves and I can assure you they are very useful for performance..

Hilbert encoding does take longer than Z order, but I have a SIMD optimized routine for it so it isn't that bad.

Your comment about compilers doesn't make sense, compilers can't rearrange memory order so that are incapable of making a hilbert or zorder like transform.

I profiled hilbert vs zorder and found hilbert was sufficiently superior to justify the extra overhead, hilbert was about ~22% less work vs zorder.

I wrote an article about it and S2 some time ago as well for those interested: https://blog.christianperone.com/2015/08/googles-s2-geometry...

One problem I’ve encountered is the inverse mapping is not necessarily locality preserving.

Hilbert maps (x,y) -> h such that nearby h correspond to nearby x,y.

But the inverse isn’t true: similar x,y don’t always have similar h.

This is a problem for some applications where we are trying to find dense hot spots cheaply by only looking at h’s, but turns out this doesn’t work out so well.

There's an even stronger result. Every space filling curve's inverse is necessarily not locality preserving.

Should an inverse exist that is continuous then 2D space would be homeomorphic to 1D, but they're obviously different (if you want a proof, consider that removing a point from a line makes it disconnected while in 2D the space remains connected, now note that 'connectedness' is preserved by homeomorphisms).

Yeah for perfect data its a bit soso, but if you don't care about that its great. I'm using some Morton curves for finding neighbours for movement and targeting in a 2d space for a large amount of points (in a compute shader).

One can divide the space into buckets, but for example for targeting at say 10 units the bucket can be 5k long for 1 million entities in a smallish area.

Using Morton which is fast to compute I can usually get a great selection of good candidates within a max set left/right distance and/or under an x,y distance check of some bigger value (as in allow 2d distances to climb to 3x max of our desired distance before breaking).

ahhhh...space-filling curves.

With some of the recent work done with ClickHouse this has been an area I've had to learn about and, tbh, wish I had found this earlier.

Our CTO started using Morton curves for interesting purposes several months ago with initially piqued my interest and started me down the path.

https://reversedns.space/ (a map of the Internet) - Morton curve is used as a visualization tool;

https://adsb.exposed/ (a visualizer of air traffic) - Morton curve is used as a database index;

Our most recent release post dove into the usage of Hilbert curves in context of maintaining spatial locality for weather measurements

https://clickhouse.com/blog/clickhouse-release-24-06#hilbert...

Quite an interesting area of study and optimisation!

I'm imagining a physical world analog: shoving a bicycle chain into a shallow box until you can't shove any more of the chain in.

This reminds of https://binvis.io a binary file visualisation tool that uses space filling curves for visualisation. Discussed here previously https://news.ycombinator.com/item?id=39210436

Has anyone made generative art with SFC?

Closely related is "Opt Art":

* Examples: https://www2.oberlin.edu/math/faculty/bosch/tspart-page.html

* Paper: https://www.tandfonline.com/doi/abs/10.1080/10724117.2006.11... (find it online at the usual places)

* Book: https://press.princeton.edu/books/hardcover/9780691164069/op...

Drawing hilbert curves is especially great at evaluating the performance of online whiteboards!

David Hilbert myst be the least German German name of all time.

How so? There are thousands of Herr and Fräulein Hilbert in Germany. Apparently it's more frequent there than anywhere else.

It sounds British

Reply on news.ycombinator.com