INCREMENTAL MAINTENANCE OF ONTOLOGIES BASED ON BIPARTITE GRAPH MATCHING

Preetpal Singh, Kalpdrum Passi

2009

Abstract

Today’s Information Society demands complete access to available information, which is often heterogeneous and distributed. A key challenge in building the Semantic Web is integrating heterogeneous data sources. This paper presents an incremental algorithm for maintaining integration in evolving ontologies. For example, an increased number of smaller, task oriented ontologies, are emerging across the Bioinformatics domain to represent domain knowledge; integrating these heterogeneous ontologies is crucial for applications utilizing multiple ontologies. Most ontologies share a core of common knowledge allowing them to communicate, but no single ontology contains complete domain knowledge. Recent papers examined integrating ontologies using bipartite graph matching techniques. However, they do not address the issue of incrementally maintaining the matching in evolving ontologies. In this paper we present an incremental algorithm, OntoMaintain, which incrementally calculates the perfect matching among evolving ontologies and simultaneously updates the labels of the concepts of ontologies. We show that our algorithm has a complexity of O(n2) compared to complexity O(n3) of traditional matching algorithms. Experimental results prove that our algorithm maintains the correctness of a ‘brute force method’ while significantly reducing the time needed to find a perfect matching in evolving ontologies.

Paper Citation

in Harvard Style

Singh P. and Passi K. (2009). INCREMENTAL MAINTENANCE OF ONTOLOGIES BASED ON BIPARTITE GRAPH MATCHING . In Proceedings of the Fifth International Conference on Web Information Systems and Technologies - Volume 1: WEBIST, ISBN 978-989-8111-81-4, pages 444-449. DOI: 10.5220/0001843904440449

in Bibtex Style

@conference{webist09,
author={Preetpal Singh and Kalpdrum Passi},
title={INCREMENTAL MAINTENANCE OF ONTOLOGIES BASED ON BIPARTITE GRAPH MATCHING},
booktitle={Proceedings of the Fifth International Conference on Web Information Systems and Technologies - Volume 1: WEBIST,},
year={2009},
pages={444-449},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001843904440449},
isbn={978-989-8111-81-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Fifth International Conference on Web Information Systems and Technologies - Volume 1: WEBIST,
TI - INCREMENTAL MAINTENANCE OF ONTOLOGIES BASED ON BIPARTITE GRAPH MATCHING
SN - 978-989-8111-81-4
AU - Singh P.
AU - Passi K.
PY - 2009
SP - 444
EP - 449
DO - 10.5220/0001843904440449