The Fantastic thing about House-Filling Curves: Understanding the Hilbert Curve

0. Introduction

(SFC) are fascinating mathematical constructs with many sensible purposes in knowledge science and knowledge engineering. Whereas they might sound summary, they’re typically hiding in plain sight—behind phrases like Z-ordering or Liquid Clustering (used, for instance, in platforms like Databricks). For those who’ve labored with large-scale knowledge platforms, likelihood is you’ve already used SFCs with out realizing it.

Regardless of its relevance in fashionable programs, info on this matter is usually fragmented, making it tough to bridge principle and observe. This text goals to bridge that hole, whereas specializing in the Hilbert curve.

My objective is to supply a condensed and accessible overview of SFCs: beginning with their mathematical origins, transferring by means of sensible implementation methods, and ending with real-world purposes in knowledge processing and optimization. It’s not the plan to exchange present sources however relatively reference them for extra detailed info. Additional sources for terminology and particulars might be referenced all through the textual content.

You would possibly ask: What’s so fascinating about curves? In any case, an everyday curve is straightforward to grasp and doubtless not the primary matter I might decide up a e book about. However SFCs are totally different. They traverse each level in a steady area, have fractal properties, and produce visually placing patterns when plotted in 2D or 3D-especially in decrease iterations. So, allow us to take a more in-depth look.

(If you wish to begin with visualization and animations instantly, take a look at my GitHub repository)

1. Historical past and Concept of House-Filling Curves

The examine of SFCs dates again to the nineteenth century, when Georg Cantor made a groundbreaking discovery. He confirmed that ”two finite-dimensional easy manifolds have the identical cardinality, no matter their dimensions.” [1]

For instance this, contemplate the unit interval [0, 1] ⊂ R and the unit sq. [0, 1]² ⊂ R². Intuitively, one would possibly anticipate the sq. to have a bigger cardinality than the road section. Nevertheless, Cantor demonstrated that each units even have the identical cardinality, utilizing his technique of interleaving decimals.

This outcome implies the existence of a bijection between the interval and the sq., which means there’s a one-to-one correspondence between their parts. Following Cantor’s discovery, a pure query arose: Is there additionally a steady bijection between these units? Eugen Netto answered this query within the destructive.

On this context, continuity may be interpreted geometrically: a steady mapping would permit one to “draw” the picture in 2D or 3D with out lifting the pen – forming a curve. This perception laid the groundwork for the later growth of SFCs — curves that, whereas steady, can come arbitrarily near filling a higher-dimensional
area.

2. Peano Curve: The Discovery of House-Filling Curves

After Netto’s sobering discovery, the query arose as as to if such a mapping, if not bijective, may very well be surjective. The primary one who was in a position to outline such a mapping was G. Peano, establishing the so-called Peano curve.

The Peano curve is outlined recursively. Its area is the unit interval [0, 1] ⊂ R, and its picture lies within the unit sq. [0, 1]² ⊂ R². By repeatedly subdividing the interval [0, 1] into thirds, and correspondingly partitioning the sq. in R² right into a 3 × 3 grid, the development converges to the precise space-filling curve because the variety of iterations tends to infinity. [1]

Thus, the graphs of the Peano curve at finite iterations (Determine 1) don’t symbolize the “ultimate” SFC. Solely within the restrict, because the variety of iterations of this recursive mapping approaches infinity, does the precise SFC emerge, which traverses each level in [0, 1]². Visually, on this restrict, the curve would basically seem as a stuffed sq. spanning from (0, 0) to (1, 1)

This commentary raises an initially counterintuitive query: By definition, a curve is one-dimensional. Whereas it may be embedded in a higher-dimensional area (n > 1), its intrinsic parameter area stays one-dimensional. But, if the Peano curve passes by means of each level in [0, 1]² and thus utterly fills the airplane, can its picture nonetheless be considered one-dimensional? The reply is not any: the picture of the Peano curve has Hausdorff dimension 2. One other attribute of an SFC is that its picture has constructive Jordan content material (Peano-Jordan Measure). These information could appear shocking, nevertheless it aligns with the properties of fractals: many such units have Hausdorff dimensions larger than 1, and a few even non-integer Hausdorff dimensions.

3. The Hilbert Curve – Common until in the present day!

Though Peano was the primary to assemble an SFC, a way more well-known instance is the Hilbert curve, outlined by David Hilbert in 1891. Its definition is barely less complicated and begins with a 2 x 2 grid. Just like the Peano curve, the mapping of the Hilbert curve recursively subdivides every interval in [0, 1] and every sq. in [0, 1]² into 4 smaller intervals/squares at every step. As with the Peano curve, the Hilbert curve converges to a real SFC within the restrict because the variety of iterations approaches infinity.

