Portrait of the Hilbert Curve (2010)
1–10 of 16 posts
Re: Portrait of the Hilbert Curve (2010)
#2[deleted]
Re: Portrait of the Hilbert Curve (2010)
#3Here's a nice example of the curve to index transpose in a well established codebase:
https://github.com/SchedMD/slurm/blob/abebf13e9009831376a2d7...
It greatly simplifies the job scheduler to cluster across index instead of some n-dimensional space when calculating placement in the cluster. Consider that each server in the cluster has multiple connections to other servers which all form a sort of hypercube with the Hilbert curve conceptually drawn inside it.
It also shows how simple the transpose operation can be. It's just a few loops and bit shifts.
Re: Portrait of the Hilbert Curve (2010)
#4> For want of a better term, I've called this Zigzag order.
I learned this has a technical name: the zigzag order is called “Boustrophedonic”, after the Ancient Greek tablets where they wrote right-to-left on one line, then left-to-right on the next. https://en.wikipedia.org/wiki/Boustrophedon
It totally depends on the specifics of your application, but a little while ago, I compared Hilbert to both Boustrophedonic and Morton order, and surprisingly, Boustrophedonic was the winner. My application was partitioning a 3d grid into blocks of active voxels where each block could be represented efficiently with only a range (pair) of indices. It’s surprising at first that the zig-zag sometimes has better locality than Hilbert or Morton.
Re: Portrait of the Hilbert Curve (2010)
#5If I remember right, one of the key guarantees of the Hilbert curve is that if you specify a number N=6 say, then given any rectangle of vertices, you can cover it by no more than N sequential sub-curves of the Hilbert curve without “overshooting” by too much. More precisely, there is a constant C (depending only on N) such that your cover will never be no more than C times larger than the original rectangle.
And then as you let N grow, C tends to 1.
I believe the same is true for Morton, though the constant is larger. However, I think it is false for the zig-zag curve, with a counter-example being a long strip orthogonal to the usual direction of the zig-zag.
Re: Portrait of the Hilbert Curve (2010)
#6This is one of those fun reads because it unifies quite a few things that I’ve read about or been interested in recently — Hilbert curves for geospatial indexing in dbs, Gray codes, and fractals! And it’s all fairly intuitive — the 1-bit shift makes sense for space traversal and makes the numbers curve pattern easier to reason about.
Re: Portrait of the Hilbert Curve (2010)
#7Fun article, but the example of Hilbert Curve usefulness with hard drives is quickly aging out. SSDs, which are increasingly prevalent, have more-or-less constant access time. There is no equivalent of the seek time or rotational latency that slows down HHD access when successive reads are on different tracks, at different rotational angles.
Re: Portrait of the Hilbert Curve (2010)
#8Fun article, but the example of Hilbert Curve usefulness with hard drives is quickly aging out. SSDs, which are increasingly prevalent, have more-or-less constant access time. There is no equivalent of the seek time or rotational latency that slows down HHD access when successive reads are on different tracks, at different rotational angles.
It wasn’t even really a thing for HDD. There was a broad consensus that it was inefficient for such purposes by the 1990s. If you had random access at all, you could do better.
The killer app was tape drives.
Re: Portrait of the Hilbert Curve (2010)
#9This reminds me of one of my favourite pieces of art, 'Order from Chaos' (https://allrgb.com/order-from-chaos). You can see it as an attempt to map two dimensional space to three dimensional space in such a way that close points get sent to close points.
Re: Portrait of the Hilbert Curve (2010)
#10Hilbert curves are used in modern data lakehouse storage optimisation techniques, such as Databricks' "liquid clustering" [1]. This can replace the need for more traditional "hive-style" partitioning, in which the data files are partitioned based on a folder structure (e.g. `mydatafiles/YYYY/MM/DD/`).