KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Bradley, Patrick Erik ORCID iD icon; 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
Zitationen: 4
Zugehörige Institution(en) am KIT Geodätisches Institut (GIK)
Institut für Photogrammetrie und Fernerkundung (IPF)
Universität Karlsruhe (TH) – Interfakultative Einrichtungen (Interfakultative Einrichtungen)
KIT-Zentrum Klima und Umwelt (ZKU)
Publikationstyp Zeitschriftenaufsatz
Publikationsmonat/-jahr 02.2022
Sprache Englisch
Identifikator ISSN: 0010-4620, 1460-2067
KITopen-ID: 1000121191
Erschienen in The computer journal
Verlag Oxford University Press (OUP)
Band 65
Heft 2
Seiten 310–330
Projektinformation Topo Stadtmodell (DFG, DFG EIN, BR 2128/18-1)
DFG, DFG EIN, BR 3513/12-1
Vorab online veröffentlicht am 13.07.2020
Schlagwörter Gray code; Hilbert curve; index; scalability; high dimension; p-adic number
Nachgewiesen in Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page