For the needs of this text, we are going to concentrate on the Hilbert curve, as its properties make it a useful device in fashionable knowledge platforms.

3.1 Formal Definition of the Hilbert Curve

Beginning with the interval [0,1] because the area of the Hilbert curve, every recursion step divides the present interval into 4 equal subintervals: a is the left endpoint and h the interval width, the subintervals are:

For any chosen level in [0, 1], precisely one in every of these subintervals accommodates the purpose. This interval can then be subdivided once more utilizing the identical rule, producing a finer interval that also accommodates the purpose. This course of may be continued infinitely, yielding an arbitrarily exact location of the purpose alongside the curve. The identical recursive subdivision is utilized in [0, 1]² in parallel, splitting every sq. into 4 smaller squares:

Common properties:

• Surjective: From its recursive definition it follows that the Hilbert curve is surjective: each level in [0, 1]² is roofed within the restrict. The nested intervals are compact, and adjoining intervals share boundary factors (e.g., a + h/4 is each the proper endpoint of the primary subinterval and the left endpoint of the second).
  Thus your complete sq. is stuffed. The mapping, nonetheless, is just not injective—makes an attempt to implement bijectivity (e.g., by opening intervals) break continuity.
• Steady: This property is evident from visible representations: the curve may be drawn with out lifting the pen. Formally, it may be established by displaying that the Hilbert curve arises because the uniform restrict of steady capabilities, and uniform convergence preserves continuity.
• Nowhere differentiable: By taking a look at graphs of the Hilbert Curve it’s apparent that this curve is just not
  differentiable. A proof for this property was given by H.Sagan utilizing the distinction quotient.
• Locality preserving: In distinction to less complicated mappings such because the Z-order curve, the Hilbert curve tends to protect locality: factors which are shut within the one-dimensional parameter are sometimes mapped to close by. This side is essential for purposes in huge knowledge platforms.
• Optimistic Jordan Content material: Within the restrict of infinitely many iterations, the picture of the Hilbert curve has constructive Jordan measure, which means that it occupies a nonzero space of the airplane. (Peano-Jordan Measure)
• Hausdorff Dimension of two: Correspondingly, the Hilbert curve doesn’t behave like a normal one-dimensional line, however has Hausdorff dimension 2, reflecting that it totally fills the unit sq..

Although, early definitions of the Hilbert Curve are approached in 2D, larger dimensions are additionally possible. The algorithm we talk about within the subsequent part works in any finite dimension.

4 Computing the Hilbert Curve With Skilling’s Algorithm

The definition of the Hilbert Curve was given in a geometrical method with out an algebraic definition for computing coordinates on a given grid, for a given level in I. It took nearly 100 years after Hilbert launched his concept earlier than mathematicians considered methods the way to compute factors for a given Hilbert index. Who might blame them? In any case, for a very long time there have been no computer systems that might draw curves with lots of or 1000’s of factors. Whereas researching I found a number of methods the way to compute the Hilbert curve – from complicated numbers to L-Methods. Whereas some are tremendous in depth, others protect the iterative strategy for computing single factors of the curve. What I used to be searching for was one thing easy:

• A perform that takes a Hilbert index (i.e. any numbers like 1,2,3 in 1D area) and returns its coordinates. You possibly can contemplate the Hilbert index because the variety of the interval from left to proper for Hilbert Curve of order < infinity.
• A perform that does the inverse, mapping a coordinate again to its Hilbert index.

Whereas looking the web for potential implementations I got here throughout a Github repository of Princeton University implementing the algorithm of John Skilling, that was printed in a paper from 2004 known as Programming the Hilbert Curve. Sadly, this paper is just not freely obtainable for the general public, so I made a decision to investigate the code from the Princeton repository.

4.1 Skilling’s Algorithm – Overview

Skilling noticed that mapping Hilbert indices to coordinates may be expressed elegantly when it comes to binary operations. For instance, contemplate the indices 0, 1, 2, 3 in a single dimension. These correspond to the coordinates (0, 0), (1, 0), (1, 1), (0, 1) in a 2 × 2 grid. Right here, the values 0, 1, 2, 3 not symbolize fractional factors within the unit interval (like 1/3), however as a substitute discrete interval numbers. With a 2 × 2 grid, there are precisely 4 intervals in [0, 1] and 4 corresponding squares in [0, 1]². Skilling’s algorithm generalizes this concept. It computes the mapping from a Hilbert index to its corresponding coordinate (and vice versa) in any finite dimension utilizing binary transformations. The important steps are:

