Inexact Matching of Ontology Graphs Using Expectation-Maximization.

TitleInexact Matching of Ontology Graphs Using Expectation-Maximization.
Publication TypeJournal Article
Year of Publication2009
AuthorsPrashant Doshi, Ravikanth Kolli, Christopher Thomas
KeywordsExpectation-maximization, Homomorphism, Matching

We present a new method for mapping ontology schemas that address similar domains. The problem of ontology matching is crucial since we are witnessing a decentralized development and publication of ontological data. We formulate the problem of inferring a match between two ontologies as a maximum likelihood problem, and solve it using the technique of expectation-maximization (EM). Specifically, we adopt directed graphs as our model for ontology schemas and use a generalized version of EM to arrive at a map between the nodes of the graphs. We exploit the structural, lexical and instance similarity between the graphs, and differ from the previous approaches in the way we utilize them to arrive at, a possibly inexact, match. Inexact matching is the process of finding a best possible match between the two graphs when exact matching is not possible or is computationally difficult. In order to scale the method to large ontologies, we identify the computational bottlenecks and adapt the generalized EM by using a memory bounded partitioning scheme. We provide comparative experimental results in support of our method on two well-known ontology alignment benchmarks and discuss their implications.

Full Text

Prashant Doshi, Ravikanth Kolli, Christopher Thomas, Inexact matching of ontology graphs using expectation-maximization, Web Semantics: Science, Services and Agents on the World Wide Web, Volume 7, Issue 2, April 2009, Pages 90-106, ISSN 1570-8268, DOI: 10.1016/j.websem.2008.12.001.
research center: LSDIS Lab, Dept. of Computer Science, University of Georgia, Athens, GA 30602, United States; Kno.e.sis Center, Dept. of Computer Science and Engineering, Wright State University, Dayton, OH 45435, United States
project: Tcruzi and SemDis
pages: 90-10
publisher: Elsevier
year: 2009
venue url:
related resource url: 10.1016/j.websem.2008.12.001
hasBookTitle: Journal of Web Semantics: Science, Services and Agents on the World Wide Web