Locality-Preserving Linearization via Space-Filling Curves

211 concepts152 papers1 proposal

Our physical computing infrastructure is fundamentally one-dimensional. Random-access memory (RAM), solid-state drive (SSD) pages, and GPU execution blocks are organized as linear sequences of addresses. Yet, the data we care about is increasingly multi-dimensional: 2D images, 3D point clouds, spatiotemporal vehicle trajectories, and high-dimensional feature embeddings.

This mismatch introduces severe inefficiencies. If we store a 2D image using a standard row-by-row (raster) scan, pixels that are vertically adjacent end up separated by the entire width of the image in memory. When a neural network or spatial database attempts to query a local neighborhood, it triggers fragmented memory accesses, cache misses, and random disk I/O.

To bridge this gap, researchers across deep learning, database design, and distributed systems rely on a powerful geometric mechanism: locality-preserving linearization via space-filling curves. By mapping multi-dimensional coordinates to a continuous 1D path, this approach ensures that elements close in physical or abstract space remain proximal in memory.

The Intuition: Why Space-Filling Curves Preserve Proximity

To understand why space-filling curves work, contrast them with a standard raster scan. A raster scan forces a hard disconnect at every row boundary: the last pixel of row $N$ is memory-adjacent to the first pixel of row $N+1$, even though they sit on opposite sides of the image. Meanwhile, it completely decouples vertical neighbors.

Space-filling curves (SFCs), such as the Z-order (Morton) curve or the Hilbert curve, solve this by using fractal, self-similar paths that recursively fill a multi-dimensional space.

Z-Order Curve (N-Shape)       Hilbert Curve (U-Shape)
   ┌───┐   ┌───┐                 ┌───┐   ┌───┐
   │   │   │   │                 │   │   │   │
 ┌─┘   ┌─┘ ┌─┘   ┌─┘             └───┘   └───┘
 │     │   │     │               ┌───┐   ┌───┐
 └───┐ └───┐ └───┐               │   │   │   │
                                 └───┘   └───┘

The Z-order curve achieves linearization by interleaving the binary bits of a point's coordinates. As shown by Cai et al. in DITIR: Distributed Index for High Throughput Trajectory Insertion and Real-time Temporal Range Query, interleaving spatial and temporal bits maps a 3D spatiotemporal trajectory directly to a 1D sequence. This bit-interleaving ensures that data points belonging to the same localized space-time volume receive similar 1D keys, simplifying complex multi-dimensional range queries into linear lookups.

The Hilbert curve improves upon the Z-order curve by eliminating the dramatic directional jumps seen at the boundaries of the Z-curve's "N" shapes. The Hilbert path turns continuously, ensuring that it only ever steps to an immediate physical neighbor. Schmidt-Hieber leverages this property in The Kolmogorov-Arnold representation theorem revisited, demonstrating how Lebesgue or Hilbert curves can map multivariate functions into smooth univariate representations. By maintaining spatial adjacency, these curves turn complex geometric proximity problems into simple 1D distance comparisons.

Accelerating Modern Deep Learning

In deep learning, transformers and state-space models (SSMs) process data as sequences, but visual and physical data is inherently spatial. Linearization allows models to process multi-dimensional inputs without losing structural context.

In high-resolution image generation, standard attention mechanisms scale quadratically with the number of tokens. To mitigate this, Tai et al. in Scale-DiT: Ultra-High-Resolution Image Generation with Hierarchical Local Attention reorder image tokens along a Hilbert curve. Because spatially adjacent pixels are stored contiguously in memory, the model can utilize highly efficient block-sparse attention kernels, drastically reducing memory overhead and latency for 4K image generation.

Similarly, the authors of Hilbert-Guided Sparse Local Attention demonstrate that aligning 2D neighborhoods with 1D memory blocks maximizes the formation of "empty blocks" that modern GPU kernels can skip entirely, yielding up to an 18× speedup. Zhang et al. extend this principle to video and language models in SpargeAttention: Accurate and Training-free Sparse Attention Accelerating Any Model Inference, showing that reordering multi-dimensional tokens into a 1D sequence via space-filling curves preserves spatial locality well enough to supercharge block-based compression and sparsity techniques without sacrificing accuracy.

