[HN Gopher] Portrait of the Hilbert Curve (2010)
       ___________________________________________________________________
        
       Portrait of the Hilbert Curve (2010)
        
       Author : ofou
       Score  : 35 points
       Date   : 2025-01-18 01:25 UTC (21 hours ago)
        
 (HTM) web link (corte.si)
 (TXT) w3m dump (corte.si)
        
       | fintler wrote:
       | Here'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.
        
       | dahart wrote:
       | > 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.
        
         | yarnover wrote:
         | Right-to-left and left-to-right is how hand-knitting charts are
         | read. But also bottom to top!
        
       | kevinventullo wrote:
       | 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.
       | 
       | 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.
        
       | elijahbenizzy wrote:
       | 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.
        
       | lcuff wrote:
       | 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.
        
         | jandrewrogers wrote:
         | 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.
        
       | OscarCunningham wrote:
       | This 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.
        
         | markisus wrote:
         | I don't understand this. Wouldn't the optimal solution be a
         | constant color over the whole image?
        
       | gdubya wrote:
       | Hilbert 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/`).
       | 
       | 1. https://docs.databricks.com/en/delta/clustering.html
        
       | tidwall wrote:
       | Lately, I've found using hilbert curves with a "spatial btree"
       | [1] beats an rtree for most of my geolocation needs.
       | 
       | 1.
       | https://github.com/tidwall/bgen/blob/main/docs/SPATIAL_BTREE...
        
       | rbanffy wrote:
       | 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.
        
       ___________________________________________________________________
       (page generated 2025-01-18 23:00 UTC)