3. SPACE DRIVEN PARTITION BY FILLING CURVES
In the first case the partition take into account only the
amount of the stored data and this quantity determines
only the number of cells, but not their location, size and
shape. In this approach the space filling curves, also
called spatial ordering, can order all cell belonging to a
regular partition.
By definition spatial ordering is a mathematical
transformation mapping a finite k-dimensional lattice to a
finite set of natural numbers.
Usually we introduce also a parameter, called resolution,
which represents the granularity of the domain: for
example a two dimensional spatial filling curve of
resolution r has built by dividing the original 2D square
representing the embedding space in 2 2r cells.
As an example of application, we may consider the “point
data geoidal height model layer”, which can be considered
representative of the most of vector point data in the geoid
data structure. We have that a point is a zero dimensional
object and so, by the theoretical point of view it is
impossible to find one-dimensional curve passing through
all the point. By the way we can associate with the point
an infinitesimal two-dimensional cell (the dimension of
which is determined by the sample granularity in the
sense that one point only belongs to each cell) and we
look to a space filling curve which has the characteristic of
completely covering the area.
1
3
0
2
5
7
13
15
4
6
12
14
1
3
9
11
0
2
8
10
Fig. 13 -N order
resolution 1,2
21
23
29
31
53
55
61
63
20
22
28
30
52
54
60
62
17
19
25
27
49
51
57
59
16
18
24
26
48
50
56
58
5
7
13
15
37
39
45
47
4
6
12
14
36
38
44
46
1
3
9
11
33
35
41
43
0
2
8
10
32
34
40
42
Fig. 14 - N order
resolution 3
1fj
M
\?
8
Cj
1(1
1P
7|
fi
fi
4
n
1
p
J
There are several space ordering, but the more important
are the following:
N or Peano order (Peano, 1890) (Figs. 13-14)
n or Hilbert order (Hilbert, 1891) (Figs. 15-16)
Both these curves pass once on every point cell in the
two-dimensional space; moreover the points which are
neighbours on the curve are generally neighbours in the
space.
In this way we can introduce an efficient single numerical
key on a one-dimensional line for each point instead of
identify the cells by means of two coordinates. The
construction of the Peano key is done by the interleaving
procedure; as an example the k key corresponding to the
point P(6,4) with cp = 6 (in binary 0110) and X = 4 (in
binary 0100) is k = 56 (00111000). Analogously a key for
the Hilbert key may be otbained, even if the algorithm
necessary for its construction it quite more complicate.
Compared by other spatial order, for instance the more
usual (in our approach) row order or row-prime order,
shown in Fig. 17, it has be seen that the Hilbert curve has
better performance in the most of spatial data processing,
but its encoding/decoding involves tedious operations.
In any case the suitability of the spatial ordering depends
upon the queries applied to the data and so is useful to
evaluate which kind of curve it is better to take into
account by examining the particular query distribution.
21
22
25
26
37
38
41
42
20
23
24
27
36
39
40
43
19
18
29
28
35
34
45
44
16
17
30
31
32
33
46
47
15
12
11
10
53
52
51
48
14
13
8
9
54
55
50
49
1
2
7
6
57
56
61
62
0
3
4
5
58
59
60
63
1
2
0
3
5
6
9
10
4
7
8
11
3
2
13
12
0
1
14
15
Fig. 17 - Row order and row-
prime order
