An Ontology-Based P2P Network for Semantic Search - Cloud, Grid and High Performance Computing: Emerging Applications - page 308

This forwarding process is recursively carried out
until the destination semantic cluster is reached.
When the query reaches a node in the des-
tination semantic cluster, the node will use its
finger table to route the query in the lower-tier
network. An example of the finger table of node
N5 is shown in Figure 4. If a context query in the
form of SELECT ?x WHERE (<socam:John>
<socam:homeAddress> ?x) reaches node N5 ,
node N5 will look up the hashed <sub pred> pair
using its fingers. Finally, node N6 and the result
<socam:John socam:homeAddress “XYZ”> will
be returned.
For a given network with N nodes and M se-
mantic clusters, a query can be first routed to any
semantic cluster in O( 1

invoked to simulate the dynamic characteristic of
the network. Each node is assigned with a query
generation rate, which is the number of queries
that it generates per unit time. In our experiments,
each node generates queries at a constant rate. If
a node receives queries at a rate that exceeds its
capacity to process them, the excess queries are
queued in its buffer until the node is ready to read
the queries from the buffer. Queries are selected
randomly among various semantic clusters. We
set the same number of nodes for each semantic
cluster in our experiments; however, in reality
they can be different.
We use the following metrics to measure
the performance of our system: the search path
length measured as the average number of hops
traversed by a query to the destination; the cost
of node joining/leaving measured as the average
number of messages incurred when a node joins
or leaves the network.

s log 2 M) hops where s is
the total number of long range contacts, and then
routed to the destination in log(N/M) hops.

EVALUATION

Simulation Results

We move on to evaluate our system using simula-
tion and compare its performance to the original
Chord. We first describe our simulation model
and the performance metrics. Then we report the
results from a range of simulation experiments.
We also report the measurement results from the
prototype system we developed.

First, we evaluate the efficiency of query routing
in our system and compare it to Chord. We built
the two-tier network by defining a number of
semantic clusters in the upper-tier. In this experi-
ment, we fix the number of semantic clusters to 16
and vary network size from 2 5 to 2 13 . Hence, each
semantic cluster in the lower-tier has a number
of nodes ranged from 2 to 2 9 . Figure 5 plots the
average search path length of our system with 1
to 5 long range contacts on a logarithmic scale
in comparison with Chord. The result shows that
the two-tier network with 2 or more long range
contacts has shorter search path as compared to
Chord for a network size of 2 13 nodes or less.
It also shows that the search path length of the
two-tier network is logarithmic to the number of
nodes with a fixed number of semantic clusters.
In this experiment, we evaluate the impact of
semantic clustering in our system. We fix the
semantic cluster size to 8 (i.e., 8 nodes in each
semantic cluster) and vary the number of seman-

Simulation Model and Metrics

We use the AS model to generate network topolo-
gies as previous studies (Saroiu, et al., 2002) have
shown that P2P topologies follow both small world
and power law properties. The simulation starts
with having a pre-existing node in the network
and then performing a series of join operations
invoked by new coming nodes. A node joins its
major semantic cluster based on its local data, and
then stores its data triples and registers its data
indices. After the network reaches a certain size, a
mixture of node joining and leaving operations is