Information Technology Reference
In-Depth Information
local repository then a
QueryMatch
message is
created containing information about the match.
The
QueryMatch
messages are then transmitted
back, using reversely the path
q
travelled, to
Q
.
Finally, since more than one
QueryMatch
message
may have been received by
Q
, it can select the
peer with best connectivity attributes for direct
transfer of the match. It is obvious that the BFS
sacrifices performance and network traffic for
simplicity and high-hit rates. In order to reduce
network traffic, the TTL parameter is used, which
is the number of peers a query should be forwarded
to. In a modified version of this algorithm, the
Random BFS (RBFS) (Kalogeraki, Gunopulos,
& Zeinalipour-Yazti, 2002), the query peer
Q
propagates the query
q
not to all but a fraction
of its neighbor peers.
In an attempt to rectify the inability of the
RBFS to select a path of the network leading to
large network segments, the
>RES
algorithm was
developed (Yang & Garcial-Molina, 2002). In
this approach, the query peer
Q
propagates the
query
q
to a subset of its neighbor peers based on
an aggregated statistic. That is,
Q
propagates the
q
to
k
neighboring peers, all of which returned
the most results during the last
m
queries, with
k
and
m
being configurable parameters.
>RES
is
a significant amelioration in comparison to the
RBFS algorithm, however its attitude is rather
quantitative than qualitative, since it does not
select the neighbors to propagate the query
q
based on the similarity of the content of
q
with
the previous queries.
To overcome this quantitative behavior of
the
>RES
approach, the
ISM
approach emerged
(Kalogeraki et al., 2002). In
ISM
, for each query,
a peer propagates the query
q
to the peers that
are more likely to reply the query based on the
following two parameters; a profile mechanism
and a relevance rank. The profile is built and
maintained by each peer for each of its neigh-
boring peers. The information included in this
profile consists of the
t
most recent queries with
matches and their matches as well as the number
of matches the neighboring peer reported. The
relevance rank (
RR
) function is computed by
comparison of the query
q
to all the queries for
which there is a match in each profile. Thus, for
a querying peer
P
Q
the
RR
function is calculated
by the following formula:
RR
Q
(
P
i
,
Q
) =
Qsim
(
q
j
,
q
)
a
×
S
(
P
i
,
q
j
)
where Qsim is the similarity function used be-
tween queries and S(P
i
,
q
j
) is the number of the
results returned by Pi
i
for query
q
j
. The
ISM
al-
lows for higher ranking of the neighboring peers
that return more results by adjustment of the α
parameter. Obviously, the strong point of the
ISM
approach reveals in environments that show
increased degree of document locality.
searching methods In structured
p2p networks
In strictly structured P2P systems, the neighbor
relationship between peers and data locations is
explicitly defined. Thus, the particular network
architecture of such systems determines the
searching process. Of the alternative strictly
structured systems available, some implement the
Distributed Hash Table (DHT), others have flat
overlay structures while some have hierarchical
overlay structures.
A DHT is a hash table whose table entries
are distributed among different peers located in
arbitrary locations. In such systems each node is
assigned with a region in a virtual address space,
while each shared document is associated with
a value of this address space. Thus, locating a
document requires only a key lookup of the node
responsible for the key. Numerous different flat
data structures can be used to implement the
DHT, including ring, mesh, hypercube, and other
special graphs such as de Bruijn graph.
Hierarchical DHT P2P systems organize peers
into different groups or clusters, where each group
forms its own overlay. The entire hierarchical
Search WWH ::
Custom Search