The Great thing about Area-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 usually hiding in plain sight—behind phrases like Z-ordering or Liquid Clustering (used, for instance, in platforms like Databricks). In the event you’ve labored with large-scale knowledge platforms, likelihood is you’ve already used SFCs with out realizing it.

Regardless of its relevance in fashionable techniques, info on this matter is usually fragmented, making it troublesome to bridge concept and follow. This text goals to bridge that hole, whereas specializing in the Hilbert curve.

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

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

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

1. Historical past and Concept of Area-Filling Curves

The research 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]

As an example this, contemplate the unit interval [0, 1] ⊂ R and the unit sq. [0, 1]² ⊂ R². Intuitively, one may 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 methodology of interleaving decimals.

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

On this context, continuity could be interpreted geometrically: a steady mapping would enable 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 Area-Filling Curves

After Netto’s sobering discovery, the query arose as as to whether 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, setting up 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 “closing” 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 statement 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 way of each level in [0, 1]² and thus utterly fills the aircraft, can its picture nonetheless be thought to be one-dimensional? The reply isn’t 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 better than 1, and a few even non-integer Hausdorff dimensions.

3. The Hilbert Curve – Widespread until right now!

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 easier 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’ll concentrate on the Hilbert curve, as its properties make it a beneficial instrument 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 among 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 could 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:

Normal 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 correct endpoint of the primary subinterval and the left endpoint of the second).
  Thus all the sq. is stuffed. The mapping, nevertheless, is just not injective—makes an attempt to implement bijectivity (e.g., by opening intervals) break continuity.
• Steady: This property is obvious from visible representations: the curve could 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 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 easier 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 large knowledge platforms.
• Constructive 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 aircraft. (Peano-Jordan Measure)
• Hausdorff Dimension of two: Correspondingly, the Hilbert curve doesn’t behave like a regular one-dimensional line, however has Hausdorff dimension 2, reflecting that it absolutely fills the unit sq..

Despite the fact that, early definitions of the Hilbert Curve are approached in 2D, larger dimensions are additionally possible. The algorithm we focus on 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 thought of methods learn how to compute factors for a given Hilbert index. Who may blame them? In any case, for a very long time there have been no computer systems that would draw curves with a whole bunch or hundreds of factors. Whereas researching I found a number of methods learn how to compute the Hilbert curve – from advanced numbers to L-Techniques. Whereas some are tremendous in depth, others protect the iterative method for computing single factors of the curve. What I used to be in search of 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 College 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 out there 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 could be expressed elegantly by way of 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. Remodel 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 may assist (we focus on all the pieces 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 on. grid. (Keep in mind the definition above and its recursive method).
By wanting on the numbers, one may 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 instance. Two bits per axis are ample:

1. The primary bit identifies the key 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 type 0010. Deciphering this:

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

Nevertheless, if we proceed this course of for indices better 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 strictly the place Grey code and XOR operations (as in Skilling’s algorithm) change into important.

4.3 Grey Code Illustration

The subsequent step in Skilling’s algorithm is a metamorphosis from binary to Grey code. The important thing distinction is that in Grey 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 remains to be not appropriate)

By wanting on the binary numbers and the orientation of the completely different sections of the curve, we are able to see that the curve remains 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 methodology 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 key quadrant and the second pair the sub-quadrant. Nevertheless, for coordinate computation we want a construction of the shape (bitx₁, bitx₂, bity₁, bity₂) so that each one x-bits and y-bits can later be mixed into the respective decimal coordinates (x, y). This step is known as 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 reveals how Grey-coded coordinates are transformed into customary binary numbers by making use of easy transformations: swaps and bit-flips.

The diagram on the correct visualizes the impact: the higher quadrants are rotated by 180◦, the decrease quadrants are mirrored alongside the diagonal, and in some instances (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 customary binary type. Which means the output of Skilling’s algorithm could 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 could be: [-1, ndims, nbits]. Instance: The quantity 4 could be represented as the next listing/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 (normally x) If 0: Swap values between
   decrease bits in present dimension and dimension 0 (in the event that they differ).

Step 3 could 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 personal animations in 2D or 3D, take a look at my GitHub Repository

5 Functions of Area Filling Curves

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

One beneficial 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 may stay in vector areas of arbitrary dimension. 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 Knowledge Partitioning/Clustering utilizing SFCs

Some of the distinguished purposes of SFCs is knowledge partitioning. For instance, in Databricks, Z-ordering is predicated 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 possibly can 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 immediately retrieve all matching entries. The important thing benefit is that this mapping allows quick and versatile knowledge retrieval. In contrast to conventional indexing, the Hilbert-based partitioning adapts naturally to updates or progress within the dataset — with out requiring all the index to be recomputed.

5.2 Knowledge 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 dimension. 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 type 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 indicate pricey jumps to new storage addresses.

To quantify efficiency, I used two metrics:

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

The worst-case state of affairs could 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 dimension of seven (7×7 in 2D, 7x7x7 in 3D and so on.) 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 end in fewer clusters and thus larger intra-cluster density with Hilbert indices. In follow, this interprets into extra environment friendly knowledge retrieval and lowered I/O prices, significantly for multidimensional vary queries.

6 Past Area-Filling Curves

The purpose of this text was for instance the magnificence of SFCs and to offer a glimpse into their purposes in knowledge indexing. Nevertheless, the newest analysis on this subject goes past classical SFCs.

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

To beat this, researchers reminiscent of Chen et al. (College of Digital Science and Know-how of China & Huawei) have proposed AdaCurve, a machine studying–based mostly method. As a substitute of counting on a predetermined mapping, AdaCurve trains a mannequin to generate a one-dimensional index immediately from high-dimensional knowledge factors, optimized in response to 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 may pave the best way for considerably extra environment friendly indexing in large-scale knowledge platforms sooner or later.

References

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

[2] M. Bader, Area-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]. Out there:https://zheng- kai.com/paper/2025_sigmod_chen.pdf