Over the last years, time-efficient approaches for the discovery of links between knowledge bases have been regarded as a key requirement towards implementing the idea of a Data Web. A considerable portion of the information contained available as RDF on the Web pertains to persons. Thus, efficient and effective measures for comparing names are central to facilitate the integration of information about persons on the Web of Data. The Jaro-Winkler measure has been developed especially for the purpose of comparing person names. Hence, we present a novel approach for the efficient comparison of sets of strings using this measure. We evaluate our approach on several datasets derived from DBpedia 3.9 and containing up to 105 strings and show that it scales linearly with the size of the data for large thresholds. We also evaluate our approach against SILK and show that we outperform it even on small datasets.
The Linked Open Data Cloud (LOD Cloud) has developed to a compendium of more
than 2000 datasets over the last few years.1 Currently, data sets pertaining to more than
14 million persons have already been made available on the Linked Data Web.2 While
this number is impressive on its own, it is well known that the population of the planet
has surpassed 7 billion people. Hence, the Web of Data contains information on less
that 1% of the overall population of the planet (counting both the living and the dead).
The output of open-government movements,3 scientific conferences,4 health data5 and
similar endeavours yet promises to make massive amounts of data pertaining to
persons available in the near future. Dealing with this upcoming increase of the number of
person-related resources requires providing means to integrate these datasets with the
aim to facilitate statistical analysis, data mining, personlization, etc. However, while the
1 See http://stats.lod2.eu for an overview of the current state of the Cloud. Last
access: July 11th, 2014.
2 Data collected from http://stats.lod2.eu. Last access: July 11th, 2014.
3 See for example http://data.gov.uk/.
4 See for example http://data.semanticweb.org/
5 http://aksw.org/Projects/GHO
number of datasets on the Linked Data Web grows drastically, the number of links
between datasets still stagnates.6 Addressing this lack of links requires solving two main
problems: the quadratic time complexity of link discovery (efficiency) and the
automatic support of the detection of link specifications (effectiveness). In this paper, we
address the efficiency of the execution of bounded Jaro-Winkler measures,7 which are
known to be effective when comparing person names [
The contributions of this paper are as follows: 1. We derive length- and range-based filters that allow reducing the number of strings t that are compared with a string s . 2. We present a character-based filter that allows detecting whether two strings s and t share enough resemblance to be similar according to the Jaro-Winkler measure. 3. We evaluate our approach w.r.t. to its runtime and its scalability with several threshold settings and dataset sizes.
The rest of this paper is structured as follows: In Section 2, we present the problem we tackled as well as the formal notation necessary to understand this work. In the subsequent Section 3, we present the three approaches we developed to reduce the runtime of bounded Jaro-Winkler computations. We then evaluate our approach in Section 4. Related work is presented in Section 5, where we focus on approaches that aim to improve the time-efficiency of link discovery. We conclude in Section 6. The approach presented herein is now an integral part of LIMES.8 2
In the following, we present some of the symbols and terms used within this work. 2.1
In this work, we use link discovery as a hypernym for deduplication, record linkage,
entity resolution and similar terms used across literature. The formal specification of
link discovery adopted herein is tantamount to the definition proposed in [
In this paper, we thus study the following problem: Given a threshold 2 [0; 1] and
two sets of strings S and T , compute the set M 0 = f(s; t; (s; t)) 2 S T R+ :
(s; t) g. Two categories of approaches can be considered to improve the runtime
of measures: Lossy approaches return a subset M 00 of M 0 which can be calculated
efficiently but for which there are no guarantees that M 00 = M 0. Lossless approaches
on the other hand ensure that their result set M 00 is exactly the same as M 0. In this
paper, we present a lossless approach. To the best of our knowledge, only one other
link discovery framework implements a lossless approach that has been designed to
exploit the bound defined by the threshold to ensure a more efficient computation of
the Jaro-Winkler distance, i.e., the SILK framework with the approach MultiBlock [
Let be the set of all the strings that can be generated by using an alphabet A. The Jaro measure dj : ! [0; 1] is a string similarity measure approach which was developed originally for name comparison in the U.S. Census. This measure takes into account the number of character matches m and the ratio of their transpositions t: dj = ( 0 31 jsm1j + jsm2j + mm t if m = 0 otherwise Here two characters are considered to be a match if and only only if (1) they are the same and (2) they are at most at a distance w = b max(js21j;js2j) c from each other. For example, for s1 = "Spears" and s2 = "P ears", the second s of s1 matches the s of s2 while the first s of s1 does not match the s of s2.
The Jaro-Winkler measure [
dw = dj dj + (`p(1
if dj < bt dj )) otherwise (1) (2) Here, ` denotes the length of the common prefix and p is a weighting factor. Winkler uses p = 0:1 and ` 4. Note that `p must not be greater than 1.
For the strings s1 = "DEM OCRACY "; s2 = "DEM OGARP HY " (with s2 being intentionally misspelled) we get the following output of the Jaro-Winkler measure.
– js1j = 9; js2j = 10 – w = 4 – m = 7 – t = 1 – dj = 13 jsm1j + jsm2j + mm t – dw = dj + `p (1 dj ) = 0:867
The main principle behind reducing the runtime of the computation of measures is to reduce their reduction ratio. Here, we use a sequence of filters that allow discarding similarity computations while being sure that they would have led to a similarity score which would have been less than our threshold . To this end, we regard the problem as that of finding filters that return an upper bound estimation e(s1; s2) dw(s1; s2) for some properties of the input strings that can be computed in constant time. For a given threshold , if e(s1; s2) , then we can safely ignore the input (s1; s2). 3.1
In the following, we denoted the length of a string s with jsj. Our first filter is based on the insight that large length differences are a guarantee for poor similarity. For example, the strings "a" and "alpha" cannot have a Jaro-Winkler similarity of 1 by virtue of their length difference. We can formalize this idea as follows: Let s1 and s2 be strings with respective lengths js1j and js2j. Without loss of generality, we will assume that js1j js2j. Moreover, let m be the number of matches across s1 and s2. Because m js1j, we can substitute m with js1j and gain the following upper bound estimation for dj (s1; s2): dj = Now the lower bound for the number t of transpositions is 0. Thus, we obtain the following equation.
dj 31 1 + jjss21jj + 1 32 + 3jjss12jj The application of this approximation on Winkler’s extension is trivial: dw = dj + ` p (1 dj ) 2 + js1j + ` p 3 3js2j
Consider the pair s1 = "bike" and s2 = "bicycle" and a threshold = 0:9. Applying the estimation for Jaro we get dj 23 347 = 0:857. This exceeeds the boost threshold, so we use equation 5 to compute e(s1; s2) = 0:885. Now we do not have to actually compute dw(s1; s2), since e(s1; s2) < .
By using this approach we can decide in O(1)9 if a given pairs score is greater than a given threshold, which saves us the much more expensive score computation for a big number of pairs, provided that the input strings sufficiently vary in length. 9 In most programming languages, especially Java (which we used for our implementation), the length of string is stored in a variable and can thus be accessed in constant time. (3) (4) (5) 3.2
The approach described above can be reversed to limit the number of pairs that we are going to be iterated over. To this end, we can construct a index : N ! 2 which maps strings lengths l 2 N to all strings s with jsj = l. With the help of this index, we can now determine the set of strings t that should be compared with the subset S(l) of S that only contains strings of length l. We go about using this insight by computing the upper and lower bound for the length of a string t that should be compared with a string s. This is basically equivalent to asking what is the minimum length difference jjsj jtjj so that e(s; t) is satisfied. We transpose equation 5 to the following for our lower bound:
For example, consider a list of strings S with equally distributed, distinct string lengths (4; 7; 11; 18). Using Equation 6 and Equation 7 we obtain Table 1. Taking into account the last column of the table, we will save a total of 38 comparisons. jtj jsjmin jsjmax sizes in range An even more fine-grained approach can be chosen to filter out computations. Let e :
A ! N be the function with returns the number of occurrences of a given character c in a string s. For the strings s1 and2, the number of maximum possible matches mmax can be expressed as mmax =
X c2s1 min(e(s1; c); e(s2; c)) m Consequently, we can now substitute m for mmax in the Jaro distance computation: dj (s1; s2) = mmax iff (3
1)js1jjs2j : js1j + js2j (10)
For instance, let s1 = "astronaut"; s2 = "astrochimp". The retrieval of mmax ist shown in Table 2. The aim of our evaluation was to study how well our approach performs on real data. We chose DBpedia 3.9 as a source of data for our experiments as it contains data pertaining to 1.1 million persons and thus allows for both fine-grained evaluations and scalability evaluations. All experiments where deduplication experiments, i.e., S = T . We considered the list of all rdfs:label in DBpedia in our runtime evaluation and scalability experiments. We also computed the runtime of our approach on up to 105 labels for our scalability experiments. All experiments were performed on a 2.5 GHz Intel Core i5 machine with 16GB RAM running OS X 10.9.3. In our first series of experiments, we evaluated the runtime of all filter combinations against the na¨ıve approach on a small dataset containing 1000 labels from DBpedia. The results of our evaluation are shown in Figure 4.1. This evaluation suggests that all filters outperform the na¨ıve approach. Moreover, the combination of all filtersl lead to the best overall runtime in most cases. Interestingly, the character-based filter leads to a significant reduction of the number of comparisons (see Figure 2) by more than 2 orders of magnitude. However, the runtime improvement is not as substantial. This result seems to indicate that the lookup in the character indexes is very time-demanding. We will thus aim to improve our character indexing in future work. Overall, the results on this dataset already shows that we outperform the na¨ıve approach by more than an order of magnitude when is high. The runtimes on a larger sample of size 104 show an even better improvement (see Figure 3). This suggests that the relative improvement of our approach improves with the size of the problem.
0:8 0:85
0:9
0:95 1 The aim of the scalability evaluation was to measure how well our approach deals with datasets of growing size datasets. In our first set of experiments, we looked at the growth of the runtime of our approach on datasets of growing sizes. Our results suggest that our approach grows linearly with the number of labels contained in S and T (see Figure 5). This suggests that the runtime of our approach can be easily predicted for large datasets, which of importance when asking users to wait for the results of the computation. The second series of scalability experiments looked at the runtime behaviour of our approach on a large dataset with 105 labels. Our results suggest that the runtime of our approach falls superlinearly with an increase of the threshold (see Figure 4). This behaviour suggest that our approach is especially useful on clean datasets, where high thresholds can be used for link discovery.
0:8 0:85 0:95
1 0:9
na¨ıve range (r) length (l) freq. (f) r+l r+f r+l+f
na¨ıve r+l ( = 0:91) r+l ( = 0:95) r+l ( = 0:99) r+l+f ( = 0:91) r+l+f ( = 0:95) r+l+f ( = 0:99)
Fig. 5. Runtimes with multiple thresholds for growing input sizes
We compared our approach with SILK2.6.0. To this end, we retrieved all rdfs:label
of instances of subclasses of Person. We only compared with SILK on small datasets
(i.e., on classes with small numbers of instances) as the results on these small datasets
already showed that we outperform SILK consistently.10 Our results are shown in
Table 3. They suggest that the absolute difference in runtime grows with the size of the
datasets. Thus, we did not consider testing larger datasets against SILK as in the best
case, we were already 4.7 times faster than SILK (Architect dataset, = 0:95).
DBpedia Class Size OA(0:8) OA(0:9) OA(0:95) SILK(0:8) SILK(0:9) SILK(0:95)
Actors
Architect
Criminal
The work presented herein is related to record linkage, deduplication, link discovery
and the efficient computation of Hausdorff distances. An extensive amount of literature
has been published by the database community on record linkage (see [
In addition to addressing the runtime of link discovery, several machine-learning
approaches have been developed to learn link specifications (also called linkage rules)
for link discovery. For example, machine-learning frameworks such as FEBRL [
In this paper, we present a novel approach for the efficient execution of bounded JaroWinkler computations. Our approach is based on three filters which allow discarding a large number of comparisons. While our evaluation suggests that the filters are complementary, the character-based filter seems not to contribute to a significant reduction of the runtime once we deal with large datasets. We showed that our approach scales linearly with the amount of data it is faced with. Moreover, we showed that our approach can be make effective use of large thresholds by reducing the total runtime of the approach considerably. We also compared our approach with the state-of-the-art framework SILK 2.6.0 and showed that we outperform it on all datasets. In future work, we will study the character-based filter in more detail and aim to eradicate its exact performace bottleneck. Moreover, we will evaluate partitioning of datasets and parallelization of filters to further improve the runtime of large datasets. Finally, we will test whether our approach improves the accuracy of specification detection algorithms such as EAGLE.