Digital Signal Processing Reference
In-Depth Information
Fig. 9
σ
-ordered classifier chain
In this section, we study the impact of the topology of classifiers on the
performance of the stream mining system. For a single application/query this
topologic optimization may be seen as an order selection for a chain topology. We
thus start by focusing on a chain topology and study how the order of classifiers on
the chain alters performance.
The chain-topology construction problem has been studied as part of the broader
in query optimization. However, their focus has been on simple and deterministic
operators. For instance, the research only considers perfect classifiers, i.e. classifiers
that make no mistakes (
p
D
1and
p
F
0). Furthermore, the management of
limited resources (e.g. CPU, memory, I/O bandwidth etc.) while providing desired
=
=
3.1
Linear Topology Optimization: Problem Formulation
Since classifiers have different a-priori selectivities, operating points, and com-
plexities, different topologies of classifiers will lead to different classification and
delay costs. Therefore, given a set of classifiers instantiated on processing nodes,
topologic optimization can improve the end-to-end utility of the stream mining
system.
Consider
N
classifiers in a chain, defined as in the previous section. An order
σ
∈P
is a permutation such that input data flows from
C
σ
(
1
)
to
C
σ
(
N
)
.
We generically use the index
i
to identify a classifier and
h
to refer to its depth
in the chain of classifiers. Hence,
C
i
=
erm
(
N
)
C
σ
(
h
)
will mean that the
h
th classifier in the
chain is
C
i
. To illustrate the different notations used, a
σ
-ordered classifier chain is
throughput
t
i
and goodput
g
i
of classifier
C
i
=
C
σ
(
h
)
recursively as
t
i
g
i
p
i
+
φ
h
(
t
h
−
1
g
h
−
1
p
i
−
p
i
)(
φ
h
−
φ
h
)(
p
i
−
p
i
)
=
.
(5)
φ
h
p
i
0
T
h
T
i
=
