Space-Filling Curves for Efficient Multidimensional Data Storage and Querying

In the real world, massive multidimensional spatial data such as gas‑station locations and river trajectories exist. To store and manage these data efficiently, many key‑value based spatial databases (e.g., the open‑source GeoMesa plugin and JD's JUST engine) employ space‑filling curve (SFC) techniques, converting multidimensional data into one‑dimensional index values for storage and query.

Spatial objects can be divided into point objects (e.g., POI and GPS points) and extended objects (e.g., roads, trajectories, administrative regions). Managing these objects is challenging because they often contain high‑dimensional coordinates, shapes, sizes, and attributes, and the data volume can reach terabytes or even petabytes, causing scalability issues for traditional spatial databases.

Point Space‑Filling Curves

Z‑ordering (Z‑curve) recursively subdivides space into four quadrants until a maximum resolution is reached, assigning a unique code to each smallest grid. The codes follow a lexical order that resembles the letter “Z”. For efficient comparison, the Z‑curve codes are usually converted to integers.

Hilbert Curve

The Hilbert curve is a fractal space‑filling curve that recursively divides a square into four sub‑squares and connects their centers. It uses a U‑shaped traversal pattern, adjusting orientation at each recursion to preserve locality. The resulting integer codes start from 0 and increase following the curve’s order.

Spatial‑Extension Filling Curves (XZ‑Ordering)

While Z‑ordering and Hilbert curves work well for point objects, they cannot uniquely represent extended objects that intersect multiple grids. XZ‑Ordering extends Z‑ordering by defining an "expanded element" that doubles the width and height of each sub‑space, allowing a single integer to represent an entire polygon or line. The method uses enlarged elements that fully contain the object, reducing storage overhead and query‑time deduplication.

XZ‑Ordering also employs a depth‑first integer encoding similar to Z‑ordering, ensuring that spatially close elements receive numerically close codes.

Conclusion

Space‑filling curves map multidimensional data to a one‑dimensional integer domain while preserving spatial locality. Z‑ordering and Hilbert curves are easy to implement for point data, whereas XZ‑Ordering extends these techniques to efficiently handle non‑point spatial objects such as lines and polygons.

References

[1] https://www.geomesa.org/

[2] http://just.urban-computing.com/

[3] R. Li et al., "Just: JD urban spatio‑temporal data engine", ICDE 2020.

[4] T. Asano et al., "Space‑filling curves and their use in the design of geometric data structures", Theoretical Computer Science 1997.

[5] https://en.wikipedia.org/wiki/Space-filling_curve

[6] https://baike.baidu.com/item/希尔伯特曲线/938155

[7] C. Böhm et al., "XZ‑Ordering: A Space‑Filling Curve for Objects with Spatial Extension", SSD'99.