Space-filling Curves for High-performance Data Mining
  Space-filling curves like the Hilbert-curve, Peano-curve and Z-order map
natural or real numbers from a two or higher dimensional space to a one
dimensional space preserving locality. They have numerous applications like
search structures, computer graphics, numerical simulation, cryptographics and
can be used to make various algorithms cache-oblivious. In this paper, we
describe some details of the Hilbert-curve. We define the Hilbert-curve in
terms of a finite automaton of Mealy-type which determines from the
two-dimensional coordinate space the Hilbert order value and vice versa in a
logarithmic number of steps. And we define a context-free grammar to generate
the whole curve in a time which is linear in the number of generated
coordinate/order value pairs, i.e. a constant time per coordinate pair or order
value. We also review two different strategies which enable the generation of
curves without the usual restriction to square-like grids where the side-length
is a power of two. Finally, we elaborate on a few applications, namely matrix
multiplication, Cholesky decomposition, the Floyd-Warshall algorithm, k-Means
clustering, and the similarity join.
