Information Technology Reference
In-Depth Information
•
Reduces the processing (CPU) time at each
MH, as the cost of resolving false-positives
at each MH depends on the size of
R
.
Figure 5. The RT algorithm
Query initialization.
The querier sets
R
equal to a sample
with an initial size (parameter) plus the query coefficients, and
propagates (broadcasts) it to all its neighbors.
Reception of R
. Upon the reception of
R
, each MH
P
probes its
indexes, resolves as many false-positives as possible based on the
received query sample of
R
, and produces a list of results. The
answer-set is propagated back to the querier, by following the
described policy for the backward phase. Accordingly, should
there be available
h
,
R
is size is reduced, and the reduced
R
is
conveyed to all P's neighboring MHs (forward phase).
Reception of an answer-set.
When a MH receives a reply, it
checks if it can resolve any false-positives. This is true, should
it have received (if any) a representation that was larger than the
one that the sequences in the answer set were examined previ-
ously (i.e., at the sending MH). After any possible pruning, as
long as there is available
h
, the answer-set is routed backwards
following a policy.
An answer-set reaches the querier.
When an answer-set
reaches the querier, initially any remaining false positives
requiring resolution are examined, and then the results are
presented to the user.
The reduction is performed by getting
l
values
according to an inverse sigmoid function (Fig-
ure 4b). Due to the shape of this function, the
immediate neighborhood of the querier, which
can provide results faster, receives a larger
R
,
whereas the burden posed on MHs that are far
is appreciably smaller. Additionally, this way
the exponential growth of traffic that results by
plain broadcasting of a full-size representation
is controlled. An example is depicted in Figure
4a.
P
1
is the querier and
P
4
is the node that starts
propagating the answer-set. The MHs in the path
from
P
1
to
P
4
are depicted gray shaded, and they
are annotated with the size of
R
that reaches them
(
P
1
starts with 10K DWT coefficients). Figure
4b illustrates that these sizes are reducing, fol-
lowing an inverse sigmoid function. During the
backward phase, starting from
P
4
, MHs
P
3
and
P
5
can be reached (depicted with dashed arrows).
The cached representation in
P
3
can help resolving
possible false-positives in the answer-set. This is
due to the fact that in
P
4
the false-positives were
examined against a smaller
R
than the one in
P
3
.
In contrast,
P
5
was not in the path, thus cannot
resolve any false-positives.
Henceforth, the size of the initial query rep-
resentation is given as a factor (denoted as
I
) of
the complete query size, whereas the slope of the
inverse sigmoid function is controlled by a pa-
rameter denoted as α (higher values of α produce
a steeper slope).
Regarding the second objective, in contrast to
the simplistic approach of ML, which propagates
the answer-sets to all neighbors, during the for-
ward phase, as it is typical in any dynamic source
routing protocol (Johnson & Maltz, 1996), each
MH that receives
R
, additionally receives the ID
of all MHs in the path that were used from the
querier to it. These IDs can be maintained along
with
R
with minimal cost (only some bytes).
When a MH starts propagating answer-sets, it
selects among its current neighbors those that
will propagate the answer-set (not all of them).
To make this selection, it applies a policy that
focuses on the neighbors that were included in
the path from the querier to it. Since several
such policies can be developed, Section “Rout-
ing Policies for the Backward Phase” elaborates
further on them. All the policies, despite their
differences, emphasise on selecting neighboring
MHs that were included in the path, due to the
cached representations they maintain, which can
resolve some false-positives in situ.
The algorithm that combines all the aforemen-
tioned characteristics is denoted as RT (querying
Figure 4. Searching procedure example
Search WWH ::
Custom Search