representation of an instance that is the aggregate of a cluster of matched instances. We believe that this model will prove f exible enough to handle sparse instance data and can improve the accuracy of the knowledge model over time.
Though consolidation has been researched in other domains, such as the database domain, it is less explored in the Semantic Web domain. In relation to coreference resolution (also known as instance matching and entity resolution), once two instances or entities are designated as the same or coreferent, they are tagged in some way (using owl:sameAs) or consolidated into a single entity using various approaches. What has received less attention is how to merge instances with conf icted information and how to adapt consolidations over time. In this paper we describe our ongoing work that supports instance consolidation by grouping matched instances into clusters of abstract representations. We develop our consolidation algorithm to work with incremental online coreference resolution by providing a way to improve the instance data that will be used in subsequent matching. For example, in the case of sparse instances, a consolidated representation of features would be more likely to match newly discovered instances. As more instances are added to the cluster, the representation will become more enriched and more likely to match a wider number of instances in subsequent matches. When performing subsequent instance matching that includes both clusters and individual instances, the consolidated representation of clustered data, supported by our merging algorithm, can be used.
Figure 1 depicts an example of a consolidation when conf icts may occur. In this example, when we have a pair of attributes that are the same but their values differ, to consolidate we must determine whether both values are maintained, none of the values are maintained or one of the values is maintained. For the purposes of using the consolidated instance for future matching, the merging of instance data is incredibly important as it affects the performance of future matching. This is particularly true when working with data sets that are sparse.
The temporal support is an important aspect to this problem since over time an entity’s features may change. In Figure 2, the attribute population changes over time. This example highlights two complexities that are a natural effect of time. An instance can be thought of as a snapshot in time, therefore an instance captured at time t − 1 may not be as relevant as an instance captured at time t. This affects how instances should be consolidated and is a good example of when a technique is required to resolve conf icts. Also, this implies that in certain cases, given enough time, two instances may no longer be coreferent, supporting the argument that temporal issues play a signif cant role in consolidation and subsequent processing. 2
Semantic Web data, which includes semantically tagged data represented using a
Resource Description Framework (RDF) [
The topic of instance consolidation, the process of combining instances, is not
novel. Previous research has addressed instance consolidation in relation to
merging instances that are coreferent. What has received less attention is the temporal
aspect of this problem, how to merge instances when conf icts are present and how
using this method to support incremental coreference resolution can address issues
related to spareness. For example, in Figure 3 we show two Friend of a Friend
(FOAF) [
The research that exists today, has a tendency to use a methodology that relies
upon inverse functional properties. For example, Hogan et al. [
In our person data set, specif cally using the FOAF ontology, we found a sizable percentage of the instances contained very few attributes. In Table 1, we show the number of instances originating from 3 different sources. Source ’vox’ had the highest number of instances and also the lowest number of attributes per instance. We have found this is prevalent among social networking sites and sites that support exports of user prof le data using the FOAF ontology. This is not specif c to FOAF instances and can present a problem for coreference resolution algorithms. 3
We def ne an instance as an abstract representation that can be either a cluster of coreferent instances, or a single entity instance. A formal def nition follows. Definition 1. Given a set of instances I and a set of clusters C, an abstract instance A ∈ (I ∪ C).
Definition 2. Given a pair of instances in and im, if the pair are coreferent or coref (in, im), then a cluster Cnm is formed such that the cluster Cnm = {in, im}.
A consolidated representation is required in order to use the clustered data in subsequent matching. This consolidation can be as simple as a union between the sets of attributes of instances. However, as seen in Figure 1, this approach does not address situations where attributes are in conf ict. Even in this simple example, conf icts are present that should be resolved. Our initial work includes the merging of instances and resolution of conf icts by using a basic set of rules and temporal information.
When evaluating two instances, for each attribute that is shared, if the values are equal, we retain one instance of the attribute. If two instances share the same attribute but their values differ, we try to resolve the conf ict. If the two instances contain attributes that are not shared we include their unshared attributes. In resolving the conf ict, we f rst try to determine if the two values are synonymous. If they are synonymous, we keep both values for the particular attribute. If not, then we will use additional analysis such as temporal information. As the same instance is processed over time given a particular URI, we track the changes among attributes for that instance. Given that attributes have changed for a particular instance we give the more recent values of the attributes a higher signif cance than a less recent values. We can then use this information to assist with resolving conf icts. When conf icts can not be resolved we keep both values for the unresolved attribute. We anticipate this approach will advance as we progress in our research.
Our cluster links are symbolic in nature. In order to support changes to the cluster over time, each instance in a cluster is linked and weighted to other instances in the cluster. How the weight is def ned is based on the coreference resolution algorithm. In our work, we are using a clustering algorithm to cluster instances that are thought to be coreferent. The output of our calculation that supports our clustering method will also be used as an assessment of how closely the two instances are related for consolidation. Given the set of attributes for each instance in the cluster, we associate a score with each set of matched attributes. This score can be based on a distance function or based on a more complex representation. The goal of this step is to weight common features among pairs of coreferent instances in the cluster. Across all features in the cluster we wish to pick the most signif cant features to be used for subsequent matching. We are currently exploring feature reduction mechanisms to perform this step. This structure gives us the ability to compare coreferent relationships among instances over time, to remove coreferent relationships given changes over time, or to add and modify existing relationships given new instances that are added to the cluster. 4
We have presented a need for a more adaptive-based consolidation approach. A cluster-based consolidation provides a powerful model for instance matching algorithms. It is meant to adapt to change over time, is f exible and could potentially improve subsequent matching. Given the complexities of systems today, adaptation is a necessity. The challenge is developing a consolidation approach that is f exible enough to support the complexities of systems today, without incurring a large performance penalty.