The problem of ontology alignment is prominent for applications that operate on integrated semantic data. With ontologies becoming numerous and increasingly large in size, scalability is an important issue for alignment tools. This work introduces a novel approach for computing ontology alignments using cloud infrastructures. An alignment algorithm based on particle swarm optimisation is deployed on a cloud infrastructure, taking advantage of its ability to harness parallel computation resources. The deployment is done with a focus on parallel e ciency, taking into account both communication latency and computational inhomogeneity among parallel execution units. Complementing previous experiments showing the e ectiveness of the alignment algorithm, this paper contributes an experiment executed \in the cloud", which demonstrates the scalability of the approach by aligning two large ontologies from the biomedical domain.
Ontology alignment is a problem prominent in semantic applications, the semantic web, and the linked data web. It is based on the observation that ontologies1 are heterogeneous models, often representing a similar or equal domain of interest, and hence have a certain overlap. Accordingly an ontology alignment is de ned as a set of correspondences between ontological entities, i.e. classes, properties, and individuals, of two ontologies.
Two examples of where ontology alignment plays an important role are the
linked data web [
This paper addresses the scalability problem of ontology alignment by
utilising cloud computing as a massively parallel computation infrastructure. The
algorithm to be deployed in the cloud is an alignment algorithm based on particle
swarm optimisation (PSO) [
The rst two issues are inherent to the application of the PSO meta-heuristic. However, the usability of the approach depends on an e cient deployment on parallel computing infrastructures. Computation and adjustment of alignments on an irregular basis usually does not justify the acquisition of large parallel hardware infrastructures.
Cloud computing infrastructures are scalable and can be used for data
intensive parallelisable jobs, as it has successfully been shown e.g. in the eld of
bio-informatics [
The remainder of this paper is structured as follows. In Sect. 2 relevant background knowledge and related work is presented. Section 3 introduces the approach of ontology alignment by PSO and demonstrates its parallel scalability. Justi ed by these insights, Sect. 4 discusses the design and implementation of a cloud-based deployment of the formerly introduced approach. Experimental results are presented in Sect. 5 demonstrating both the e ectiveness by referring to previous benchmarks, and the scalability by using a real-world biomedical alignment scenario. Section 6 summarises the contributions and provides an outlook on future work.
This section introduces ontology alignment, particle swarm optimisation (PSO), and cloud computing in more details. 2.1
An ontology alignment is de ned as a set of correspondences between ontological
entities [
A representative overview of the state-of-the-art in ontology alignment is
given by Euzenat and Shvaiko [10, Chap. 6] and by the yearly Ontology
Alignment Evaluation Initiative (OAEI) [
PSO is a biologically and socioculturally-inspired meta-heuristic [
PSO algorithms use a population of particles to nd the optimal parameter con guration with respect to one or more objective functions. Each particle represents a candidate solution. A particle's tness is evaluated using objective function(s). During initialisation, each particle in the swarm is assigned a random position in the parameter space. A PSO algorithm runs iteratively, where in each iteration, each particle adjusts its position in the parameter space by adding a velocity vector to its current position. These particle updates can be performed in parallel. The velocity vector for a particle is determined by the particle's previous velocity (inertia), the best position that has been visited by any neighbour of the particle so far (social component ), and the best position, the particle itself has visited so far (cognitive component ). Regarding the social component, several models of de ning particle neighbourhoods have been analysed. Such models are called social network structures or topologies. A PSO algorithm is called gBest (global best) PSO, if the neighbourhood of a particle consists of the whole swarm. Thus the gBest PSO is a special case of the lBest (local best) PSO, where the neighbourhood of a particle comprises only a subset of the swarm [8, Chap. 12].
It is important to note, that the particle swarm search heuristic works without any knowledge about the objective function(s). Hence an objective function is replaceable and adjustable to arbitrary optimisation problems. 2.3
Cloud computing is a new paradigm that has been evolving over the last few
years. Most de nitions of cloud computing have in common that cloud computing
o erings can be categorised using the \Everything as a Service" (XaaS) model. A
more detailed view of this model is the \Cloud Computing Stack" [
The IaaS o erings at the \Basic Infrastructure Services" level, give the
developer full control over the servers that are running his software. At this level
the user can deploy new machines using Web service technologies. This o ers
the power and exibility to work on a machine level without running one's own
data center and so having convenient access to new resources. O erings such as
Amazon EC2 give users the opportunity to automatically deploy hundreds of
virtual machines within minutes. Thus, it is possible to build highly scalable
applications that can scale up and down in short periods. One famous example of
a successful cloud o ering is Animoto [
Another interesting feature of cloud o erings is the typical pay-as-you-go
pricing model. This means that users only pay for the resources they are really
using. Having such a pricing model it makes no di erence if one single server
is running for 10 hours or if 10 servers are running for just one hour. The New
York Times used this pricing scheme when they built their \TimesMaschine".
By using Amazon EC2 they were able to convert their whole archive (4 TB of
scanned TIFF les), spanning the years 1851-1922, to web documents within
24 hours and total costs of US$ 890 [
In the context of semantic technologies and the semantic web, cloud
computing technologies have been successfully applied, mainly for RDF storage [
Considering ontology alignment as an optimisation problem, a novel discrete
PSO algorithm (DPSO) has been developed to nd an optimal alignment of two
ontologies [
3.1
In the case of ontology alignment, each particle represents a valid candidate
alignment. With a swarm of particles being initialised randomly, in each
iteration, each particle evaluates the alignment it represents via an objective function
comprising various basic matching techniques [10, Chap. 4] as well as the size of
an alignment. Typically there is only a partial overlap of ontologies, so the
alignment algorithm strives for nding the largest alignment, i.e. maximum number of
correspondences, of high quality. Base matchers can evaluate a correspondence
according to di erent characteristics, such as lexical or linguistic similarity of
entity labels or comments. Moreover, correspondences do not necessarily have
to be evaluated in isolation, e.g. a correspondence of two classes can get a better
evaluation if a correspondence of their superclasses is also part of the alignment
represented by this particle. As discussed in Sect. 2.2 the objective function and
thus the base matchers are replaceable and hence can be adapted to particular
alignment scenarios. For instance in biomedical ontologies speci c OBO4 [
Similar to the previous work by Correa et al. [
This update mechanism allows for a guided convergence of the swarm to a global optimum, which represents the best alignment with respect to the basic matching techniques speci ed as objective function. Moreover, the size of each particle varies during the execution of the algorithm in uenced by the size of the global best alignment. This causes the algorithm to search for the optimum size of the alignment, i.e. partial overlap, as well. 3.2
A detailed theoretical discussion of the correlation between population size and number of iterations with respect to the swarm convergence goes beyond the scope of this paper. Figure 1 illustrates an empirical analysis of the convergence towards the optimum5 when aligning small ontologies of the OAEI benchmark dataset. The gure shows clearly that a larger number of particles results in faster convergence by reducing the number of required iterations and thus reducing wall-clock runtime. Where it takes about 225 iterations for a swarm of 8 particles to reach an alignment of high quality, the same result is achieved in only 90 iterations by a swarm of 64 particles. Using only 2 particles does not reach an equally good result within 300 iterations. 4 Open Biomedical Ontologies 5 Note that the optimum depends on the chosen base matchers and thus not necessarily has to be 0.
0.8 0.7 t 0.6 n e lignm 0.5 A t s e lba 0.4 b o lf g tyo 0.3 li a u Q 0.2 0.1 To obtain the required scalability, the PSO-based alignment algorithm has been ported to Amazon Web ServicesTM (AWS), the IaaS cloud service of Amazon R . AWS is one of the biggest IaaS providers with a large and active community, and is representative for any other IaaS provider in the context of this work.
The deployment has been realised using a server-worker pattern. Several workers evaluate and update several local particles each, while they are managed by a central server. Each worker determines the local best alignment among the results of its particles and sends it to the server. The server determines the global best alignment, then broadcasts it and synchronises the workers. Exchange of information between server and workers is realised by the Amazon Simple Queue Service (SQS)6 or via TCP/IP. The exchange of concrete particle states is realised by the Amazon Simple Storage Service (S3)7 for reasons of scalability, reliability, and parallel access. Deploying the algorithm on virtual machines connected by a network bears two main challenges. Firstly, the communication latency is much higher when communicating via network than via main memory. Hence nding and broadcasting the global best particle leads to a higher communication overhead, which slows down the algorithm and creates unwarranted costs.
Secondly, the computation times of workers in a particular iteration di er. This di erence occurs mainly for two reasons: The unpredictable performance of the virtual environment, and the varying particle sizes. The performance of the virtual machine depends on its mapping to real hardware. For example a \noisy" neighbour, i.e. another program sharing the same real hardware via a di erent virtual machine, can slow down network communication. In turn, a virtual machine can utilise more computing power if there are no or only inactive neighbours. This results in unbalanced performance of the virtual machines. The random initialisation of particles and their di erent sizes add to this discrepancy in computation time. A small particle needs less computation time than a big particle, therefore a worker with smaller particles will require less runtime per iteration. The random initialisation of particles with di erent sizes is necessary to search for the optimal alignment size and thus be able to identify partial overlaps of ontologies. This computation time discrepancy causes fast workers to idle while waiting for the slower workers and thus decreases parallel e ciency. 4.2
The challenges of deploying the algorithm to a cloud-based infrastructre identied have been addressed and solutions are proposed as follows.
Addressing Latency. Amazon SQS was used as a means for communication between server and workers. Amazon advertises SQS as reliable, scalable, and simple. However, it turned out that SQS has high latency. For reducing the network latency, direct communication has been implemented using the TCP/IP protocol. Apart from reduced latency, this also resulted in a reduction of the additional communication overhead caused by multiple workers.
The latency is reduced further by only sending particle states when necessary, i.e. when a better particle state has been found. To achieve this a worker sends the tness value of its local best particle to the server and writes the particle state itself into the S3 database. The server then broadcasts the global best tness and the according database location to all worker instances.
The number of read operations is minimal, since in the PSO topology used, each particle must know about the global best. In case the global best does not change, no worker has to read a particle state. The (unlikely) worst case in terms of communication latency happens if every worker nds a new best alignment and thus writes its particle state before it has to read a new one found by another worker in the same iteration.
Addressing Runtime Discrepancy. The e ect that workers require di erent runtimes for particle tness computation can be minimised by particle pooling, i.e. having each worker instance computing multiple particles. Using few particles per worker results in high runtime variance between workers caused by di erent particle sizes and the resulting uneven workload. Using more particles per worker, i.e. the workload for each worker being the sum of workloads contributed by each of its particles, averages the runtime because a rather uniform distribution of small and big particles per worker is expected. Using a multi-particle approach also increases parallel e ciency due to the increased overall runtime required to evaluate and update several particles. By increasing the runtime the proportion of time used for communication decreases and thus parallel e ciency is increased.
Using asynchronous particle updates is another way to compensate the runtime discrepancy. When using synchronous particle updates every worker has to wait for the slowest worker and thus is wasting computation time. In the asynchronous communication mode workers keep on evaluating and updating their particles until they nd a particle state that is better than the global best they know about. They send this particle state to the server and continue. The server broadcasts the new particle state if it is better than the global best known by the server. Preventing workers to idle drastically increases parallel e ciency.
Introducing an asynchronous particle update strategy has an e ect on the underlying particle swarm meta-heuristic. Having not all particles exchanging information at the same time step has a similar e ect than changing the social network structure of the PSO from a star topology to a cluster topology8 [8, Chap. 12], which results in fast communication between particles on the same worker compared to the communication between workers themselves. A clustered (lBest ) topology in general results in slower convergence but better robustness compared to the star (gBest ) topology [8, Chap. 12].
Furthermore, a loss of information can be observed compared to the
synchronous update mechanism. This is due to the fact, that particles compute
iterations with possibly outdated information about the global best, which might
be available on a worker that is still computing another particle. This problem
has been analysed by Lewis et al. [
The bene cial e ect on the runtime for an alignment is re ected in Fig. 2, showing runtime behaviour for two medium sized ontologies for both synchronous and asynchronous particle updates. As expected, using an asynchronous communication mode does not have any e ect if only a single worker is used. However, for 16 workers that need to communicate their local best results in each iteration, a clear runtime improvement of almost 50 % can be observed.
One further e ect resulting from the asynchronous particle updates is that
workers hosting mainly small particles can complete an iteration more quickly
than those hosting mainly large particles. Therefore small particles tend to
compute more iterations and thus in uence the swarm stronger than it would be the
case in the synchronous mode. This is bene cial to the overall runtime of the
algorithm, because the average size of particles is smaller and therefore iterations
are faster.
8 While in a star topology, every particle shares information with every other particle,
the cluster topology allows only groups of particles to communicate with each other,
while the groups themselves exchange information only via dedicated particles, which
are part of two clusters.
Since for large ontologies there are no reference alignments available, e ectiveness
and scalability of the approach need to be evaluated separately. While it can
be shown for small benchmark ontologies, that the algorithm produces correct
results using a problem speci c parameter con guration, a separate experiment
has been conducted evaluating scalability using a cloud infrastructure.
Previous evaluations of the MapPSO system at the Ontology Alignment
Evaluation Initiative (OAEI) campaigns 2008 and 2009 [
In the experiment a population of 128 particles was used distributed on 16 Amazon EC2 instances (workers) and thus utilising particle pooling by computing 8 particles per worker. The EC2 instances were of the type \High-CPU Extra Large Instance, 7 GB of memory, 20 EC2 Compute Units (8 virtual cores with 2.5 EC2 Compute Units each), [. . . ] 64-bit platform, [where] one EC2 Compute Unit (ECU) provides the equivalent CPU capacity of a 1.0-1.2 GHz 2007 Opteron or 2007 Xeon processor"11. The setup was chosen in a way, that the number of particles on each instance matches the number of virtual cores, thus enabling e cient multi-threading of particle computation.
The experiment was run for 3.5 h, where due to the asynchronous particle updates, workers computed between 50 and 75 iterations. The di erence in the number of iterations illustrates the di erent computational e orts of each worker. Workers that achieved a lower number of iterations than other workers at the same time, are most likely computing smaller particles on average. This illustrates the runtime discrepancy addressed in Sect. 4.1 and the increased parallel e ciency gained by using an asynchronous approach. By using a synchronous approach the slowest particle constitutes an upper bound and thus a maximum of 50 iterations could have been computed in 3,5 h. The asynchronous approach, however, computes an average of 62.875 iterations, which is an increase of 25 %.
Since there is no reference alignment available for GO and MESH as there is none for any other large ontologies, no statement about the result quality can be made. The experiment, however, demonstrates the scalability of the proposed approach, operating on large ontologies and converging to an alignment. 6
The problem of large-scale ontology alignment detection has been addressed by a PSO-based approach. PSO has the characteristics of (i ) being independent of its objective function(s) and thus easily adaptable to various ontology alignment scenarios, (ii ) being incremental, i.e. able to re ne an alignment when input ontologies evolve, and (iii ) being inherently parallelisable. The latter aspect has been exploited in this paper by deploying the algorithm in the AWS cloud. This deployment is making use of the emerging cloud computing paradigm, which
provides an on-demand infrastructure for dynamic computational needs, as it is the case for alignment re nements of gradually evolving ontologies.
When utilising parallel computation infrastructures on a pay-per-use basis, such as cloud o erings, it is crucial to maximise parallel e ciency. Due to the variable particle sizes used in this approach, di erent computation times for each particle in each iteration can be observed. Thus particle pooling, i.e. multiple particles per cloud instance, as well as asynchronous particle updates have been introduced to the algorithm in order to reduce the time wasted by idling particles.
Previous experiments in the course of OAEI participations have shown the e ectiveness of the PSO-based approach. Complementing these results, the scalability via parallelisation has been shown for two large biomedical ontologies.
Having realised the successful deployment of an ontology alignment algorithm in the cloud using an IaaS provider, it is a straightforward extension to provide ontology alignment itself as a web service (SaaS) based on a dynamic and scalable infrastructure. This enables large-scale ontology alignment for every user without bothering about hardware requirements. Together with the anytime behaviour of the PSO-based algorithm, business models comprising the dimensions computation time, price, and alignment quality can be created.
The presented research was partially funded by the German Federal Ministry of Economics (BMWi) under the project Theseus (number 01MQ07019).