KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Bradley, Patrick Erik; Jahn, Markus Wilhelm

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.

DOI: 10.1093/comjnl/bxaa036
Zugehörige Institution(en) am KIT Geodätisches Institut (GIK)
Institut für Photogrammetrie und Fernerkundung (IPF)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2020
Sprache Englisch
Identifikator ISSN: 0010-4620, 1460-2067
KITopen-ID: 1000121191
Erschienen in The computer journal
Projektinformation DFG, DFG EIN, BR 3513/12-1
Topo Stadtmodell (DFG, DFG EIN, BR 2128/18-1)
Vorab online veröffentlicht am 13.07.2020
Schlagwörter Gray code; Hilbert curve; index; scalability; high dimension; p-adic number
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page