Data interlinking is the problem of detecting the instances of di erent repositories but co-refer to the same topic. The large scale of linked data pushes a challenge to current interlinking algorithms. ScSLINT is an extension of SLINT+ [4] and its focus is scalability. ScSLINT also includes several modi ed features for the resolution sub-steps. The impressive performance of ScSLINT is validated by an experiment on very large datasets.
The goal of data interlinking is to detect all instances that co-refer to the same
objects in two repositories, the source and the target. The interlinking problem
on web-based data, such like linked data, is considered as more challenging than
other types of data because of the heterogeneity and scalability issues. Linked
data interlinking is a well-studied problem [
Among many proposed solutions, SILK [
Following the success of SLINT+ [
The architecture of ScSLINT is depicted by Fig. 1. Rsource and Rtarget are the input repositories. We describe the detail of each component in their order in the interlinking process.
This component creates the property alignments between Rsource and Rtarget. A property alignment is expected to describe the same attribute. ScSLINT considers only the properties satisfying the requirement of coverage, discriminability
alignments
generator
e c r u o s R t e g r a t
[
jOpsource j Opk = fE(o)jx 2 Rk; < s; pk; o >2 xg (1) where < s; p; o > stands for a RDF triple and E is a preprocessing function that extracts the tokens or normalizes the data format (e.g., date, time, and decimal) of the given RDF objects. ScSLINT is more scalable than SLINT+ because it does not need to consider all elements of Optarget as SLINT+ does.
This component uses the property alignments generated previously to create a list of initial similarity functions. A similarity function is speci ed by two pieces of information: a property alignment [psource; ptarget] and a similarity measure S. For two instances x 2 Rsource and y 2 Rtarget, a similarity function calculates the similarity S(value(x; psource); value(y; ptarget)) where value(a; p) extracts all RDF objects of the triples declared by p. Compared to SLINT+, this new module enables user to install any new similarity measure into ScSLINT.
The mission of the candidate generator is to reduce the huge number of pairwise alignments between instances, at jRsourcej jRtargetj pairs. This component detects the candidates of potentially co-referent instances. SLINT+ computes the rough similarity of instances using a weighted matrix structure, which is not scalable and inaccurate on ambiguous data. We recommend using token-based pre x blocking without weighting and currently install it in ScSLINT by default.
A con guration contains the parameters for further components. It describes similarity functions, similarity aggregator, and co-reference lter. If no intervention (e.g., user and con guration learning algorithms) to this component is declared, a default con guration will be construct by taking all generated similarity functions and picking the frequently used similarity aggregator and co-reference lter.
ScSLINT: Time and Memory E cient Interlinking Framework
In this component, the similarity functions are executed and their results are accumulated into one nal matching score. Currently, for computing the matching score of two instances x and y, ScSLINT supports the following equation: scoreFsim (x; y) = 1
X valid(UFsim (x; y)) v2UFsim (x;y) vk weight(y) (2) UFsim (x; y) = fsim(x; y)jsim(x; y) sim; sim 2 Fsimg where Fsim is the similarity functions speci ed by the con guration. k 2 f1; 2g controls the transformation for each similarity v. weight is a function weighting the target instance, which is logmaxt2Rtarget size(t) size(y), where size(y) counts the number of RDF triples of y. valid returns the number of elements in UFsim (x; y). sim is the acceptance threshold for the respective similarity function sim.
This is the most expensive component in the interlinking process. However, since the candidates can be read and processed independently, ScSLINT applies parallel processing technique for this component.
This component uses the matching scores of the candidates to construct the nal
co-references. In this step, acceptance threshold is applied onto the matching
scores in order to remove candidates with low similarity. In addition, for highly
ambiguous data, ltering is recommended in order to obtain the high quality
coreferences. ScSLINT currently supports stable ltering, which applies the idea
of stable marriage problem [
Implementation note. In order to optimize the memory load, ScSLINT uses pre-indexed structures of input RDF repositories. The complexity of indexing algorithm is small and is linear to the size of repository. Note that these indexes are created only one time and are reusable. ScSLINT is developed in C++. The source code this framework is available at http://ri-www.nii.ac.jp/ScSLINT. 3
We evaluate ScSLINT on a computer equipped with one Intel core i7 4770K CPU and 8GB memory. We enable multi-threading for the similarity aggregator. We test ScSLINT on 7 real datasets with very large size. The source repositories are three subsets of NYTimes, whose domain are locations (nyt.loc), organizations (nyt.org), and people (nyt.peo). The target repositories are Dbpedia (db), Freebase (fr), and Geonames (gn). We use the default token blocking, linear similarity aggregator (k = 1), and two complex similarity measures for strings, TF-IDF Cosine and Levenshtein. We use reverse distance for numeric values and exact matching for other data types. Using this con guration, in average, 90.57% of actual co-references are successfully detected.
Table 1 reports the complexity of these datasets and the execution time of each component of ScSLINT. In this table, the columns from 2 to 4 describe the parameters that make impacts to the complexity of the interlinking process. Column 2 is jRsourcej jRtargetj, which re ects the complexity of property alignment generator (Comp. 1) and candidate generator (Comp. 3). The multiplication of column 3 and 4 is the number of comparisons, which directly de nes the complexity of the similarity aggregator (Comp. 5) and co-reference lter (Comp. 6).
In our experiment, while ScSLINT achieves a very impressive speed, LIMES
and SILK fail to nish the interlinking task even within 10 times longer period
for each dataset (and we terminate those programs in this case). The longest
interlinking time is about 36 minutes, recorded on nyt.peo-fr, which requires
11:16 109 comparisons. On a dataset that is about 2000 times smaller than
nyt.peo-fr, the required time for LIMES and SILK are almost 30 minutes and
9.5 hours, respectively [
ScSLINT can process large data in very short time when running on a usual personal computer. That is, the framework expresses its compatibility for even huge scale datasets. ScSLINT can far bene t from being conjuncted with other big data processing framework or deployed on a powerful machine. Also, more advanced candidate generators, similarity metrics, aggregation strategies, and learning algorithm can be implemented in ScSLINT easily.