On the Behaviour of p-Adic Scaled Space Filling Curve Indices for High-Dimensional Data

Space filling curves are widely used in computer science. In particular, Hilbert curves and their
generalizations to higher dimension are used as an indexing method because of their nice locality
properties. This article generalizes this concept to the systematic construction of p-adic versions of
Hilbert curves based on special affine transformations of the p-adic Gray code and develops a scaled
indexing method for data taken from high-dimensional spaces based on these new curves, which with
increasing dimension is shown to be less space consuming than the optimal standard static Hilbert
curve index. A measure is derived, which allows to assess the local sparsity of a dataset, and is tested
on some real-world data.