Information Technology Reference
In-Depth Information
Banerjee et al.
[7]
suggested three types of clustering sequences in a CAD
object-oriented database—
depth first
,
breadth first
, and
children-depth-first
. Chang
and Katz
[13]
developed a clustering algorithm for objects with multiple relation-
ships and different access frequencies among objects. Based on the notion provided
by
[13]
, Cheng and Hurson
[19]
analyzed the clustering technique by studying the
effect of object updating when tuning the disk page
read/write
ratio. A cost esti-
mation of the gain achieved by a dynamic re-clustering scheme was investigated.
It was concluded that, in general, as the read/write ratio increases, re-clustering
should be performed more frequently. Inspired by Kruskal's minimum-cost spanning
tree algorithm, the work was enhanced by proposing a level clustering algorithm.
The algorithm takes a weighted DAG as its input, and provides a level-clustering
sequence as its output based on the degree of connectivity among the objects—
objects related through stronger semantic links (higher weights on the edges) are
clustered closer to one another. Chehadeh et al.
[17]
investigated object cluster-
ing in a parallel disk environment. Finally, Lim et al.
[45]
studied the employ-
ment of the clustering scheme of Cheng and Hurson
[19]
in a distributed environ-
ment.
Figure 5
depicts a weighted DAG and the resulting clustering sequences achieved
when different clustering techniques are applied. It should be noted that the tech-
niques proposed in
[7]
are only applicable to non-weighted DAG and that the tech-
niques proposed in
[17,19]
generate the same clustering sequence.
Similar concept can be adapted to organize information on the air channel.
The object organization on an air channel has to meet the following three crite-
ria
[14,16]
:
Linear ordering
: The air channel is a one-dimensional sequential access struc-
ture. This fact requires that the linear object ordering. In a DAG representation
of a complex object, an edge between two nodes could signify an access pattern
among the two nodes; retrieving the object represented by the first node could
trigger the retrieval of the second object. Therefore, if an edge exists from object
a
to object
b
, then to achieve minimum delays between the retrieval of objects,
a
has to appear before
b
.The
linearity
property is defined as: if an edge exists
between two objects
o
1
and
o
2
and in the direction
o
1
→ o
2
, then
o
1
should be
placed prior to
o
2
.
Minimum linear distance between related objects
: Reducing the distance among
interrelated objects along the broadcast reduces the response time and power
consumption.
More availability for popular objects
: Considering the sequential access pattern
of the broadcast channel, providing more availability for popular objects can be
achieved by simply replicating such objects.
