Database Reference
In-Depth Information
tree; the node 4 has nodes 2 and 6 below it at the next level of the tree, while
the node 12 has 10 and 14 below it at the next level of the tree. The last
level has nodes 1 and 3 below 2, 5 and 7 below 6, and so on. Note that this
is a general structure suitable for out-of-core storage of static binary trees.
It is independent of the dimension
d
of the grid of points or of the Z-order
space-filling curve.
The structure of the binary tree defined on the Z-order space-filling curve
allows one to easily determine the three elements necessary for the computa-
tion of the cardinality. They are (1) the level
i
of an element, (2) the constants
C
i
of Equation (9.1), and (3) the local indexes
I
i
.
i
— if the binary tree hierarchy has
k
levels then the element of Z-order index
j
in the
Z
-order belongs to the level
k
h
, where
h
is the number of
trailing zeros in the binary representation of
j
.
C
i
— the total number of elements in the levels coarser than
i
, with
i
−
>
0, is
2
i
−
1
with
C
0
=
C
i
=
0.
j
2
k
−
i
must be
I
i
— if an element has index
j
and belongs to the set
S
i
, then
an odd number, by definition of
i
. Its local index is then:
2
k
−
i
+
1
j
I
i
(
j
)
=
.
The computation of the local index
I
i
can be explained easily by looking
at the bottom right part of Table 9.2 where the sequence of indexes (1, 3, 5,
7, 9, 11, 13, 15) needs to be remapped to the local index (0, 1, 2, 3, 4, 5, 6,
7). The original sequence is made of a consecutive series of odd numbers. A
right shift of one bit (or rounded division by two) turns them into the desired
index.
These three elements can be put together to build an ecient algorithm that
computes the hierarchical index
I
(
I
i
s
)
=
C
i
+
(
s
)
in the two steps shown in
Figure 9.6(a):
+
1. Set the bit in position
k
1to1.
2. Shift to the right until a 1 comes out of the bit string.
This algorithm could have a very simple and ecient hardware implementa-
tion. The software C++ version can be implemented as follows:
inline adhocindex remap(register adhocindex i){
i |= last_bit_mask; // set leftmost one
i /= i&-i;
// remove trailing zeros
return (i>>1);
// remove rightmost one
}
This code would work only on machines with two's complement representa-
tion of numbers. In a more portable version, one needs to replace
i /= i&-i
with
i /= i&((~i)+1)
.