This linearization is equally potent for 3D data and sequence models:

Unifying Spatial Databases and Traditional Indexing

Beyond deep learning, space-filling curves allow multi-dimensional databases to inherit the decades of optimization built into traditional 1D indexing structures like B+ trees and Log-Structured Merge (LSM) trees.

In their foundational work on the Hilbert R-tree, Kamel et al. Hilbert R-tree: An Improved R-tree using Fractals show that assigning a scalar key to bounding boxes based on their Hilbert-ordered centroids enables "deferred splitting" techniques typical of B-trees. This maximizes node utilization and reduces search times. Similarly, the authors of Hierarchical Quadrant Spatial LSM Tree for Indexing Blockchain-Based Geospatial Point Data linearize 2D coordinates into 1D Z-order strings, enabling standard sorted-string storage engines to process write-heavy blockchain geospatial data via sequential write patterns.

By mapping multi-dimensional data to a 1D space, complex multi-dimensional range queries are transformed into simpler 1D range searches. Günther demonstrates in Benchmarking spatial joins a la carte that z-ordering allows spatial queries to leverage mature B+-trees for efficient range searches and joins. When dealing with massive data streams, Koudas et al. Approximate NN queries on Streams with Guaranteed Error/performance Bounds employ Z-curves to linearize grid cells, allowing standard tree structures to manage spatial proximity with guaranteed error bounds.

Optimizing Distributed Systems and Parallel Computing

When data scales beyond a single machine, maintaining locality becomes a network bottleneck. Space-filling curves provide an elegant way to partition data across distributed clusters.

In distributed graph and mesh processing, Borrell et al. A runtime-based dynamic mesh partitioning approach map multi-dimensional mesh coordinates to a 1D sequence, balancing computational workloads across parallel hardware without the high overhead of traditional graph-connectivity analysis. For distributed databases, Scholl et al. HiSbase: Histogram-based P2P Main Memory Data Management utilize Z-order curves to ensure that geographically proximal data points reside on the same or adjacent peers in a distributed hash table, minimizing network hops during range queries.

This principle extends to MapReduce and Spark frameworks. Zhang et al. Efficient parallel kNN joins for large data in MapReduce combine space-filling curves with random data shifts to handle approximate $k$-nearest neighbor joins across distributed nodes. In the context of semantic web data, the authors of DiStRDF: Distributed Spatio-temporal RDF Queries on Spark use a Hilbert curve to bake spatial coordinates into 1D identifiers, allowing Spark to prune irrelevant data at the very start of the query pipeline.

Supercharging Data Compression and Privacy

Because space-filling curves ensure that similar or physically close data points are stored adjacent to one another, they dramatically enhance the efficiency of local compression algorithms.

Benini highlights in Extended Bit-Plane Compression for Convolutional Neural Network Accelerators that neural network feature maps function like heat maps where values change smoothly across spatial dimensions. Keeping these dimensions adjacent in memory creates longer sequences of highly compressible data. For massive scientific simulations, Di et al. In-Depth Exploration of Single-Snapshot Lossy Compression Techniques for N-Body Simulations reorder particles using Z-order curves before applying lossy compression, ensuring that physically close entities are contiguous in memory and maximizing compression ratios.

In the domain of data privacy, Ghinita Fast Data Anonymization with Low Information Loss demonstrates that projecting multi-dimensional records onto a 1D Hilbert curve simplifies complex partitioning into linear ordering tasks. This preserves the locality of the original data, resulting in significantly lower information loss during data anonymization compared to traditional axis-splitting techniques.

Key Foundational Work

DOT: A Spatial Access Method Using Fractals (1991) — contributed 6 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_space_filling_curve_mapping_34fc4400,
  title = {space-filling curve mapping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/space-filling-curve-mapping/rdr_34fc4400f42c4293af76645e373749fc},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_space_filling_curve_mapping_34fc4400_v1,
  title = {space-filling curve mapping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/space-filling-curve-mapping/rdr_34fc4400f42c4293af76645e373749fc/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake