Irregularity in high-dimensional space-filling curves
Abstract
A space-filling curve is a way of mapping the discrete multi-dimensional space into the one-dimensional space. It acts like a thread that passes through every cell element (or pixel) in the discrete multi-dimensional space so that every cell is visited exactly once. Thus, a space-filling curve imposes a linear order of the cells in the multi-dimensional space. There are numerous kinds of space-filling curves. The difference between such curves is in their way of mapping to the one-dimensional space. Selecting the appropriate curve for any application requires knowledge of the mapping scheme provided by each space-filling curve. Irregularity is proposed as a quantitative measure for the ordering quality imposed by space-filling curve mapping. The lower the irregularity the better the space-filling curve in preserving the order of the discrete multi-dimensional space. Five space-filling curves (the Sweep, Scan, Peano, Gray, and Hilbert) are analyzed with respect to irregularity. Closed formulas are developed to compute the irregularity in any dimension k for a D-dimensional space-filling curve with grid size N. A comparative study of different space-filling curves with respect to the irregularity is conducted and results are presented and discussed. We find out that for an application that is biased toward one of the dimensions, the Sweep or the Scan space-filling curves are the best choice. For high-dimensional applications, the Peano space-filling curve would be the best choice. For applications that require fairness among various dimensions, the Hilbert and Gray space-filling curves are the best choice.
Keywords
space-filling curves, fractals, irregularity, high-dimensional space, performance analysis
Date of this Version
11-2011
DOI
10.1007/s10619-010-7070-7
Comments
Distributed and Parallel Databases Volume 29, Number 3 (2011), 217-238