The OKKAM initiative1 has recently highlighted the need of moving from the traditional web towards a \web of entities", where real-world objects descriptions could be retrieved, univocally identi ed, and shared over the web. In this paper, we propose our vision of the entity recognition problem and, in particular, we propose methods and techniques to capture the \identity" of a real entity in the Semantic Web. We claim that automatic techniques are needed to compare di erent RDF descriptions of a domain with the goal of automatically detect heterogeneous descriptions of the same real-world objects. Problems and techniques to solve them are discussed together with some experimental results on a real case study on web data.
The Semantic Web is a web of data2, but, we could add, it is (or should be)
also a web on entities. In the Semantic Web context, people and organizations
provide a explicit and semantically rich descriptions of their contents on the web,
enabling human and machine interaction as well as data integration. In doing
this, concrete and abstract real-world entities (e.g., persons, products, locations)
are searchable on the web by exploiting their RDF descriptions. But, obviously,
people perceive and describe the same real entity in many di erent ways. The
risk of this is to produce the so-called \archipelago of semantic islands" [
We call individual any abstract or concrete entity in a domain of interest. When a domain is described by a formal representation of its contents, we do not have a direct knowledge of the individuals per se, but only a set of descriptions or perceptions of these individuals. A domain representation is seen as a set of descriptions. A description is an arbitrary set of assertions about domain objects and data values speci ed according to a formal language and a data model. In this respect, the problem of individual identi cation is de ned as: 1. the problem of detecting, out of the several assertions that characterize a description, those assertions which denote a speci c individual in the domain; 2. the problem of detecting, out of several descriptions in a domain representation, those descriptions which denote the same individual in the domain. A domain representation is provided according to a formal language and a data model. Data provided in the model can be typed and featured by a well de ned semantics (e.g., DL ontologies), structured by a relational or object-oriented model (e.g., relational or object-relational databases), or organized as potentially untyped graphs (e.g., RDF, RDFS). We assume to generalize domain representations as RDF untyped graphs, where nodes denote objects or atomic data and edges denote labeled binary relations. To give an example of individual representations, let us suppose to represent a DVD collection. Two examples of RDF individual descriptions are the following ones:
Description 1 h#d01i h#titlei scarface h#d01i h#directori Brian De Palma h#d01i h#actori Al Pacino h#d01i h#actori Michelle Pfei er h#d01i h#pricei 14.99
Description 2 h#d01i h#titlei scarface h#d01i h#directori h#d02i h#d02i h#namei Brian De Palma h#d01i h#actori h#d03i h#d03i h#namei Al Pacino h#d01i h#actori h#d04i h#d03i h#namei Michelle Pfei er h#d01i h#pricei 14.99 Intuitively, we have in both cases a description of a DVD (i.e., d01) and some data about it. But, how many di erent individuals are represented in the two descriptions? Which properties are referred to which individual? How can we detect individuals here? We can maybe agree on the fact that, in both cases, ve real individuals are represented: four concrete individuals (i.e., the DVD, the persons Brian De Palma, Al Pacino and Michelle Pfei er) and an abstract individual (i.e., the movie \Scarface"). But we have di erent properties in the two cases: title is an attribute of the DVD or an attribute of the movie \Scarface", or both? Moreover, persons have a name in the second representation, but no attributes in the rst. Finally, supposing to have a correct identi cation of individuals in the two cases, how are we supposed to match these two di erent representations? We can try to address these questions by splitting the Identity Recognition Problem into three sub-problems: 1. Individuals identity and essence: what is an individual and how it is identied? 2. Individuals description: how to compare two di erent descriptions of the same individual? 3. Individuals existence: how to deal with the fact that some individuals descriptions \contain" descriptions of other individuals? When an individual has an independent existence? In the following sections we try to formalize these problems and sketch possible techniques to address them. 2.1
A Real Case Study In order to test and discuss the techniques proposed in this paper over real data, we created a case study using data about DVDs provided by the Amazon.com web service3 together with data provided about movies by the IMDB database4. The goal of our test case is to identify movies out of these datasources. For what concerns Amazon, movie identi cation is not trivial, because data describe DVD editions of the movies and not the movies per se. Thus, we want to cluster together DVDs referring to the same movie and to extract out of DVD descriptions the movie description (i.e., extraction). In our ideal case, a user who is going to create a RDF movie collection would be able to get a reference to \Scarface" by automatically exploring the Amazon DVD collection. On the other side, IMDB provides data about movies. In such a case, the goal is to compare IMDB movie descriptions with movie descriptions extracted from Amazon, in order to automatically identify di erent descriptions referred to the same real movie (i.e., mapping). These two goals are graphically presented in Figure 1.
4 http://imdb.com/. Despite the fact that IMDB is an Amazon.com company, data provided by the two services are very di erent, at least with respect to the user query. Scarface (Widescreen Anniversary Edition)
DVD 2003 Scarface (Platinum Edition)
DVD 2006
Extraction Scarface (1983)
Identification
Scarface (1932) ? Scarface (1983)
Scarface (1932) aka: Scarface, the Shame of the Nation
Scarface (1982) - TV
Scarface DVD 2003
"Scarface" Scarface (1928)
us.imdb.com
In order to evaluate our techniques, we manually built a set of expected results. From Amazon, we got data resulting for the query \Scarface" over the DVDs collection. Results contain 87 items (describing videos and DVDs). Manually, we categorized these items with respect to the related movie: we obtained 15 DVD editions of the movie \Scarface (1983)", 4 of the movie \Scarface (1932)", 6 DVD collections including the movie \Scarface (1983)", 11 of the movie \Mr. Scarface (1976)", 4 of the movie \Captain Scarface (1953)" and 47 DVD editions of other movies/materials not directly related to the query \Scarface". Concerning IMDB, we collected 27 movies, including the ones in Amazon and others. Finally, we imported data into two very simple RDF schemas, with the goal of preserving as much as possible the original structure of data provided by the two resources. A portion of resulting RDF is shown in Figure 2. 3
In general, when looking at a real individual we focus on some of its properties
in order to distinguish it from other individuals. However, not all the individual
properties can be used to perform such a distinction. In the Aristotelian theory of
de nition, some properties are considered as part of the individual essence, some
h#item-2i h#titlei Scarface, Special Edition
h#item-2i h#directori Brian De Palma
h#item-2i h#actori Al Pacino
h#item-2i h#formati PAL
h#item-2i h#hasLanguagei h#L06i
h#L06i h#namei Spanish
h#M-01i h#titlei Scarface (1983)
h#M-01i h#directori h#P04i
h#M-01i h#casti h#C06i
h#P04i h#namei Brian De Palma
h#P04i h#birthi 11-09-1940
h#C06i h#actori h#P16i
h#C06i h#characteri Tony Montana
h#P16i h#namei Al Pacino
other are just \accidental" attributes. Borrowing this intuition, we can assume
that, given an individual description Do = fA0; A1; : : : ; Ang as a set of assertions
about an individual o, the identi cation Io of o is an identity function Io(Do) !
f(di; vi)g which associates to each group of assertions in Do an identi cation
strength vi in the range [
De nition 1. Identity Function. Given an individual description D = fA0; A1;
: : : ; Ang, the Identity Function I(D) ! f(di; vi)g is de ned as follows:
8di 2 P(D); di ! vi
where P(D) denotes the power set of D, di denotes a possible subset of assertions
in D, while vi is a measure (in the range [
Implementation of the Identity Function The identity function can be obtained in three di erent ways: 1. by taking into account schema constraints when available (e.g., functional properties in DL, key constraints in relational databases); 2. by taking into account domain speci c information or human suggestions (e.g., ISBN codes for books, personal identi cation numbers for persons, manual con guration of an identity recognition system); 3. by exploiting statistical techniques over data values. Usually, the idea behind these techniques is that assertions with a high number of di erent values are more useful for identi cation than assertions with a high number of similar or equal values.
In HMatch, identifying properties can be manually chosen or automatically detected by taking into account, for each group of assertions d 2 D, the number tNh6=de goifvedni oenreen.tMvoarleuefosrrmetarlileyv,egdivfeonr adniinndailvlitdhuealinod, iwviedtuaaklse oinfttohaecscaomunet ttyhpeeseotf O of all the individuals of the same type of o in the RDF description. Then, we calculate the identity function as follows: 8di 2 P(D); di !
N=di
6 j OP j where N6=di is the number of di erent values of the assertions di over the set O, while j OP j is the number of di erent properties featuring the individuals in O. Example. To see how the function works, let us suppose to have three simple movie descriptions: h#M01i h#titlei Scarface h#M02i h#titlei Scarface h#M03i h#titlei Testament h#M01i h#yeari 1983 h#M02i h#yeari 1932 h#M03i h#yeari 1983 h#M01i h#genrei Crime
By taking into account all possible subsets of movie properties, the results of the identi cation function is shown in Table 1.
Looking at the results, we can see how the function does not take into account properties with missing values, because they do not provide useful information. Moreover, the title or the year are not useful if we consider them separated, but they are enough to identify movies when taken into account in combination. 4
The same individual can be described in many di erent ways. Descriptions of the same individual can be di erent for several reasons, including the use of di erent languages or data models and a di erent conceptualization of the same domain. The use of a generalized RDF model does not avoid the presence of heterogeneous descriptions of the same individual. Thus, a key requirement in individual identi cation is the capability of comparing heterogeneous descriptions of the individuals in order to cluster together similar or matching descriptions. Given an individual o and two descriptions Do1 = fA0; A11; : : : ; Ang and 1 1 Do2 = fA0; A12; : : : ; A2mg of o, the identi cation Io of o is a matching function 2 Io(Do1; Do2) ! (D1;2; v). Goal of the function Io(Do1; Do2) is to understand when two descriptions denote the same real individual in the domain. De nition 2. Matching Function. Given two individual descriptions D1 and D2, the matching function I(D1; D2) is de ned as follows:
I(D1; D2) ! (D1;2; v);
where v is a measure in the range [
Implementation of the Matching Function
A typical implementation of the matching function is based on the idea of
comparing the data values associated with a given individual. But, since di erent
descriptions may have a di erent structure, how can we know which graph nodes
in the two descriptions should be compared? The approach used in HMatch is to
rely on the results provided by matching the two datasource schemas. In order to
deal with highly di erent data structures, we need complex mappings between
the concepts and properties of the two schemas. HMatch itself implements
several di erent techniques for schema matching, including linguistic, structural and
contextual matching [
Example . Consider two individuals item-1 and M-01 representing di erent RDF descriptions of the movie Scarface (Figure 3). item-1 describes a DVD sold by Amazon while M-01 describes directly the movie.
Amazon item
First of all we suppose to have the following set of mappings at schema level
produced by a schema matching tool: f(title,title), (director, director ), (actor,
actor.name), (theatricalReleaseDate, Year )g. These mappings reduce the nested
structure of the M-01 description to a at one, making the M-01 description
more comparable with the one of item-1. For each pair of properties involved
in a mapping, HMatch compares the two values by means of a matching
function speci c for the category of the property (e.g. person name, date), which
produces a similarity measure in the range [
Having a reasonable threshold value of 0.6, the two individual descriptions are considered similar, which is correct since they are referred to the same movie. 5
In the two previous sections, we assumed to work with individual descriptions.
But, a description is just an arbitrary collection of assertions. So, the problem
here is: how can we select the minimal set of assertions describing an individual?
In other terms, we could also wondering if there is a method to identify an
autonomous individual out of a domain representation. The most simple intuition
here is to consider all the assertions having the same domain object as subject.
This method can be easily generalized to cope with more nested graph structures,
by taking into account all the assertions that are directly or indirectly connected
with a domain object. However, this approach is not su cient in many cases.
This problem can be introduced by looking at the example of Figure 4. The two
descriptions in the example represent two di erent DVD editions of the same
movie. This means that there is a real individual (i.e., the movie \Scarface")
which is not represented by a speci c description. In general, a good design of
the source schema should avoid this anomalies, but in real data it happens very
often to have individuals that are \hidden" into descriptions of other individuals.
For example, when talking about books, movies, music works and other kind of
abstract individuals, it happens that the work is not distinguished from its
physical edition. Also in other domains this is a problem: we have persons descriptions
hidden into business transaction descriptions, geographical locations hidden into
travel descriptions, and so on. How can we deal with this kind of individuals?
In this context, the identity Io of an hidden individual o is a discovery function
Io(D) ! f(di; vi)g which is de ned as follows:
De nition 3. Discovery Function. Given an arbitrary description D, the
discovery function Io(D) ! (di; vi) is de ned as:
where di denotes a possible subset of assertions of D and vi (in the range [
D(di) = di + vi: In such a way, we consider the subset with the best balance between the number of properties and the number of matching values over its properties as the set of properties candidate to denote an autonomous individual description within a description of other individuals.
Example. As an example, we take into account the example of Figure 4. Matching description 1 against description 2, we obtain the following mappings: f(A1; A2); (E1; E2); (F 1; F 2); (G1; G2)g leading to the following subset of matching properties:
d = f#title; #director; #actorg: Since the example is very simple, it is easy to see how d is also the best candidate to denote an autonomous individual. In more complex situations, this approach can fail due to some properties in the candidate set which are in fact useless to individual discovery. However, the resulting candidate set can be used to perform matching again by considering only the properties in the candidate set, in order to verify the quality of the obtained results. A more detailed discussion on this is provided in the following section. 6
In order to evaluate the proposed techniques, we take into account the case study presented in Section 2.1. In particular, we have two goals: i) we want to discover movies within Amazon.com DVD data; ii) we want to compare movie descriptions discovered in Amazon.com against movies in IMDB, in order to nd di erent descriptions of the same real movies. 6.1
Discovery Test Case Concerning the rst goal, our approach for testing is to match all the DVD descriptions extracted from Amazon.com in order to nd correspondences (i.e., mappings) among DVDs containing the same movie. The ground truth has been created by manually clustering DVDs with respect to the movie and by creating the set of expected mappings. It is important to stress that the goal here is not to nd similar or equal DVDs, but DVDs, potentially di erent, with the same movie. This means that some data referred to the product, such as ISBN, is not useful to our needs. Moreover, data are quite \dirty" because they contain errors or incomplete information. Thus, we performed two preliminary operations: rst, we execute matching by considering all the properties, in order to have a measure of how the discovery works without a set of properties that denote the autonomous individual movie (Test 1); second, we manually select the set of DVD properties referred to movies, and we execute matching again. This provides a measure of how the matching works in the ideal situation, when the relevant properties denoting movies in DVD descriptions are correctly selected (Test 3). Finally, we exploited the discovery function of HMatch to automatically retrieve the relevant properties for movies and we execute the matching by considering only the relevant properties (Test 2). In order to evaluate the quality of the results we used three measures: precision, de ned as the quantity of retrieved mappings that are correct, and recall, de ned as the quantity of correct mappings that are retrieved, and F-Measure which is the harmonic mean of the two. Results are shown in Table 2, where, for each Test, we provide two measures in the form X (Y), where X is the absolute value of precision or recall, while Y is the value of precision and recall with respect to the ideal matching case (Test 3).
The results show how matching over all the DVD properties is useless with
respect to the goal of discovering movies. In fact, many DVD are similar
because of properties like the format which is not relevant neither for the DVD
identi cation nor for the movie identi cation. So, this method (Test 1) produces
a high number of mappings, leading to a high recall with a very low precision.
On the other way, manual selection of properties (Test 3) produces the best
results that can be obtained by using matching for movie discovery. These
results are characterized by a good precision and an average recall. This means
that when we collect together DVDs with the same movie, it is quite probable
that the collection is correct, even if some DVD is missing. The results obtained
with the discovery function (Test 2) are promising because, despite the fact that
the method is completely automatic, we obtained quite good precision and recall
results, especially if compared with the ones obtained with the manual approach.
The matching test case has been executed by taking onto account data
extracted from Amazon together with data provided by IMDB. The goal here is
to evaluate in terms of precision and recall the quality of the results obtained
using HMatch for individual comparison. In particular, we want to check if our
instance matching techniques are suitable for automatically retrieve di erent
descriptions denoting the same real entity (i.e., a movie). The ground truth has
been de ned by manually comparing the 27 movies retrieved in IMDB against
the 87 DVDs retrieved on Amazon for the query \Scarface". In particular, we
have manually mapped each movie with all the DVDs containing that movie.
Then, we have executed HMatch by taking into account only the properties
selected in the previous discovery test (Test 2). The results in terms of precision,
recall and F-Measure are shown in Table 3.
In the paper, we have seen how instance matching techniques are crucial for
solving the identity recognition problem by exploiting automatic techniques.
In general, instance matching is frequently referred to as an Entity Resolution
problem (also called Deduplication or reference reconciliation) and it is de ned
as the process of identifying and merging records judged to represent the same
real-world entity. Up to now, the instance matching problem has been recognized
as particularly relevant in database and data integration applications where it
is referred to as record linkage and it is de ned as the task of quickly and
accurately identifying records corresponding to the same entity from one or more
data sources [
A rst important category of approaches to record linkage rely on statistical
theories and techniques. In particular the problem is translated in a Bayesian
inference problem [
In the Semantic Web the attention on instances for the purpose of ontology
matching has been poorly studied and only basic techniques for ontology instance
matching have been proposed. For example, in [
In this paper, we have discussed the problem of identity and entity recognition in the semantic web, by presenting three main sub-problems and by providing speci c techniques to solve them. Our thesis is that instance matching and related techniques can be used to support entity recognition by enabling the automatic discovery of \hidden" entities as well as the automatic comparison of di erent descriptions of the same real-world objects. To this end we have presented promising experimental results. Concerning scalability, which is a crucial issue for semantic web applications, we are currently performing tests with larger datasets and our future work will be focused on optimization of the algorithms in terms of computational performances. Moreover we are collecting more experimental data in the BOEMIE European Project 5, where instance matching is used with the purpose of retrieving descriptions of the same entities over semantic data extracted from multimedia resources. BOEMIE provides methods and techniques for knowledge acquisition from multimedia content, by introducing the notion of evolving multimedia ontologies, which is used for the extraction of information from multimedia content in networked sources. In particular, multimedia resources are analyzed with the goal of providing a semantic description of their content. The result of this process is the population of an OWL ontology. In the process of population, di erent instances created from di erent resources are grouped together if they denote the same real-world object. Our current and future work in the project is to investigate, develop and test advanced instance matching techniques as a support for ontology population.