Multidimensional digital compression methods based on Space-Filling Curves

Abstract

Common compression techniques typically do not exploit the underlying structure and dimensionality of the data being processed. However, queries on multidimensional data are already enhanced through the use of spatial data structures and d-dimensional restructuring. Space-Filling Curves (SFCs) are one such technique, mapping the data to the one-dimensional space such that the spatial locality is somewhat preserved. Their application to data compression is not as extensively researched, especially given that such work must be conducted within the context of the type of data being compressed. In this research, the application of SFCs to the compression of Digital Elevation Model and Radio-Astronomy data is evaluated. This has not been extensively researched before, for these types of data. Datasets from the Shuttle Radio Topographical Mission (SRTM) and Square-Kilometre Array telescope (SKA) projects are used in this work. An analysis and discussion of metrics quantifying locality preservation of these curves is provided, to allow for the analysis of how these curves impact the performance of compression schemes for the two aforementioned datasets. It is found that SFCs improve compression ratios in certain cases, the extent to which is dependent on the curve, the data’s statistical model, the preprocessing steps, and the metric performance of the curve. Compression and decompression speeds are not as significantly improved, with some combinations of curve and compression scheme giving a reduction in speeds. However, as is predicted by the locality preservation metrics and the data models, the SFCs do contribute to a significant increase in compressibility as measured by the information entropy