5 ms·

Space-filling curves, constructively

113 points by luu 2y ago

aguynamedben 2y ago
An interesting variant of space-filling curves + dimensionality reduction is Geohash (https://en.wikipedia.org/wiki/Geohash https://en.wikipedia.org/wiki/Geohash, http://geohash.org/ 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.
- Sharlin 2y ago
  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!)
  - tomsmeding 2y ago
    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-curve_rounded-gradient-animated.gif 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.
    - Sharlin 2y ago
      Yes, you’re right, of course.
  - kittoes 2y ago
    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/ https://hbfs.wordpress.com/2018/08/07/moeud-deux/.
- anitil 2y ago
  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 https://www.youtube.com/embed/JcJSW7Rprio at about 6 minutes, though I recommend the whole thing.
- mbo 2y ago
  Protomaps (https://protomaps.com/ https://protomaps.com/) uses this for their PMTiles HTTP range request lookups too right (https://docs.protomaps.com/pmtiles/ https://docs.protomaps.com/pmtiles/)?
- xelxebar 2y ago
  > [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.
- TinkersW 2y ago
  Geohash just appears to be obfuscated zorder/morton, and being able to truncate the bits etc is just normal SFC stuff.
wenc 2y ago
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 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.
- CurtHagenlocher 2y ago
  "Liquid Clustering" from Databricks also uses Hilbert curves.
perone 2y ago
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-on-the-sphere-cells-and-hilbert-curve/ https://blog.christianperone.com/2015/08/googles-s2-geometry...
JKCalhoun 2y ago
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.
wenc 2y ago
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.
- contravariant 2y ago
  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).
  - animal531 2y ago
    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).
j2kun 2y ago
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 https://en.wikipedia.org/wiki/Z-order_curve
- ashvardanian 2y ago
  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.
- TinkersW 2y ago
  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.
brcmthrowaway 2y ago
Has anyone made generative art with SFC?
- noelwelsh 2y ago
  Closely related is "Opt Art": * Examples: https://www2.oberlin.edu/math/faculty/bosch/tspart-page.html https://www2.oberlin.edu/math/faculty/bosch/tspart-page.html * Paper: https://www.tandfonline.com/doi/abs/10.1080/10724117.2006.11974624 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/opt-art https://press.princeton.edu/books/hardcover/9780691164069/op...
brcmthrowaway 2y ago
David Hilbert myst be the least German German name of all time.
- kgwgk 2y ago
  How so? There are thousands of Herr and Fräulein Hilbert in Germany. Apparently it's more frequent there than anywhere else.
  - brcmthrowaway 2y ago
    It sounds British
zholer 2y ago
Drawing hilbert curves is especially great at evaluating the performance of online whiteboards!
smusamashah 2y ago
This reminds of https://binvis.io 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 https://news.ycombinator.com/item?id=39210436
tylerhannan 2y ago
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/ https://reversedns.space/ (a map of the Internet) - Morton curve is used as a visualization tool; https://adsb.exposed/ 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-curves https://clickhouse.com/blog/clickhouse-release-24-06#hilbert... Quite an interesting area of study and optimisation!

113 points by luu 2y ago

An interesting variant of space-filling curves + dimensionality reduction is Geohash (https://en.wikipedia.org/wiki/Geohash https://en.wikipedia.org/wiki/Geohash, http://geohash.org/ 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.

Sharlin 2y ago
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!)
- tomsmeding 2y ago
  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-curve_rounded-gradient-animated.gif 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.
  - Sharlin 2y ago
    Yes, you’re right, of course.
- kittoes 2y ago
  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/ https://hbfs.wordpress.com/2018/08/07/moeud-deux/.
anitil 2y ago
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 https://www.youtube.com/embed/JcJSW7Rprio at about 6 minutes, though I recommend the whole thing.
mbo 2y ago
Protomaps (https://protomaps.com/ https://protomaps.com/) uses this for their PMTiles HTTP range request lookups too right (https://docs.protomaps.com/pmtiles/ https://docs.protomaps.com/pmtiles/)?
xelxebar 2y ago
> [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.
TinkersW 2y ago
Geohash just appears to be obfuscated zorder/morton, and being able to truncate the bits etc is just normal SFC stuff.

wenc 2y ago

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 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.

CurtHagenlocher 2y ago
"Liquid Clustering" from Databricks also uses Hilbert curves.

perone 2y ago

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-on-the-sphere-cells-and-hilbert-curve/ https://blog.christianperone.com/2015/08/googles-s2-geometry...

JKCalhoun 2y ago

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.

wenc 2y ago

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.

contravariant 2y ago
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).
- animal531 2y ago
  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).

j2kun 2y ago

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 https://en.wikipedia.org/wiki/Z-order_curve

ashvardanian 2y ago
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.
TinkersW 2y ago
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.

brcmthrowaway 2y ago

Has anyone made generative art with SFC?

noelwelsh 2y ago
Closely related is "Opt Art": * Examples: https://www2.oberlin.edu/math/faculty/bosch/tspart-page.html https://www2.oberlin.edu/math/faculty/bosch/tspart-page.html * Paper: https://www.tandfonline.com/doi/abs/10.1080/10724117.2006.11974624 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/opt-art https://press.princeton.edu/books/hardcover/9780691164069/op...

brcmthrowaway 2y ago

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

kgwgk 2y ago
How so? There are thousands of Herr and Fräulein Hilbert in Germany. Apparently it's more frequent there than anywhere else.
- brcmthrowaway 2y ago
  It sounds British

zholer 2y ago

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

smusamashah 2y ago

This reminds of https://binvis.io 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 https://news.ycombinator.com/item?id=39210436

tylerhannan 2y ago

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/ https://reversedns.space/ (a map of the Internet) - Morton curve is used as a visualization tool; https://adsb.exposed/ 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-curves https://clickhouse.com/blog/clickhouse-release-24-06#hilbert... Quite an interesting area of study and optimisation!