Information Technology Reference
In-Depth Information
it can be immediately tested against the query
itself (i.e.,
R
). Thus, no false-positives will be in-
cluded in the answer-sets, which could negatively
impact the backward-phase traffic, as they would
be propagated to the querier just to discover that
they are not actual matches. It should be noticed
that, to be able to perform index probing (i.e., to
avoid sequential searching at each MH), a small
number of DWT coefficients are included in
R
as
well. However, their size is negligible compared
to the size of the query sequence.
The resulting algorithm is denoted as ML (full
M
aximum representation with
L
ocal resolution at
MHs). ML is summarised in Figure 3 according
to the actions performed for each occurring event
(see Figure 1(b)).
two extreme cases: by setting
l
=
d
,
R
becomes
identical to the first (1) case; in contrast, by set-
ting
l
=
n
,
R
becomes identical to the second (2)
case, since the
n
DWT coefficients are equivalent
to the
n
elements of the query sequence (due to
the Parseval's theorem)
3
.
As described in Sec-
tion “Features and Indexing”, a number
l
of the
greater DWT coefficients can effectively capture
the energy of the music sequence and reduce the
number of false-positives. The result is that, com-
pared to the second (2) case, the forward traffic is
smaller, because
l
≤
n
. Compared to the first (1)
case, the backward traffic is smaller too, due to
the number of false-positives being significantly
reduced, since
d
≤
l
.
The tuning of
l
, however, is difficult, as it
depends on several factors, like the topology of
the MANET, which are changeable. Accordingly,
the following approach can be used: Initially,
l
takes an adequately large value and this value is
monotonically reduced during the propagation of
R
in the forward phase. This constitutes a
transcod-
ing
scheme, as it involves sequences with varying
number of DWT coefficients that correspond
to varying approximations of the initial query
sequence. The transcoding scheme:
Algorithm Based on Reduced Query
Representation and Transcoding
Section “Algorithm based on Maximal Query
Representation” made apparent that a trade-off
exists between the forward and backward traffic.
ML focuses only on the improvement of backward
traffic and incurs high forward traffic. In this
section a different algorithm is presented, which
has a two-fold objective. The first is to produce a
representation
R
that achieves a balance between
the two phases and minimizes the overall traffic.
The second is to develop selective routing policies
for the propagation of the answer-sets, leading to
significant reduction of the backward traffic.
The first objective is confronted by setting
R
between the two extremes cases: (1) the minimum
possible representation with only the
d
DWT
coefficients that are required for the local index-
searching (minimising forward traffic), and (2)
the maximum possible representation with all
n
elements in the query sequence itself (elimi-
nating the burden of false-positives in terms of
computation and backward traffic). Therefore,
between the two extremes,
R
can consist of the
l
greater DWT coefficients, where
d
≤
l
≤
n
. Notice
that this type of representation generalises the
•
Keeps forward traffic low, since the size of
R
is reducing during its propagation in the
forward phase.
•
Reduces backward traffic by letting the MHs
involved in the forward phase to cache the
transcoded representation and, during the
backward phase, to use it for early resolv-
ing false-positives, before these reach the
querier. The problem of caching depends
on several network parameters and is in-
dependent to the theme of this section of
the chapter, while effective solutions can
be found in Fang, Haas, Liang, and Lin
(2004). Experimentation in Karydis et al.
(2006), shows that by simply caching the
representations for a small, fixed amount
of time, adequate performance is attained.
Search WWH ::
Custom Search