1. Convert the Hilbert index from decimal to binary.
2. Rework the binary quantity into its Grey code illustration.
3. Disentangle the Grey code right into a coordinate construction.
4. Apply rotations and reflections utilizing XOR operations.
5. Convert the binary coordinates again to decimal

4.2 Binary Illustration

To know why binaries are significantly better fitted to computing factors of the Hilbert Curve from Hilbert Indices and vice versa the next examples would possibly assist (we talk about all the things in 2D, however the algorithm works in any dimensional area):
The Hilbert Curve is outlined on a 2×2, 4×4, 8×8, 16×16…and so forth. grid. (Bear in mind the definition above and its recursive strategy).
By wanting on the numbers, one would possibly uncover that the variety of intervals develop with 2ⁿ, the place n is the order of the curve. This matches completely with binary encoding: for an n-th order curve, we
want precisely n bits per axis to explain the grid.
Take the 4 × 4 grid (second order) for example. Two bits per axis are enough:

1. The primary bit identifies the most important quadrant (decrease left, higher left, decrease proper, or higher proper).
2. The second bit specifies the place inside that quadrant.

For example, Hilbert index 2 has the binary kind 0010. Decoding this:

• 00 selects the lower-left quadrant.
• 10 selects the upper-right subquadrant inside it.

Nevertheless, if we proceed this course of for indices larger than 3, we encounter a problem: the orientation of the curve adjustments from one quadrant to the subsequent. Accurately dealing with these rotations and reflections is precisely the place Grey code and XOR operations (as in Skilling’s algorithm) grow to be important.

4.3 Grey Code Illustration

The following step in Skilling’s algorithm is a change from binary to Grey code. The important thing distinction is that in Gray code, consecutive numbers differ in just one bit. This property is essential: It ensures that the curve strikes easily from one quadrant to the subsequent (though the orientation of the curve in every quadrant continues to be not appropriate)

By wanting on the binary numbers and the orientation of the totally different sections of the curve, we will see that the curve continues to be not appropriate, however the finish of every quadrant now connects to the start of the subsequent.

4.4 Disentanglement of the Bits

The actual “magic” of Skilling’s technique begins with a reordering of the Grey-coded bits—a step known as disentanglement. In our 4 × 4 instance, we initially interpreted the 4 bits as (bitx₁, bity₁, bitx₂, bity₂) the place the primary pair encodes the most important quadrant and the second pair the sub-quadrant. Nevertheless, for coordinate computation we’d like a construction of the shape (bitx₁, bitx₂, bity₁, bity₂) so that every one x-bits and y-bits can later be mixed into the respective decimal coordinates (x, y). This step is named disentanglement of the bits.

4.5 Corrective Transformations

After disentangling the bits, the ultimate step of Skilling’s algorithm is to rotate and mirror the subcurves inside every quadrant in order that they join seamlessly into the Hilbert curve of order n.

Determine 6 illustrates this course of for the 4 × 4 case. The desk on the left exhibits how Grey-coded coordinates are transformed into commonplace binary numbers by making use of easy transformations: swaps and bit-flips.

The diagram on the proper visualizes the impact: the higher quadrants are rotated by 180◦, the decrease quadrants are mirrored alongside the diagonal, and in some circumstances (e.g. the yellow quadrant) no transformation is required in any respect.

The important thing perception is that after these corrective transformations, the coordinates are as soon as once more in commonplace binary kind. Which means that the output of Skilling’s algorithm may be transformed on to decimal coordinates within the format (x, y), with out additional adjustment

Skilling algorithm key transformations: Enter: Grey code formatted (bitx₁, bitx₂, bity₁, bity₂) In python the format can be: [-1, ndims, nbits]. Instance: The quantity 4 can be represented as the next record/np-array: [[01],[10]]. For the x-Dimension 1 is the least vital bit (LSB), and 0 probably the most vital bit
(MSB).

1. Loop from probably the most vital bit (MSB) to least vital bit (LSB)
2. Innerloop from highest dimension (y in 2D) to lowest dimension
3. : Have a look at the present bit. If 1: Flip each decrease bit in dimension 0 (often x) If 0: Swap values between
   decrease bits in present dimension and dimension 0 (in the event that they differ).

Step 3 may be simply computed with numpy utilizing XOR operations. The entire technique of flipping and swapping bits in every iteration is visualized within the following animations.

If you wish to analyze the algorithm in additional element or just generate your individual animations in 2D or 3D, take a look at my GitHub Repository

5 Functions of House Filling Curves

