Music Information Retrieval in P2P Networks - Intelligent Music Information Systems: Tools and Methodologies - page 207

the MHs, in terms of CPU cost, as little as
possible.

tation, though, under the non-transformed query
is not a real result. Moreover, R must present no
false-negatives (real results that were missed due
to the transformation). However, its particular
implementation determines whether false-posi-
tives may be produced or if they will be completely
avoided. Based on all the aforementioned issues,
an abstract scheme to describe the entire searching
procedure consists of the steps depicted in Figure
1(a). These steps are summarised in four events
according to Figure 1(b).
To avoid duplicate effort, the procedure tags R
with an ID (see Section “Information Discovery/
Provision In Wireless Mobile Ad-hoc Networks”).
This way, MHs that have already received it will
perform no further action. Additionally, the propa-
gation of R to the neighboring MHs is controlled
by a parameter called h , which acts as a counter
that is decreased at each receiving MH (denotes
the available number of hops). Its initial value,
at the querier, is equal to MaxHop . This value
corresponds to the preferred tolerance to traffic
and network reach/coverage. The propagation
of answer sets (resulting from step 5) is handled
similarly.
As already mentioned, the searching process
consists of a forward and a backward phase.
During the former, R is propagated and during
the latter answers are routed back to the querier.
The two phases are interleaved, since during the
propagation of R by some MHs, other MHs are
returning answers to the querier. The backward

4. Each qualifying sequence has to reach the

querier in a way that reduces traffic. Notice
that the answers may have to be routed back
to the querier following paths different
from those through which the MHs with
qualifying sequences were reached, since
intermediate MHs may have changed their
position and therefore be out of range. Due
to this, every detected answer may not be
possible to reach the querier.

The searching procedure is initiated at the
querying MH, aiming at detecting sequences
in other MHs, which contain excerpts whose
similarity from the query sequence Q is within
user-defined boundaries, a threshold ε . The defini-
tion of the distance measure is detailed in Section
“Features and Indexing”. Just for now, one can
intuitively think of the distance as a measure of
how dissimilar two music sequences are. The
length of detected excerpts is equal to the length
of the query sequence Q .
To address traffic minimization, Q has to be
transformed to a representation form, denoted
as R , through which qualifying sequences are
detected.
Due to this transformation, it is possible that
false-positive results may appear. A false positive
result is a result that appears to be a true result
when comparing with the transformed represen-

Figure 1. Searching process and basic events

(a) seaching process

(b) events