An efficient and scalable algorithm for segmented alignment of ontologies of arbitrary size

Abstract

It has been a formidable task to achieve efficiency and scalability for the alignment between two massive, conceptually similar ontologies. Here we assume, an ontology is typically given in RDF (Resource Description Framework) or OWL (Web Ontology Language) and can be represented by a directed graph. A straightforward approach to the alignment of two ontologies entails an $O(N^2)$ computation by comparing every combination of pairs of nodes from given two ontologies, where $N$ denotes the average number of nodes in each ontology. Our proposed algorithm called Anchor-Flood algorithm, boasting of $O(N\log (N))$ computation on the average, starts off with an anchor, a pair of “look-alike” concepts from each ontology, gradually exploring concepts by collecting neighboring concepts, thereby taking advantage of locality of reference in the graph data structure. It outputs a set of alignments between concepts and properties within semantically connected subsets of two entire graphs, which we call segments. When similarity comparison between a pair of nodes in the directed graph has to be made to determine whether two given ontologies are aligned or not, we repeat the similarity comparison between a pair of nodes, within the neighborhood pairs of two ontologies surrounding the anchor iteratively until the algorithm meets that “either all the collected concepts are explored, or no new aligned pair is found”. In this way, we can significantly reduce the computational time for the alignment. Moreover, since we only focus on segment-to-segment comparison, regardless of the entire size of ontologies, our algorithm not only achieves high performance, but also resolves the scalability problem in aligning ontologies. Our proposed algorithm reduces the number of seemingly-aligned but actually misaligned pairs. Through several examples with large ontologies, we will demonstrate the features of our Anchor-Food algorithm.

Introduction

“An ontology is an explicit specification of a conceptualization” is a prominent defintion by T.R. Gruber in 1995 [13]. The definition was then extended by Studer et al., in 1998 as “an ontology is an explicit, formal specification of a shared conceptualization of a domain of interest” [39]. An ontology generally consists of entities such as concepts, properties and relations. It is the backbone to fulfill the semantic web vision [2], [23] and is a knowledge base to enable machines to communicate each other effectively. The knowledge captured in ontologies can be used to annotate data, to distinguish between homonyms and polysemies, to drive intelligent user interfaces and even to retrieve new information. A number of ontologies are increasing day by day with new semantic web contents, because an ontology is being developed to formalize the conceptualization behind the idea of semantic web. Therefore, in order to achieve semantic interoperability and integrity, ontology alignment would be playing an important role [1].

Ontologies may be of different size, small to large, having hundreds to millions of RDF triples, where an RDF triple is an RDF statement between a subject, a predicate, and an object. A small-scale ontology is usually defined within a single segment, where the term “segment” is referred by Seidenberg et al. [34] as a fragment that stands alone as an ontology in its own right. A large-scale ontology is generally very complex in nature and may contain multiple segments [34]. Stuckenschimdt et al. [38] also reveals that a large-scale ontology contains a set of modules about a certain subtopic that can be used independently of the other modules. A large-scale ontology expressed in Web Ontology Language (OWL) [25] is appearing to capture distributed knowledge in a centralized knowledge base. For example, the biomedical domain has enormous large-scale ontologies, such as FMA [32] and OpenGALEN [31].

Although there are many diverse solutions to the ontology alignment problem [7], only a few are capable to handle large ontologies efficiently [17], [19]. Many previously developed ontology alignment systems are also facing severe performance problem when they attempt to deal with large ontologies. Resolving scalability problem is also an important current issue in the ontology alignment research [35]. Moreover, users (humans or machines) may want to find a specific part of a large ontology which will fit only to their interest.

The main contribution of our approach is of attaining performance enhancement by solving the scalability problem in aligning large ontologies. The key idea is to start from an anchor point of a taxonomy of an ontology and to proceed towards the neighboring nodes considering the locality of reference. Eventually our proposed algorithm aligns a part of gigantic ontologies and outputs a segmented alignment, (i.e. an alignment across two related segments or fragments across ontologies) which are relatively small, however sufficient to satisfy users interest in a particular domain. Therefore, performance, scalability, and segmented alignment (i.e. an alignment across two related segments or fragments of ontologies) are the key motivations of our proposed algorithm in this paper.

In our previous research work, we also focused on the ontology alignment [16]. Our system was capable of aligning small-scale ontologies effectively with the feature of eliminating misalignments. However, its major drawback was against the aligning of large-scale ontologies, as its complexity was $O(N^2)$. To overcome this limitation of scalability problem, we developed a new algorithm, we called as “Anchor-Flood” algorithm.

Our algorithm assumes a seed called an anchor, where the notion anchor is derived from the Anchor-PROMPT algorithm [30], although it is clearly different from the notion used in that algorithm. The Anchor-PROMPT algorithm augments existing methods by determining additional possible aligned pairs across ontologies, while our Anchor-Flood algorithm starts aligning from an anchor and produces segmented alignments.

Our algorithm also shares the term “flood” with similarity-flooding algorithm [26] without major similarities in their action blocks. Although our work is inspired by the idea of similarity flooding algorithm in that the elements of two distinct hierarchy models are likely to be similar when their adjacent elements are similar. However, our Anchor-Flood algorithm does not propagate similarity value to the adjacent nodes iteratively unlike similarity-flooding algorithm.

In the main process block of our algorithm, we collect aligned pairs from the neighboring concepts computing similarities among the collected concepts across ontologies starting from an anchor. It begins exploring to the neighboring concepts to collect more aligned pairs. As our algorithm starts off an anchor and explores to the neighboring concepts, it has a salient feature of scalability. Our algorithm achieves enhancement in terms of scalability and performance in aligning large ontologies. It can reduce the number of seemingly-aligned but actually misaligned pairs [16]. It also outputs “segmented alignment”, which is a unique characteristic in the field of ontology alignment research.

The rest of the paper is organized as follows. Section 2 introduces general terminologies to be used in the later sections. Section 3 contains the description of our proposed “Anchor-Flood” algorithm. Section 4 includes experiments and evaluation, while Section 5 describes the complexity factor of the algorithm. Some related work and the differences with our algorithm are described in Section 6. Section 7 includes concluded remarks along with some future directions of our work.