Use 1D Hilbert curves instead of 3D Q2DI?

[danlooo]

Currently, DGGS native data cubes are stored in a 3D index i.e. Q2DI. However, address space in RAM and disk is 1D. Space filling curves, e.g. the Hilbert, transform a multi dimensional index into 1D while preserving spatial locality.

Tiling and 3D index

• Trivial neighbour retrieval (x -> x + 1)
• used by raster data (GeoTIF, Map tiles, Zarr chunking, JPEG blocks)
• More memory access (if tile size >> kernel size)
• Faster neighborhood calculation

Hilbert curves and 1D index

• Less memory access
• Used by vector data (PostGIS, FlatGeobuff)
• need to convert between 1D Hilbert and 2D coordinates every time to get neighbors (complex algo, can be cached in self similar curve)
• a bounding box can have many Hilbert intervals (No bbox to hilbert encoding found in Julia. Only pixel by pixel)
• used to assign data chunks to nodes in cluster computing (but not at lower level e.g. assign pixels)
• not implemented, e.g. no xarray extension

Conclusion

DGGS native data cubes are raster data. Just tiling should be faster than using the additional Hilbert index for reasonable tile sizes i.e. similar to window and kernel size (Google map tiles are 256*256px, S3 chunks should be ~10MB i.e. 1024px * 1024px double is 8.3MB). Trade off using Hilbert curves: caching size vs reduced number of RAM lookups.