Our proposed algorithm called Anchor-Flood algorithm, starts off with anchors. It gradually explores concepts by collecting neighbors in concept taxonomy, thereby taking advantage of locality of reference in the graph data structure. Then local alignment process runs over the collected small blocks of concepts. The process is repeated for the newly found aligned pairs. In this way, we can significantly reduce the computational time for the alignment as our algorithm concentrates on the aligned pairs and it resolves the scalability problem in ontology alignment over large ontologies. Through several experiments against OAEI2008 datasets, we will demonstrate the results and the features of our AnchorFood algorithm.
The Anchor-Flood algorithm is mainly designed targeting to align two large scale ontologies or one large scale and another small scale ontologies effectively. It does not compare an entity against all the entities in other ontology. The way of selecting the group of entities to be compared is the novelty of our algorithm. Our algorithm operates quite faster over large ontologies as observed in aligning anatomy ontologies and it is depicted in Table 2. 1.1
The purpose of our Anchor-Flood algorithm is basically ontology matching. However, we used our algorithm in patent mining system to classify a research abstract in terms of International Patent Classification (IPC). Containing mostly general terminologies leads classifying an abstract a formidable task. Automatic extracted taxonomy of related terms available in an abstract is aligned with the taxonomy of IPC ontology with our algorithm succesfully. We also start using the Anchor-Flood in the focus-oriented biomedical applications which generally contain very large ontologies.
To be specific, we only describe our Anchor-Flood algorithm and the results against OAEI 2008 datasets here. For more details, we refer the reader to our semantic website : http://www.kde.ics.tut.ac.jp/h˜ anif. More elaborate information will be come out soon in our semantic technology geared website. 1.2
We implemented Anchor -Flood algorithm in java. Our algorithm contains preprocessing, adaptation module for OAEI 2008, the basic block of algorihtm and the local alignment process.
We created our own persistent model of ontology, as our algorithm requires optimal graph structure of concept taxonomy along with other non-trivial structural and simple lexical information. To collect the necessary information in repository, we use the ARP triple parser of jena module. Fig 1 shows the basic block of Anchor-Flood algorithm to comprehend easily. However, it has complex process of collecting small blocks of concepts and related properties dynamically.
As a part of preprocessing, we also normalize the lexical information and extract the derivative relations, like inherited restrictions etc.
The basic part of Anchor-Flood algorithm is depicted in Fig. 1. Starting off an
anchor, Anchor-Flood algorithm collects neighboring concepts which includes super
concepts, siblings and subconcepts of certain depth to form a pair of blocks across
ontologies, as the neighbors of similar concepts might also be similar [
Multiple anchors from different part of ontologies confirm a fair collection of aligned pairs as a whole. 1.3
The Anchor-Flood algorithm needs an anchor to start off. Therefore, we used another tiny program module, which is capable of extarcting some probable aligned pairs as anchors. The tiny program is attached inside along with our basic algorithm to produce a system. It uses lexical information and some statistical relational information to extract a small number of aligned pairs from different part of ontologies. The program is essentially small, simple and faster. We also removed the subsumption module of our algorithm to make it more faster. 1.4
The version of Anchor-Flood for OAEI-2008 can be downloaded from our website: http://www.kde.ics.tut.ac.jp/h˜anif/res/anchor flood.zip 1.5
The results for OAEI-2008 are available at our website: http://www.kde.ics.tut.ac.jp/ h˜anif/res/aflood.zip 2
In this section, we describe the results of Anchor-Flood algorithm against the benchmark and anatomy ontologies provided by the OAEI 2008 campaign. On the basis of the nature, we can divide the benchmark dataset into five groups: #101104, #201-210, #221-247, #248-266 and #301-304. We described the performance of our Anchor-Flood algorithm over each of the groups and depicted in . The overall summary over 1xx, 2xx and 3xx are also figured in . #101-104 Table 1 shows that Anchor-Flood algorithm produces perfect precision and recall in this group. #201-210 Although the lexical information of the ontologies are suppressed or modified, their structures remain quite similar. Therefore traversing the structure with taxonomy and relation works better for this group. #221-247 The structures of the candidate ontologies are altered. However, the dynamic block collector of our Anchor-Flood algorithm can collect concepts and properties as the ontologies are small in size. Therefore, it can still produce good precision and recall. #248-266 This is the most difficult group for our Anchor-Flood algorithm, as the structure and the lexical information altered significantly. However, the subgroups with xxx2 through xxx-8 are seemingly easier to align. #301-304 Anchor-Flood algorithm in this group works well even after removing the subsumption module from our main algorithm. Both structural and lexical analysis works well in this group. In this test, the real world cases of anatomy for Adult Mouse Anatomy (2744 classes) and NCI Thesaurus (3304 classes) for human anatomy are included. These are relatively large compared to benchmark ontologies. The actual effectivity of our Anchor-Flood algorithm shows with faster operational time. It collects 1187 aligned pairs within only 1.09 minutes in our Core2 Duo 2.4MHz processor with 2GB of memory. Table 2 shows the summary of the performance on the anatomy task. The main strength of our Anchor-Flood algorithm is the way of minimizing the comparisons between entities, which leads enhancement in performance. It has some better scope in the field of ontology versioning of small specific domain ontologies comparing with other large ontologies.
The weak points are: it has still rooms of improving alignments based on axioms, semantic similarity, and structures of ontologies.
The subsumption module of our algorithm takes much time. Our next plan is to improve the alignments on the basis of axioms and structures and improving the subsumption module as well. 4
Ontology matching is very important part of establishing interoperability among semantic application as the core of every semantic application is ontology. We implemented faster algorithm to align specific interrelated parts across ontologies, which gives the flavor of segmentation. Pair of segmented aligned part across ontology can be used versioning ontologies, e.g. cancer ontology versioning with the general diseases ontology. The anatomical ontology matching shows the effectiveness of our Anchor-Flood algorithm. Moreover, the experimental experience in the OAEI 2008 campaign will influence us building comprehensive ontology matching system removing the limitations of our algorithm in the future.
This study was partially supported by Global COE Program gFrontiers of Intelligent Sensingh from Japan’s Ministry of Education, Culture, Sports, Science and Technology.
The following table contains the results of Anchor-Flood algorithm in the benchmark test. The table includes precision (Prec.), recall (Rec.) and processing time. The processing time includes construction of model, execution of algorithm to produce aligned pairs and writing the results into a .rdf file.