Close Menu
    Trending
    • Dispatch: Partying at one of Africa’s largest AI gatherings
    • Topp 10 AI-filmer genom tiderna
    • OpenAIs nya webbläsare ChatGPT Atlas
    • Creating AI that matters | MIT News
    • Scaling Recommender Transformers to a Billion Parameters
    • Hidden Gems in NumPy: 7 Functions Every Data Scientist Should Know
    • Is RAG Dead? The Rise of Context Engineering and Semantic Layers for Agentic AI
    • ChatGPT Gets More Personal. Is Society Ready for It?
    ProfitlyAI
    • Home
    • Latest News
    • AI Technology
    • Latest AI Innovations
    • AI Tools & Technologies
    • Artificial Intelligence
    ProfitlyAI
    Home » The Beauty of Space-Filling Curves: Understanding the Hilbert Curve
    Artificial Intelligence

    The Beauty of Space-Filling Curves: Understanding the Hilbert Curve

    ProfitlyAIBy ProfitlyAISeptember 7, 2025No Comments19 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Share
    Facebook Twitter LinkedIn Pinterest Email


    0. Introduction

    (SFC) are fascinating mathematical constructs with many sensible purposes in information science and information engineering. Whereas they could 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 information platforms, chances are high you’ve already used SFCs with out realizing it.

    Regardless of its relevance in fashionable techniques, info on this matter is commonly fragmented, making it tough to bridge concept and observe. 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 means of sensible implementation methods, and ending with real-world purposes in information processing and optimization. It’s not the plan to exchange present sources however moderately 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, a daily curve is straightforward to grasp and possibly not the primary matter I’d choose up a e book about. However SFCs are totally different. They traverse each level in a steady house, 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 instantly, 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 clean manifolds have the identical cardinality, no matter their dimensions.” [1]

    For example 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 methodology of interleaving decimals.

    This outcome implies the existence of a bijection between the interval and the sq., that 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 destructive.

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

    2. Peano Curve: The Discovery of Area-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 capable of outline such a mapping was G. Peano, developing 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]

    Determine 1: Peano curve of order 1,2 and three (from left to proper).
    The picture of the Peano curve of order 1 is copied and mirrored in greater orders. It may be noticed that the fundamental sample of the first-order Peano curve reappears in greater orders, however is mirrored in each second iteration. This alternating strategy of mirroring and rotating the fundamental ingredient is a function shared by different SFCs as effectively.
    (Image from Wikipedia below public area license, modified by creator)

    Thus, the graphs of the Peano curve at finite iterations (Determine 1) don’t signify 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 primarily seem as a crammed sq. spanning from (0, 0) to (1, 1)

    This remark raises an initially counterintuitive query: By definition, a curve is one-dimensional. Whereas it may be embedded in a higher-dimensional house (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 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 seem 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 – In style until as we speak!

    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.

    Determine 2: The fundamental unit on the left (order 1) is repeated to construct higher-order Hilbert curves. Nevertheless, the mandatory transformations (corresponding to mirroring and rotation) are extra advanced than within the case of the Peano curve.
    (Picture by creator)

    For the needs of this text, we are going to concentrate on the Hilbert curve, as its properties make it a priceless device in fashionable information 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:

    Splitting intervals in [0,1]. (Formular from [2], Picture by creator)

    For any chosen level in [0, 1], precisely one among these subintervals comprises the purpose. This interval can then be subdivided once more utilizing the identical rule, producing a finer interval that also comprises 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:

    Splitting quadrants in [0,1]2 . (Formular from [2], Picture by creator)

    Basic 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 precise endpoint of the primary subinterval and the left endpoint of the second).
      Thus the whole sq. is crammed. 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 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 features, 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 can be shut within the one-dimensional parameter are sometimes mapped to close by. This facet is essential for purposes in large information platforms.
    • Optimistic Jordan Content material: Within the restrict of infinitely many iterations, the picture of the Hilbert curve has constructive Jordan measure, that 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..

    Despite the fact that, early definitions of the Hilbert Curve are approached in 2D, greater 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 thought earlier than mathematicians considered methods learn how 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 would draw curves with lots of or 1000’s 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 searching for was one thing easy:

    • A perform that takes a Hilbert index (i.e. any numbers like 1,2,3 in 1D house) 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 accessible for the general public, so I made a decision to research 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 signify 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]2. 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 grasp why binaries are a lot better suited to computing factors of the Hilbert Curve from Hilbert Indices and vice versa the next examples would possibly assist (we focus on every part in 2D, however the algorithm works in any dimensional house):
    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 would possibly uncover that the variety of intervals develop with 2n, 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. Deciphering this:

    • 00 selects the lower-left quadrant.
    • 10 selects the upper-right subquadrant inside it.
    Determine 3: Mapping binaries to grid cells. The primary two bits encode the most important quadrant, the final two bits the
    subquadrant. Contemplate the repetitive sample of 00, 01, 10, 11 in each quadrant, forming a Hilbert curve of
    order 1. (Picture by creator)

    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 following. Accurately dealing with these rotations and reflections is precisely the place Grey code and XOR operations (as in Skilling’s algorithm) develop 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 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 following (regardless that the orientation of the curve in every quadrant remains to be not right)

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

    Determine 4: After remodeling binary values to Grey code, the final cell of a present quadrant has the identical worth
    as the primary cell of the following (Picture by creator)

    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 (bitx1, bity1, bitx2, bity2) 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 (bitx1, bitx2, bity1, bity2) so that every 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.

    Determine 5: Orientation of subquadrants in a 4×4 grid after Grey code disentanglement (Picture by creator)

    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 commonplace binary numbers by making use of easy transformations: swaps and bit-flips.

    The diagram on the precise 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. Because of this the output of Skilling’s algorithm could be transformed on to decimal coordinates within the format (x, y), with out additional adjustment

    Determine 6: Remaining transformations to transform grey code to binary coordinates (Picture by creator)

    Skilling algorithm key transformations: Enter: Grey code formatted (bitx1, bitx2, bity1, bity2) 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 important bit (LSB), and 0 probably the most important bit
    (MSB).

    1. Loop from probably the most important bit (MSB) to least important 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 strategy of flipping and swapping bits in every iteration is visualized within the following animations.

    Determine 7: Creation strategy of a 2D Hilbert curve utilizing the algorithm of John Skilling (Picture by creator)
    Determine 8: Creation strategy of a 3D Hilbert curve utilizing the algorithm of John Skilling (Picture by creator)

    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 Area Filling Curves

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

    One priceless facet of the Hilbert Curve is that it maps a 1D ordered set (i.e. 1,2,3…) to coordinates in an n-dimensional house. It provides an order to the factors it traverses and it may possibly stay in vector areas of arbitrary dimension. Thus, the Hilbert Curve is used for information partitioning and cluster, picture compression and likewise for constructing options in machine studying, when coping with spatial information.

    5.1 Information Partitioning/Clustering utilizing SFCs

    Probably the most distinguished purposes of SFCs is information 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 information. In determine 9 you’ll be able to see how some exemplary information factors are mapped to factors of the Hilbert curve, by assigning every level to at least one partition given by the curve.

    Determine 9: Mapping of information to factors of the Hilbert Curve. The purple dashed arrows point out some mappings
    exemplarily (Picture by creator)

    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 information retrieval. In contrast to conventional indexing, the Hilbert-based partitioning adapts naturally to updates or progress within the dataset — with out requiring the whole 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 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 is able to 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 indicate expensive jumps to new storage addresses.

    Determine 10: 100 random queries for a 2D setup utilizing Hilbert curve and Z-curve. As you’ll be able to see, you’ll be able to’t see something! 😉
    (Picture by creator)

    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 common variety of indices per cluster

    The worst-case state of affairs 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 dimension of seven (7×7 in 2D, 7x7x7 in 3D and so on.) and 6 bits per axis (i.e. 64 values per axis)

    Determine 11: Comparability of Hilbert and Z curve based mostly on variety of clusters and intra-cluster unfold for two,3 and 4 dimensions. The outcomes clearly present that the Hilbert curve preserves locality a lot better than the Z-curve (Picture by creator)

    The outcomes clearly present that the Hilbert curve preserves locality a lot better than the Z-curve. Throughout all examined dimensions, queries lead to fewer clusters and thus greater intra-cluster density with Hilbert indices. In observe, this interprets into extra environment friendly information retrieval and diminished 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 provide a glimpse into their purposes in information indexing. Nevertheless, the most recent analysis on this discipline goes past classical SFCs.

    The principle 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 corresponding to Chen et al. (College of Digital Science and Expertise of China & Huawei) have proposed AdaCurve, a machine studying–based mostly method. As an alternative of counting on a predetermined mapping, AdaCurve trains a mannequin to generate a one-dimensional index instantly from high-dimensional information factors, optimized in accordance with each the dataset and the question workload. [3]

    This concept is extremely promising: whereas Hilbert and different SFCs supply 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 information 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 information with discovered adaptive curve,” SIGMOD, vol. 3, 2025. [Online]. Accessible:https://zheng- kai.com/paper/2025_sigmod_chen.pdf



    Source link

    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticlePreventing Context Overload: Controlled Neo4j MCP Cypher Responses for LLMs
    Next Article Mistral Le Chat blir en riktig ChatGPT-utmanare – med nya minnessystemet
    ProfitlyAI
    • Website

    Related Posts

    Artificial Intelligence

    Creating AI that matters | MIT News

    October 21, 2025
    Artificial Intelligence

    Scaling Recommender Transformers to a Billion Parameters

    October 21, 2025
    Artificial Intelligence

    Hidden Gems in NumPy: 7 Functions Every Data Scientist Should Know

    October 21, 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Top Posts

    Synthetic data in healthcare: Definition, Benefits, and Challenges

    April 9, 2025

    Exploring RAFT: The Future of AI with Retrieval-Augmented Fine-Tuning

    April 4, 2025

    ChatGPT Agent, Grok 4, Meta Superintelligence Labs, Windsurf Drama, Kimi K2 & AI Browsers from OpenAI and Perplexity

    July 22, 2025

    Are You Being Unfair to LLMs?

    July 11, 2025

    Modern GUI Applications for Computer Vision in Python

    May 1, 2025
    Categories
    • AI Technology
    • AI Tools & Technologies
    • Artificial Intelligence
    • Latest AI Innovations
    • Latest News
    Most Popular

    AI tool generates high-quality images faster than state-of-the-art approaches | MIT News

    April 4, 2025

    Generalists Can Also Dig Deep

    September 12, 2025

    How to Correctly Apply Limits on the Result in DAX (and SQL)

    August 18, 2025
    Our Picks

    Dispatch: Partying at one of Africa’s largest AI gatherings

    October 22, 2025

    Topp 10 AI-filmer genom tiderna

    October 22, 2025

    OpenAIs nya webbläsare ChatGPT Atlas

    October 22, 2025
    Categories
    • AI Technology
    • AI Tools & Technologies
    • Artificial Intelligence
    • Latest AI Innovations
    • Latest News
    • Privacy Policy
    • Disclaimer
    • Terms and Conditions
    • About us
    • Contact us
    Copyright © 2025 ProfitlyAI All Rights Reserved.

    Type above and press Enter to search. Press Esc to cancel.