Portrait of the Hilbert Curve (2010)

&gt; For want of a better term, I&#x27;ve called this Zigzag order.<p>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. <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Boustrophedon" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Boustrophedon</a><p>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.

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

Hilbert curves are used in modern data lakehouse storage optimisation techniques, such as Databricks&#x27; &quot;liquid clustering&quot; [1]. This can replace the need for more traditional &quot;hive-style&quot; partitioning, in which the data files are partitioned based on a folder structure (e.g. `mydatafiles&#x2F;YYYY&#x2F;MM&#x2F;DD&#x2F;`).<p>1. <a href="https:&#x2F;&#x2F;docs.databricks.com&#x2F;en&#x2F;delta&#x2F;clustering.html" rel="nofollow">https:&#x2F;&#x2F;docs.databricks.com&#x2F;en&#x2F;delta&#x2F;clustering.html</a>

This reminds me of one of my favourite pieces of art, &#x27;Order from Chaos&#x27; (<a href="https:&#x2F;&#x2F;allrgb.com&#x2F;order-from-chaos" rel="nofollow">https:&#x2F;&#x2F;allrgb.com&#x2F;order-from-chaos</a>). 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.

Lately, I’ve found using hilbert curves with a &quot;spatial btree&quot; [1] beats an rtree for most of my geolocation needs.<p>1. <a href="https:&#x2F;&#x2F;github.com&#x2F;tidwall&#x2F;bgen&#x2F;blob&#x2F;main&#x2F;docs&#x2F;SPATIAL_BTREE.md">https:&#x2F;&#x2F;github.com&#x2F;tidwall&#x2F;bgen&#x2F;blob&#x2F;main&#x2F;docs&#x2F;SPATIAL_BTREE...</a>

Here&#x27;s a nice example of the curve to index transpose in a well established codebase:<p><a href="https:&#x2F;&#x2F;github.com&#x2F;SchedMD&#x2F;slurm&#x2F;blob&#x2F;abebf13e9009831376a2d7514e38ed83be86f0ac&#x2F;src&#x2F;plugins&#x2F;topology&#x2F;3d_torus&#x2F;hilbert.c">https:&#x2F;&#x2F;github.com&#x2F;SchedMD&#x2F;slurm&#x2F;blob&#x2F;abebf13e9009831376a2d7...</a><p>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.<p>It also shows how simple the transpose operation can be. It&#x27;s just a few loops and bit shifts.

If 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.<p>And then as you let N grow, C tends to 1.<p>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.

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

3b1b video on Hilbert curve: <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=3s7h2MHQtxc" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=3s7h2MHQtxc</a>

I often think about the worst city in the universe: it has no traffic lights (apart from pedestrian ones) and no crossings, and it has one single street called Hilbert street.