Login | Register

Design and Evaluation of Algorithms for Parallel Classification of Ontologies

Title:

Design and Evaluation of Algorithms for Parallel Classification of Ontologies

Aslani, Mina (2013) Design and Evaluation of Algorithms for Parallel Classification of Ontologies. PhD thesis, Concordia University.

[img]
Preview
Text (application/pdf)
Aslani_PhD_S2013.pdf - Accepted Version
1MB

Abstract

Description Logics are a family of knowledge representation formalisms with formal semantics. In recent years, DLs have influenced the design and standardization of the Web Ontology Language OWL. The acceptance of OWL as a web standard has promoted the widespread utilization of DL ontologies on the web. One of the most frequently used inference services of description logic reasoners classifies all named classes of OWL ontologies into a subsumption hierarchy. Due to emerging OWL ontologies from the web community consisting of up to hundreds of thousand of named classes and the increasing availability of multi-processor and multi- or many-core computers, the need for parallelizing description logic inference services to achieve a better scalability is expected.

The contribution of this thesis has two aspects. On a theoretical level, it first presents algorithms to construct a TBox in parallel, which are independent of a particular DL logic, however they sacrifice completeness. Then, a sound and complete algorithm for TBox classification in parallel is presented. In this algorithm all the subsumption relationships between concepts of a partition assigned to a single thread are found correctly, in other words, correctness of the TBox subsumption hierarchy is guaranteed. Thereafter, we provide an extension of the sound and complete algorithm which is used to handle TBox classification concurrently and more efficiently. This thesis also describes an optimization technique suitable for better partitioning the list of concepts to be inserted into the TBox.

On a practical level, a running prototype, Parallel TBox Classifier was implemented for each generation of the classifier based on the above theoretical foundations, respectively. The Parallel TBox Classifier is used to evaluate the practical merit of the proposed algorithms as well as the effectiveness of the designed optimizations against existing state-of-the-art benchmarks. The empirical results illustrate that Parallel TBox Classifier outperforms the Sequential TBox Classifier on real world ontologies with a linear or superlinear speedup factor. Parallel TBox Classifier can form a basis to develop more efficient parallel classification techniques for real world ontologies with different sizes and DL complexities.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Aslani, Mina
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science
Date:April 2013
Thesis Supervisor(s):Haarslev, Volker
ID Code:977159
Deposited By: MINA ASLANI
Deposited On:17 Jun 2013 15:38
Last Modified:18 Jan 2018 17:44
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top