Information Technology Reference
In-Depth Information
F
IG
. 5. Various clustering of a sample graph.
Figure 6
depicts a directed graph and multiple linear sequences that satisfy the
linear ordering property. The individual middle columns represent the cost of delays
between every two objects connected via an edge. For the sake of simplicity and
without loss of generality, an
object
unit is used as a unit of measurement. Further-
more, it is assumed that all objects are of equal size. The cost associated with an
edge between a pair of objects is calculated by counting the number of objects that
separate these two objects in the linear sequence. For example, in the
abfgchdeij
sequence objects
a
and
d
are separated by the sequence
bfgch
and thus have a cost
of 6. The right-most column represents the total cost associated with each individ-
ual linear sequence. An optimal sequence is the linear sequence with the minimum
total sum. In a query where multiple related objects are retrieved, a minimum aver-
age linear distance translates into smaller average response time. In this example, the
optimum linear sequence achieves a total sum of 26.
