An ontology mapping extraction method based on set covering
Hongke Xia
1, 2
, Xuefeng Zheng
1
, Xiang Hu
3
and Yunmei Shi
2
1
Information Engineer Institute, University of Science and Technology Beijing
2
Computer School, Beijing Information Science and Technology University, Beijing
3
Computer Science and Technology Department, North China Electric Power University, Beijing
E-mail: hongke.xia@gmail.com
Abstract—Ontology Mapping is the foundation of semantic
query and semantic integration based on ontology. As the
crucial point of ontology mapping, the task of mapping extrac-
tion is to find whether there exists the ontology mapping
among the similarities between source ontology and target
ontology. In this paper the problem of mapping extraction is
regarded as the problem of set covering, and a novel ontology
mapping extraction algorithm based on set covering SME
(SCM-based Mapping Extraction) is proposed, by which the
property set which covers the training data set in maximum
degree is searched during training stage, and the mapping
extraction is carried out by means of the conjunction of the
properties of property set in testing data set during testing
stage. Experimental evaluations show that this method has
better comprehensive performances compared to other algo-
rithms.
Keywords—Mapping Extraction; set covering; data-dependent
ball; property spaces
I. INTRODUCTION
Among the various strategies that realized ontology
mapping, the ontology mapping based on similarity calcu-
lating is the mainstream method, which extracts the ontolo-
gy mapping after the similarities between source ontology
and target ontology are calculated. The proposed mapping
extraction method includes the selection strategy using
threshold, the selection strategy based on maximum predi-
cated value [1], the selection strategy using relaxation labe-
ling [2], and so on.
The selection strategy using threshold defines a thre-
shold, and determines whether there exist mappings among
concept couples by judging the relationship between the
similarities of concept couples and the threshold. If the
similarity of two concepts is larger than the threshold, then
there exists ontology mapping between these two concepts;
otherwise there exists no mapping. The main shortcoming
of threshold lies in how to choose the value of the threshold,
since different thresholds impact the final mapping extrac-
tion greatly, and how to choose the threshold soundly is a
problem which should be taken into account thoroughly.
The selection strategy based on maximum predicated
value sorts all the concept similarities by descending order,
and selects the concept couple with maximum similarity as
the concept couple which has ontology mapping between
them. This method can be substitute by the strategy using
threshold each other in essence, both Falcon-AQ [3] and
Rimom [4] extract the ontology mapping with this method.
Relaxation labeling is a widely used method by graphics
and image processing, nature language processing area, and
so on, and the main idea of it is that a node’s label is influ-
enced by its neighbors’, so we can deduce a node’s label by
its neighbors’ labels. In ontology mapping, the concepts of
target ontology are treated as labels, and the label which
most fits the concept of source ontology is searched by the
means of relaxation labeling. GLUE [2] extracts ontology
mapping using relaxation labeling.
In this paper a novel ontology mapping extraction me-
thod is proposed, which introduces the theory of set cover-
ing into mapping extraction, and converts the problem of
mapping extraction into the problem of set covering. This
method searches the property set, each of which covers the
training data in maximum degree, in training set, then de-
cides whether the mapping exists or not in testing set via the
property set found. The rest of the paper organizes as fol-
lows: in section 2 the related conceptions are introduced, in
section 3 the problem of ontology mapping is described and
the mapping extraction algorithm SME is presented, and
section 4 gives the results of experiment and analysis. Final-
ly section 5 concludes the paper with a discussion.
II.
THE PROBLEM OF SET COVERING
The problem of set covering has the following mathemat-
ics descriptions: suppose {X, F} consists of a finite set X
and a family of subsets F, and F covers X, in other words
every element of X belongs to at lest one subset of F, name-
ly
SF
S
∈
= ∪
. For a family of subset B which belongs to F
(
F⊆
), if
SB
S
∈
= ∪
, it is to say B covers X. The problem of
set covering is to find the minimum subset B* of F which
2009 International Conference on Web Information Systems and Mining
978-0-7695-3817-4/09 $26.00 © 2009 IEEE
DOI 10.1109/WISM.2009.46
191
Authorized licensed use limited to: Sunchon National University. Downloaded on June 07,2010 at 13:55:57 UTC from IEEE Xplore. Restrictions apply.