Databases Reference
In-Depth Information
log-lin scale specially for Chord indicate a logarithmic hop number. The triple
components of this query are all in the domain 'ubd0v0'. Consequently, corre-
sponding triples are stored in 3nuts in the same subtree with path 'ubd0v0' and
peers managing this subtree have fast lookup to each other. This really keeps
the hop numbers down for small networks up to 64 peers where single or only a
few peers manage the data for that domain. For larger networks more routing is
needed within the subtree and we see a linear increase starting a 128 peers like
in Chord.
While Figure 3a showed the total numbers of hops during processing a query,
Figure 3b shows the numbers of hops needed for routing of the next triple pattern
in chain of triple patterns in the query (percentile to the expected hop numbers
O
(log
n
)). In the Chord overlay, we need almost the same numbers of hops to
lookup all indexed triple components. On the contrary, in the 3nuts overlay, the
hops for lookup decrease after the first step by 50% and the reason is again the
information locality: the first step starts at an arbitrary peer which might not
participate in the subtree of domain 'ubd0v0' in the 3nuts tree with
(log
n
)
hops, but when the query enters this subtree once, it stays inside for the rest of
the query steps with fast routing.
Figure 4b shows further reductions in the numbers of hops needed for evalu-
ating the query in Listing 1.2 with the creation of up to 5 shortcuts by each peer
in 3nuts network. If a peer interested in evaluation of a triple pattern maintains
a
shortcut
to the lookup key of this triple pattern, then it takes it 0 hops to
reach this lookup key. The establishment of constant numbers of shortcuts for
each peer to frequently occurring triple components in the network could result
to a significant reduction in numbers of hops, e.g. the numbers of hops needed
for our example query reduced from 26 to 9 with creation of 4 shortcuts.
O
4.2 Analysis of Query Response Time
Our simulation does not provide the simulation of a real-world physical network
and it is impossible to find one suitable model covering all possible fields of
application such as the Internet, Intra net, and so on. Therefore we will present
in this section how to derive the query response time from the given experimental
routing data with a given physical network model. Let
k
=
δ
b
denote the product
of delay
δ
and bandwidth
b
in the physical network. The query response time
t
is then for
m
triples patterns
p
i
·
c
i
+hops
i
·
δ
+
data
i
·
+
δ
hops
i
+
data
i
b
+1
.
m
m
δ
t
=
≈
δ
·
k
i
=1
i
=1
where
c
i
is the computation time for evaluating pattern
p
i
,hops
i
is the number
of hops to lookup the peer providing the triples for pattern
p
i
, and data
i
is the
data size for triples of pattern
p
i
to transfer to the next peer. For
c
i
δ
we
neglect the computation time.
The response time is mainly driven by routing delays and data transfer time.
When the bandwidth is very high, routing delays are a dominant factor and
Search WWH ::
Custom Search