Algorithms for complete, efficient, and scalable alignment of large ontologies
MetadataShow full item record
As ontology repositories proliferate on the web, many contain ontologies that overlap in scope. Ontology alignment (OA) is the process of identifying this overlap, which is important for the discovery and exchange of knowledge. Consequently, aligning ontologies gains importance. OA algorithms are faced with crucial challenges: improving the correctness and completeness of the alignment, scaling to large ontologies and quickly producing the alignment without compromising its quality. In this dissertation, we present algorithms for complete, efficient and scalable ontology alignment. Many existing algorithms unconditionally utilize lexicons such as, WordNet for the potential improvement in the alignment accuracy. We empirically analyzed the impact on alignment quality and execution time when using WordNet for OA. We provide useful insights on the types of ontology pairs for which WordNet-based alignment is potentially worthwhile. We also noticed that many algorithms either do not consider the complex concepts in their alignment procedures or model them naively. We introduce axiomatic and graphical canonical forms for modeling value and cardinality restrictions and Boolean combinations, and present a similarity-measure for them. OA algorithms may utilize this approach to model complex concepts for participation in the alignment process. Our results indicate a significant improvement in the quality of the alignment produced. Several algorithms use iterative approaches for better alignment quality though they consume more time than others. We present a novel and general approach to speed up the convergence of the iterative OA algorithms to produce similar or improved alignment using block-coordinate descent (BCD) technique. We also provide useful insights on how to identify an appropriate partitioning and ordering scheme for a given algorithm. As ontologies are submitted or updated in repositories, their alignment with others must be quickly computed. We project the problem of aligning several pairs of ontologies as that of batch alignment and demonstrate dramatic speedup in the alignment using the distributed computing paradigm of MapReduce. Using a representative set of algorithms; we empirically analyzed and evaluated the performance of all the approaches presented. This dissertation introduces algorithms and insights for OA algorithms to scale up for large ontologies and efficiently align them.