After discussing theoretical points and implementation particulars of the Hilbert Curve, the query arises, the place it may be utilized. Through the implementation we noticed the way to remodel Hilbert Indices into coordinates. For the next utility, the inverse of this course of is extra fascinating.

One useful side of the Hilbert Curve is that it maps a 1D ordered set (i.e. 1,2,3…) to coordinates in an n-dimensional area. It offers an order to the factors it traverses and it might probably dwell in vector areas of arbitrary measurement. Thus, the Hilbert Curve is used for knowledge partitioning and cluster, picture compression and likewise for constructing options in machine studying, when coping with spatial knowledge.

5.1 Information Partitioning/Clustering utilizing SFCs

Probably the most outstanding purposes of SFCs is knowledge partitioning. For instance, in Databricks, Z-ordering relies on the Z-curve, whereas liquid clustering depends on the Hilbert Curve. The reason being easy:
the Hilbert curve preserves locality higher than the Z-curve, which is essential when indexing and partitioning multidimensional knowledge. In determine 9 you’ll be able to see how some exemplary knowledge factors are mapped to factors of the Hilbert curve, by assigning every level to at least one partition given by the curve.

When a question is utilized to the info (e.g. SELECT * FROM desk WHERE x in (1,2) and y in (2,3), all factors on this vary ((1,2), (1,3), (2,2), (2,3)) are transformed to Hilbert indices and the system can instantly retrieve all matching entries. The important thing benefit is that this mapping allows quick and versatile knowledge retrieval. Not like conventional indexing, the Hilbert-based partitioning adapts naturally to updates or progress within the dataset — with out requiring your complete index to be recomputed.

5.2 Information Indexing: Hilbert Curve vs. Z-Curve

To spotlight the sensible benefits of the Hilbert curve, I in contrast its efficiency with the Z-curve on a set of artificial vary queries.

For the experiment, I generated 100 random vary queries of mounted measurement. For every question, I computed the Hilbert and Z-curve indices and counted the variety of clusters, whereas a cluster is a set of consecutive indices. For instance, if the question returned the indices [1,2,3,5,6,8,9], this may kind three clusters: [1,2,3], [5,6], and [8,9].
If the info is saved in index order, clusters correspond to sequential reads, whereas gaps between clusters suggest expensive jumps to new storage addresses.

To quantify efficiency, I used two metrics:

1. Cluster depend: Fewer clusters suggest much less fragmentation and fewer storage jumps.
2. Intra-cluster unfold: The typical variety of indices per cluster

The worst-case situation can be excessive fragmentation: each level forming a cluster of its personal. Determine 11 compares the efficiency for the Z-curve and Hilbert curve for 2, three and 4 dimensions, a question measurement of seven (7×7 in 2D, 7x7x7 in 3D and so forth.) and 6 bits per axis (i.e. 64 values per axis)

The outcomes clearly present that the Hilbert curve preserves locality significantly better than the Z-curve. Throughout all examined dimensions, queries lead to fewer clusters and thus larger intra-cluster density with Hilbert indices. In observe, this interprets into extra environment friendly knowledge retrieval and lowered I/O prices, significantly for multidimensional vary queries.

6 Past House-Filling Curves

The objective of this text was for instance the class of SFCs and to provide a glimpse into their purposes in knowledge indexing. Nevertheless, the most recent analysis on this discipline goes past classical SFCs.

The primary limitation of all space-filling curves is their mounted mechanism. As soon as outlined, their construction affords little room for adaptation to totally different datasets or workload patterns. In observe, this rigidity can restrict efficiency.

To beat this, researchers resembling Chen et al. (College of Digital Science and Expertise of China & Huawei) have proposed AdaCurve, a machine studying–based mostly strategy. As an alternative of counting on a predetermined mapping, AdaCurve trains a mannequin to generate a one-dimensional index instantly from high-dimensional knowledge factors, optimized in keeping with each the dataset and the question workload. [3]

This concept is extremely promising: whereas Hilbert and different SFCs provide elegant however inflexible mappings, AdaCurve adapts dynamically, producing an indexing system that’s tailor-made to the info and queries at hand. Such adaptability might pave the best way for considerably extra environment friendly indexing in large-scale knowledge platforms sooner or later.

References

[1] H. Sagan, House-Filling Curves. Springer-Verlag, 1994.

[2] M. Bader, House-Filling Curves – An Introduction with Functions in Scientific Computing. Springer-Verlag, 2013.

[3] X. CHEN, “Optimizing block skipping for high-dimensional knowledge with discovered adaptive curve,” SIGMOD, vol. 3, 2025. [Online]. Obtainable:https://zheng- kai.com/paper/2025_sigmod_chen.pdf