Database Reference
In-Depth Information
algorithm, amortizing the cost of individual I/O operations over several mem-
ory access operations.
In the case of hierarchical visualization algorithms for volumetric data, the
3D input hierarchy is traversed from a coarse grid to the fine-grid levels to
build derived geometric models having adaptive levels of detail. The shapes of
the output models are then modified dynamically with incremental updates of
their level of detail. The parameters that govern this continuous modification
of the output geometry are dependent on runtime user interaction, making
it impossible to determine, a priori , what levels of detail will be constructed.
For example, parameters can be external, such as the viewpoint of the current
display window, or internal, such as the isovalue of a contour or the position of
a slice plane. The general structure of the access pattern can be summarized
into two main points: (1) the input hierarchy is traversed from coarse to fine
and level by level so that data in the same level of resolution is accessed at
the same time, and (2) within each level of resolution, the regions that are
in close geometric proximity are stored as much as possible in close memory
locations and also traversed at the same time.
In this section, we describe a static indexing scheme that induces a data
layout satisfying both requirements (1) and (2) for the hierarchical traversal
of n -dimensional regular grids. The scheme has three key features that make
it particularly attractive. First, the order of the data is independent of the
out-of-core block structure, so that its use in different settings (e.g., local
disk access or transmission over a network) does not require any large data
reorganization. Second, conversion from the Z-order indexing 27 used in clas-
sical database approaches to the new indexing scheme can be implemented
with a simple sequence of bit-string manipulations, making it appealing for a
possible hardware implementation. Third, since there is no data replication,
we avoid the performance penalties associated with dynamic updates as well
as increased storage requirements typically associated with most hierarchical
and out-of-core schemes.
Beyond the theoretical interest in developing hierarchical indexing schemes
for n -dimensional space-filling curves, our approach targets practical appli-
cations in out-of-core visualization algorithms. For details on related work,
algorithmic analysis, and experimental results see Pascucci and Frank. 28
9.3.2.1
Hierarchical Subsampling Framework
This section discusses the general framework for an ecient definition of a
hierarchy over the samples of a dataset.
Consider a set S of n elements decomposed into a hierarchy
H
of k levels of
resolution
H ={
S 0 ,
S 1 ,... ,
S k 1 }
such that:
S 0
S 1 ⊂ ··· ⊂
S k 1 =
S
where S i is said to be coarser than S j if i
<
j . The order of the elements in S
is defined by a cardinality function I : S
→{
0
...
n
1
}
. This means that the
Search WWH ::




Custom Search