Database Reference
In-Depth Information
index of the data-space. Its simplicity, and the fact that it is consistent with
the linear quad-tree encoding of the space, makes it one of the most widely
used encoding methods in applications. 34 , 52 , 71 , 79 In Chapter 9, Z-order map-
ping is used for hierarchical indexing of multi-resolution data. Alternative
methods to the Z-order encoding are the Hilbert order encoding 57 and the
Gray-Code encoding. 79 In the table shown in Figure 6.7, column 4 shows the
linear quad-code (or Z-order code), generated from an 8
×
8 grid partition-
ing of the data space. Note that linear quad-code is a base k string of digits
formed by taking k-bits of the Z-order codes. The Gray-Code encodings of
the points are shown in column 5. Figures 6.12a and 6.12b depict the spatial
representations and code labels of points in a two-dimensional data space for
the Z-order and Gray-Code encoding, respectively.
6.5.3.1
Quaternary/Hierarchical Triangular Mesh
While most database applications deal with planar and hyper-rectilinear re-
gions, some large scientific applications deal with datasets that lie on spherical
surfaces. Examples of these are datasets from climate models, GIS, and as-
tronomy. The approach to indexing regions on spherical surfaces is similar to
the method of linear quad-code or Morton-sequence order encoding of planar
regions. The basic idea is to approximate the sphere by a base platonic solid
such as a tetrahedron, hexahedron (or cube), octahedron, icosahedron, and so
forth. If we consider, say, the octahedron, a spherical surface is approximated
at level 0 by eight planar triangular surfaces. By bisecting the midpoints of
each edge and pushing the midpoints along a ray from the center of the sphere
that passes through the midpoint to the surface, 4
8 triangular surfaces are
generated at level 1. Using such a recursive edge bisection procedure, the
solid formed from the patches of triangular planes approximates closer and
closer to the sphere. The process is depicted in Figure 6.13. Two base pla-
tonic solids that have been frequently used in such approximation schemes
of the sphere are the octahedron and the icosahedron shown in Figure 6.14.
Consider the use of an inscribed octahedron as the base solid. Indexing a
point on a spherical surface, at any level of the tessellation, amounts then to
indexing its projection on the triangular patch at the level where the point
lies. If we now pair the triangular upper and lower triangular patches to form
four quadrants, then the higher-level tessellation of each quadrant is similar to
the higher-level tessellation of planar regions that can now be encoded using
any of the space-filling curve encoding schemes. In Figure 6.14a we illustrate
such a possible encoding with the Z-order encoding. Variations of the tech-
nique just described, according to whether the base-inscribing platonic solid
is either an octahedron, cube, or an icosahedron, and the manner of label-
ing the triangular regions, form the basis of the various techniques known
as the Quaternary Triangular Mesh (QTM), Hierarchical Triangular Mesh,
Semi-Quadcode (SQC), and so forth. 7 , 8 , 53 , 79 , 93
×
Search WWH ::




Custom Search