Database Reference
In-Depth Information
following identity always holds:
S
[
I
(
s
)
]
≡
s
where square brackets are used to index an element in a set.
One can define a derived sequence
H
of sets
S
i
as follows:
S
i
=
S
i
\
S
i
−
1
i
=
0
,... ,
k
−
1
H
={
S
0
,
S
1
,... ,
S
k
−
1
}
where formally
S
=∅
. The sequence
is a partitioning
−
1
A derived cardinality function
I
of
S
.
:
S
→{
0
...
n
−
1
}
can be defined on
the basis of the following two properties:
S
i
:
I
(
I
(
∀
s
,
t
∈
s
)<
t
)
⇔
I
(
s
)<
I
(
t
)
S
i
,
∀
S
j
:
i
I
(
I
(
∀
s
∈
t
∈
<
j
⇒
s
)<
t
)
If the original function
I
has strong locality properties when restricted to
any level of resolution
S
i
, then the cardinality function
I
generates the desired
global index for hierarchical and out-of-core traversal. The scheme has strong
locality if elements with close indexes are also close in geometric position.
These locality properties are well studied in Moon et al.
28
The construction of function
I
can be achieved as follows: (1) determine
the number of elements in each derived set
S
i
and (2) determine a cardinality
function
I
i
I
S
i
restriction of
I
to each set
S
i
. In particular, if
c
i
is the
number of elements of
S
i
, one can predetermine the starting index of the
elements in a given level of resolution by building the sequence of constants
C
0
,... ,
=
C
k
−
1
with
i
−
1
C
i
=
c
j
.
(9.1)
j
=
0
Next, one must determine a set of local cardinality functions
I
i
:
S
i
→
{
0
...
c
i
−
1
}
so that
S
i
:
I
(
I
i
∀
s
∈
s
)
=
C
i
+
(
s
).
(9.2)
The computation of the constants
C
i
can be performed in a preprocessing
stage so that the computation of
I
is reduced to the following two steps:
S
i
)
given
s
determine its level of resolution
i
(that is the
i
such that
s
∈
compute
I
i
and add it to
C
i
These two steps must be performed very eciently as they will be executed
repeatedly at runtime. The following section reports a practical realization of
this scheme for rectilinear cube grids in any dimension.
(
s
)
