Linked data interlinking is the discovery of all instances that represent the same real-world object and locate in di erent data sources. Since di erent data publishers frequently use di erent schemas for storing resources, we aim at developing a schema-independent interlinking system. Our system automatically selects important predicates and useful predicate alignments, which are used as the key for blocking and instance matching. The key distinction of our system is the use of weighted co-occurrence and adaptive ltering in blocking and instance matching. Experimental results show that the system highly improves the precision and recall over some recent ones. The performance of the system and the e ciency of main steps are also discussed.
Years of e ort in building linked data has brought a huge amount of data in the LOD. However, maximizing the e ciency of linked data in the development of semantic web is still facing many di culties. One of the current challenges is to integrate the individual data sources for building a common knowledge system. When di erent data source may contain heterogeneous instances, which co-refer to the same real-world objects, data integration process requires the detection of such objects to ensure the integrity and consistency of data. Detecting all identities between data sources is the mission of data interlinking. Data interlinking consist of two main steps, blocking and instance matching. While blocking aims at pruning the number of comparison, instance matching is to determine the matching status of two interested instances.
Current interlinking methods can be categorized into two main groups:
schemadependent [
We present SLINT system, which use a new approach for schema-independent linked data interlinking. SLINT automatically selects important RDF predicates using the coverage and discriminability. The selected predicates are combined to construct the predicate alignments in conciliation of data type. We estimate the con dence of predicate alignments to collect the most appropriate alignments for blocking and interlinking. By this way, the collective information of instance is frequently leveraged. Blocking is therefore more complete, compact, and supportive for interlinking. Also, we apply adaptive ltering techniques for blocking and instance matching. In experiment, we compare SLINT with three systems, which participated OAEI 2011 instance matching campaign, and report the high improvement on both precision and recall. Experiments on the performance of SLINT and the e ciency of blocking step are also reported.
The paper is organized as follow: the next section is the overview of previous work. Section 3 describes the detail of SLINT system. Section 4 reports our experimental evaluation. Section 5 closes the paper with conclusion and outlook.
Data interlinking is an early studied area, however, this problem in linked data
has just been recently attended. Silk [
Zhishi.Links [
Most of previous interlinking systems do not deeply investigate on blocking
step, which generates potential identity pairs of instances. Song and He n focus
on blocking scheme for linked data interlinking for parallel independent work [
In general, the schema-dependent approaches compare two instances by speci ed properties. That is, they can detect almost right identity pairs but the precision may be low on highly ambiguous data sources. The reason is that some useful information can be ignored since the manual predicate alignment frequently is not an optimal solution. In contrast, schema-independent approaches reconcile precision and recall because of elaborate analysis on the data. Although these approaches need to collect predicate alignments, the matching is more e ective when collective information is frequently used. Comparing SLINT with previous interlinking systems, the prominent di erences are the predicate selection, predicate alignment, and adaptive ltering for blocking and interlinking. In the next section, we describe these elements as the details of SLINT. 3
This section describes the SLINT system. The overview of the interlinking process for source data Ds and target data Dt is shown in Figure 1. In this gure, the small circles and triangles respectively stand for instances and theirs RDF predicates. The referred circles of each step are the output of that step. The SLINT system consists of four steps. The interlinking process begins with predicate selection, which collects the important predicates from all predicates of each data sources. In the second step, predicate alignment, selected predicates are combined in accordance with their data type to construct the raw predicate alignments. We estimate the con dence of every raw alignment to measure its appropriateness. A raw alignment will be called a key alignment if its con dence satis es a ltering condition. These key alignments provide much useful information in blocking and instance matching steps. Next, blocking step is designed to reduce the number of comparison by producing identity candidates of instances. The instance matching afterward only need to veri es the retrieved candidates for discovering the identity pairs. The followings are the detail of each step.
The mission of this step is to nd the important predicates from the schema, which consists of all predicates appearing in interested data source. We use two criteria for determining the importance level of predicate p: coverage cov(p; D) and discriminability dis(p; D). Eq.1 and Eq. 2 are the explanations of these criteria when considering predicate p of data source D.
cov(p; D) = jfxj9 < s; p; o >2 x; x 2 Dgj : jDj (1) dis(p; D) = jfoj9x 2 D; < s; p; o >2 xgj : (2) jf< s; p; o > j9x 2 D; < s; p; o >2 xgj
In these equation, x represents an instance and is a set of RDF triple <
s; p; o > (subject, predicate, object). D is the interested data source and is a
set of instances. From each input source, we collect the predicates having high
score of coverage and discriminability. A predicate p is selected if it satis es the
condition in Eq.3, which inherits from the idea of [
(cov(p; D) ) ^ (dis(p; D) ) ^ (HM ean(cov(p; D); dis(p; D)) ): (3)
The and imply the minimum standard of an important predicate, whereas , the condition for harmonic mean of dis(p; D) and cov(p; D), is the main requirement. Therefore, we set small values for and and larger value for .
Song and He n focus on learning blocking key by iteratively maximize the
coverage and discriminability of the set of predicates [
Important predicates are expected to be used for declaring the common properties and distinct information of objects. Since coverage and discriminability respectively express the former and latter, the combination of them is therefore appropriate for the objective of predicate selection. If a predicate has a high coverage but a low discriminability or otherwise, it will not be important. An example for this kind of predicate is rdf:type. This predicate is frequently used but it usually describes a limit range of various RDF objects when observing the instances in the same domain.
In this step, we nd the appropriate alignments of predicates between the source data and target data. An alignment of two predicates is considered to be appropriate if the interested predicates describe the similar properties of instances. From selected predicates of source data and target data, we connect every typematched pair and select the alignments whose con dence is higher than threshold . Selected predicate alignments are called key alignments. The con dence of an alignment is the Dice coe cient between the representatives of RDF objects described by its formed predicates. Eq. 4 is the equation of con dence conf (ps; pt) for the alignment between predicate ps in source data Ds and predicate pt in target data Dt.
conf (ps; pt) = 2 jR(Os) \ R(Ot)j ; Ok = foj9x 2 Dk; < s; pk; o >2 xg: (4) jR(Os)j + jR(Ot)j
In above equation, R is the function that returns the representative elements of RDF objects. The return values of R depend on the type of predicates. We divide the predicates into ve di erent types: string, URI, decimal, integer, and date. This separation is based on the variety of data types in the real world and covers most of current types of linked data. For string, we extract the word token of RDF objects. For URI, we omit the domain part and use the same manner as for string, with the assumption that slash `/' is the token separator. For decimal, we take the 2-decimal digits rounded values. For integer and date, we do not transform the RDF objects and use the original values. For determining type of a predicate, we use the major type of RDF objects declared by this predicate. For example, if 51% appearance times of p is to describe decimal values, the data type of p will be decimal. Currently, we detect the type of RDF objects without the consideration about the di erence in their metric (e.g. the units of time, distance, area).
The con dence of an alignment represents the similarity of RDF objects between two data sources. The predicates having the same meaning frequently describe the similar information. Therefore, alignments of matched predicates usually have higher con dence than the others. It means that a predicate satisfying the requirements of an important predicate is veri ed again, by considering the con dence of all alignments in which it appears. For example, the predicate rdfs:comment has possibility to be important but the con dences of its alignments are usually low because the denominator of Eq.3 is very high in this case.
A common limiting point of almost previous systems is the use of string measurement for every type of RDF objects. Clearly, this approach is not su cient to cover the meaning of RDF objects, thus, does not well estimate the similarity of non-string values. We discriminate data types not only in combining predicates, but also in blocking and instance matching.
It is not easy for a person to detect all useful predicate alignments, this step is therefore very meaningful, and in accompaniment with predicate selection, it tackles the schema-independent goals. The next steps are the use of selected key alignments and their formed predicates.
As we introduced, the blocking aims at retrieving the candidates for instance matching step by grouping similar instances into the same block. A candidate is a pair of two instances, one belongs to source data and one belongs to target data. The blocking can be divided into three sub phases. The rst phase indexes 8 9 10 11
Algorithm 1: Generating candidates set
Output: Candidate set C 1 H
; 2 M [jDsj; jDtj] f0g 3 C ; 4 foreach < D; P >2 f< Ds; P rs >; < Dt; P rt >g do 5 foreach x 2 D do 6 foreach pi 2 P do 7 sumConf Ppj2fP rs;P rtgnP conf (pi; pj) foreach r 2 Rp(O); O = foj < s; pi; o >2 xg do if not H.ContainsKey(r:Label) then
H.AddKey(r:Label) H.AddValue(r:Label, D, < x; r:V alue sumConf >) 12 foreach key 2 H.AllKeys() do 13 foreach < xs; vs >2 H:GetV alues(key; Ds) do 14 foreach < xt; vt >2 H:GetV alues(key; Dt) do 15 M [xs; xt] M [xs; xt] + vs vt every instance in each data source by the value extracted from its RDF objects. The second phase traverses the index table and builds a weighted co-occurrence matrix. The nal phase uses this matrix as the input information when it applies a ltering technique to select candidates. Algorithm 1 is the pseudo-code of the whole blocking process. In this algorithm, P rs and P rt represent the list of predicates that form the key alignments, where P rk belongs to Dk. H, M , C, Rp represent the inverted-index table, weighted co-occurrence matrix, candidates set, and representative extraction method, respectively.
The lines 4-11 perform the invert-indexing, a well-known indexing technique. By once traversing each data source, we extract the representatives of RDF objects and use them as the keys of invert-index table. An element r in the representatives set of RDF objects consists of two elds: the label r:Label and value r:V alue. While r:Label is the return value of representative extraction method R as in predicate alignment step, r:V alue is computed in accordance with the data type of predicate pi. If pi is string or URI, we set the value to TF-IDF score of the token. If pi is either decimal, integer, or date, we assign the value to a xed number, which is 1.
After constructing the invert-index table, we compute weighted co-occurrence matrix M as the lines 12-15, by accumulating the value for each matrix element.
The lines 16-22 are the process of adaptive ltering. An instance pair < xs; xt > will be considered as a candidate if its weighted co-occurrence value M [xs; xt] satis es the threshold , after divided for the harmonic mean of maximum weighted co-occurrences of xs and xt. In addition, we use , a small threshold, to avoid the surjection assumption. The identities frequently have the high weighted co-occurrences; however, these values are variable for di erent pairs. Choosing a xed threshold for selecting candidates is not good in this situation and is a tedious task. Therefore, we use the coe cient of M [xs; xt] and max, which is a data driven element and expresses the adaptive ltering idea.
Blocking is very important because it reduces the number of comparison in
instance matching. However, it seems not to have been su ciently attended when
most of previous systems use quite simple method for blocking. In comparison
with blocking step in previous interlinking systems, the key di erence of our
method is the weighted co-occurrence matrix and the adaptive ltering. While
previous systems compare the pairs of RDF objects, we aggregate the product
of the weight of their matched representatives. For candidate selection, Silk [
Next, we input the set of candidates C and the key alignments A into the nal step, instance matching.
The instance matching veri es the selected candidates to determine their identity state. We compute the matching score for every candidate and choose the ones that have high score as the identity pairs. For each element in A, we compute the similarity of RDF objects, which declared by the involved predicates of interested key alignment. The nal score of two instances is the weighted average value of all these similarities, and the weights are the con dences of key alignments. Eq.5 is the computation of matching score between instance xs 2 Ds and xt 2 Dt. score(xs; xt) = 1 X conf (ps; pt) sim(R(Os); R(Ot));
W
<ps;pt>2A
Ok = foj9x 2 Dk; < s; pk; o >2 xg
X
conf (ps; pt): In this equation, R stands for the representative extraction methods, which are similar to those in predicate alignment step.
Categorizing ve data types, we implement three di erent versions of sim function in accordance with the type of predicates. For decimal and integer, we take the variance of the values to remedy the slight di erence of data representations. For date, the sim function yields 1 or 0 when the values are equal or not, respectively. A date is usually important if it is a property of the object (e.g. birthday, decease date, release date of a movie). Therefore, the exact matching is an appropriate selection for dates comparison. For string and URI, we compute the TF-IDF modi ed cosine similarity, as given in Eq.6. TF-IDF is used because its advantage in disambiguating the instances sharing common tokens. TF-IDF also minimizes the weight for the stop-words, which are usually useless. sim(Qs; Qt) =
Pq2Qs\Qt T F IDF (q; Qs)T F IDF (q; Qt) qPq2Qs T F IDF 2(q; Qs)
Pq2Qt T F IDF 2(q; Qt) Similar with blocking step, we do not use xed single threshold for ltering the candidates. Two instances will be considered as an identity pair if their score is higher than the maximum score of the candidates in which either of instances appears. The nal identities set I is formalized in Eq.7.
I = f< xs; xt > jscore(xs; xt)
^ score(xs; xt) max8<xm;xn>2C;xm xs_xn xt score(xm; xn) g: (7) An identity pair is expected to be the highest correlated candidate of each instance. However, it usually is not true because the ambiguity of instances. A thresholding method that relies on the highest score would be better in this situation. While true identity pair and its impostors have the similar score, is assigned with a quite large value. On the other hand, is additionally con gured as the minimum requirement of an identity. Like in Algorithm 1, ensures there is no assumption about the surjection of given data sources.
The key distinctions of our approach in comparison with the previous are the
use of weighted average and adaptive ltering. Previous systems do not have the
data driven information like con dence of key alignments. Silk [
We evaluate the e ciency of blocking step and the whole interlinking process
of SLINT. We also compare SLINT with Zhishi.Links [
Like previous studies, for blocking, we use two evaluation metrics: pair completeness (PC) and reduction ratio (RR); For interlinking, we use recall (Rec), precision (Prec), and F1 score, the harmonic mean of recall and precision. Eq.8 and Eq.9, Eq.10, and Eq.11 are the computations of used metrics.
P C =
(8) (9) (10)
P rec = : (11)
The performance of an interlinking system is also very important. We report the execution times of SLINT when running on a desktop machine equipped with 2.66Ghz quad-core CPU and 4GB of memory.
We use 9 datasets in experiment. The rst 7 datasets are IM@OAEI2011 datasets, the ones used in instance matching campaign at the OAEI 20113. Concretely, we use the datasets of interlinking New York Times track, which asks participants to detect identity pairs from NYTimes to DBpedia, Freebase, and Geonames. These datasets belong to three domains: locations, organizations, and people. The IM@OAEI2011 datasets are quite small. Therefore, for evaluating the computational performance of the system, we select two larger datasets. The rst one, a medium dataset, contains 13758 pairs in lm domain between DBpedia and LinkedMDB4. The second one is a quite large dataset, which contains 86456 pairs in locations domain between DBpedia and Geonames5. All datasets are downloaded by dereferencing URI and stored in external memory in advance. We remove triples having owl:sameAs predicates and rdf:seeAlso predicates of course. Table 1 gives the overview of these datasets. In this table, IM@OAEI2011 datasets are from D1 to D7, and the last two datasets are D8 and D9. We also include the number of predicates and predicate alignments in this table. Denotes that s and t are the source and target data, respectively; P rd and P fd are the 3 http://oaei.ontologymatching.org/2011/instance/ 4 http://downloads.dbpedia.org/3.7/links/linkedmdb links.nt.bz2 5 http://downloads.dbpedia.org/3.7/links/geonames links.nt.bz2 number of predicates in data source d before and after selected by predicate selection step, respectively; A and K are the number of all predicate alignments and only key alignments, respectively.
In general, excepts in NYTimes, the number of available predicates in the schema of each data source is very large, but the important predicates occupy a very small percent. As our observation, the predicates declaring the label or the name of objects are always aligned with a very high con dence. The non-string type predicates also frequently construct the key alignments. For example, in locations domain, the key alignments always contain the right combination of predicates declaring latitudes and longitudes. The predicate releaseDate of DBpedia is successfully combined with predicate date and predicate initial relase date of LinkedMDB. An interesting key alignment in dataset D6 is the high con dence combination of core#preLabel of NYTimes and user.mikeshwe.default domain.videosurf card.videosurf link text of Freebase. The latter predicate may be di cult for manual selection since the meaning of the predicate name does not imply the label. Clearly, it is not easy for human to detect every compatible predicates. When manually doing this task, we may lose to leverage all useful information.
This section reports the result of blocking and the whole interlinking process. Concretely, we report the pair completeness and reduction ratio of blocking, and precision, recall, F1 score, and the runtime of the system. Table 2 shows these metrics on each dataset. According to this table, although we cannot retain all identity pairs, the lowest PC is still very high at 0.94. Besides, the high RRs reveal that the numbers of retrieved candidates are very small if compared with the numbers of total pairs. For all the evidences of PC and RR, the aim of blocking is successfully achieved.
For interlinking, the precison and recall are very competitive. The recall, which is not much lower than pair completeness, implies that the instance matching performs a good work. The high precision implies that our system has a efcient disambiguation capability on tested datasets. It seems easy for SLINT to interlink people domain, whereas in locations domain, SLINT achieves the best result on IM@OAEI2011 datasets involving with Geonames.
The execution time of SLINT is very good in overview. Because we use cooccurrence structure in blocking, the memory on tested machine cannot satisfy Dataset D1 D2 D3 D4 D5 D6 D7 D8 D9 a very large dataset. In our context, interlinking dataset D9 has such issue. We temporarily implement a parallel program for re-computing every element of the co-occurrence matrix. The interlinking on this dataset is therefore takes much time because the repeat of data traversing and high computational cost. However, the high speeds on other datasets are really promising for scaling-up our system.
The advantage of blocking is very high if we compare the time of interlinking with and without this step. For example, the time for instance matching step to match 33926 candidates of dataset D8 is 12.2 seconds. It means that the time for matching all available pairs will be nearly 17 hours, whereas this number is only 67.76 seconds in total if we implement the blocking step. Blocking averagely occupies 58% total runtime of interlinking process on the nine tested datasets. Although this number is over a half, the advantage of blocking is still very considerable.
As mentioned, we compare our system with AgreementMaker [
The prominent di erences of SLINT and these systems are that we use the con dence of alignment as the weight for blocking and instance matching, and discriminate data types with the use of TF-IDF for the token of string and URI. Generally, SLINT is veri ed as the best accurate one among compared systems.
In this paper, we present SLINT, an e cient schema-independent linked data interlinking system. We select important predicates by predicate's coverage and discriminability. The predicate alignments are constructed and ltered for obtaining key alignments. We implement an adaptive ltering technique to produce candidates and identities. Compare with the most recent systems, SLINT highly outperforms the precision and recall in interlinking. The performance of SLINT is also very high when it takes around 1 minute to detect more than 13,000 identity pairs.
Although SLINT has good result on tested datasets, it is not su cient to evaluate the scalability of our system, which we consider as the current limiting point because of the used of weighted co-occurrence matrix. We will investigate about a solution for this issue in our next work. Besides, we also interested in automatic con guration for every threshold used in SLINT and improving SLINT into a novel cross-domain interlinking system.