Database Reference
In-Depth Information
(
)
(b)
(
)
(
)
(
)
Coarser data
(even samples)
New level data
(odd samples)
(
f
)
(g)
(
)
(
i
Figure 9.5
(See color insert following page 224.) The nine levels of resolu-
tion of the binary tree hierarchy defined by the 2D space-filling curve applied
on 16
16 rectilinear grid. The coarsest level of resolution (a) is a single point.
The number of points that belong to the curve at any level of resolution (b)
to (i) is double the number of points of the previous level.
×
b
j
” (with
j
string of
h
bits “
b
j
b
j
···
=
,... ,
1
d
) then the 1D reference
I
of
e
is
b
d
”.
The 1D order can be structured in a binary tree by considering elements of
level
i
, those that have the last
i
bits all equal to 0. This yields a hierarchy
where each level of resolution has twice as many points as the previous level.
From a geometric point of view this means that the density of the points
in the
d
-dimensional grid is doubled alternating along each coordinate axis.
Figure 9.5 shows the binary hierarchy in the 2D case where the resolution
of the space-filling curve is doubled alternately along the
x
and
y
axes. The
coarsest level (a) is a single point, the second level (b) has two points, the
third level (c) has four points (forming the Z shape), and so on.
Index Remapping.
The cardinality function discussed in Section 9.3.2.1
for the binary tree case has the structure shown in Table 9.2. For example, the
element of index 0 is always at the top of the tree (level 0) for any granularity.
If the index has 5 granularity levels (the 4th row in the table), node 8 is at
the second level of the tree; the nodes 4 and 12 are at the next level of the
“
b
1
b
2
···
b
d
b
1
b
2
···
b
d
···
b
1
b
2
···
represented by the string of
hd
bits
I
=
TABLE 9.2
Structure of the hierarchical indexing scheme for binary tree
combined with the order defined by the Lebesgue space-filling curve
Level of Tree
0 1 2
3
4
Z-order index (2 levels) 0 1
Z-order index (3 levels)021 3
Z-order index (4 levels)042 613 5 7
Z-order index (5 levels)0841226101413579 1 3 5
hierarchical index
0 1 2
3 4 5
6
7 8 9 10 11 12 13 14 15
