MinoanER : Schema-Agnostic, Non-Iterative, Massively Parallel Resolution of Web Entities

MinoanER: Schema-Agnostic, Non-Iterative, Massively Parallel Resolution of Web Entities Vasilis Efthymiou* IBM Research v[email protected] George Papadakis University of Athens [email protected] Kostas Stefanidis Univeristy of Tampere konstantinos.stef[email protected] Vassilis Christophides INRIA-Paris and Univ. of Crete v[email protected] ABSTRACT Entity Resolution (ER) aims to identify different descriptions in various Knowledge Bases (KBs) that refer to the same entity. ER is challenged by the Variety,Volume and Veracity of entity descriptions published in the Web of Data. To address them, we propose the MinoanER framework that simultaneously fulfills full automation, support of highly heterogeneous entities, and massive parallelization of the ER process. MinoanER leverages a tokenbased similarity of entities to define a new metric that derives the similarity of neighboring entities from the most important relations, as they are indicated only by statistics. A composite blocking method is employed to capture different sources of matching evidence from the content, neighbors, or names of entities. The search space of candidate pairs for comparison is compactly abstracted by a novel disjunctive blocking graph and processed by a non-iterative, massively parallel matching algorithm that consists of four generic, schema-agnostic matching rules that are quite robust with respect to their internal configuration. We demonstrate that the effectiveness of MinoanER is comparable to existing ER tools over real KBs exhibiting low Variety, but it outperforms them significantly when matching KBs with high Variety. 1 INTRODUCTION Even when data integrated from multiple sources refer to the same real-world entities (e.g., persons, places), they usually exhibit several quality issues such as incompleteness (i.e., partial data), redundancy (i.e., overlapping data), inconsistency (i.e., conflicting data) or simply incorrectness (i.e., data errors). A typical task for improving various data quality aspects is Entity Resolution (ER). In the Web of Data, ER aims to facilitate interlinking of data that describe the same real-world entity, when unique entity identifiers are not shared across different Knowledge Bases (KBs) describing them [ 8 ]. To resolve entity descriptions we need (a) to compute effectively the similarity of entities, and (b) to pair-wise compare entity descriptions. Both problems are challenged by the three Vs of the Web of Data, namely Variety, Volume and Veracity [ 10 ]. Not only does the number of entity descriptions published by each KB never cease to increase, but also the number of KBs even for a single domain, has grown to thousands (e.g., there is a x100 growth of the LOD cloud size since its first edition 1 ). Even in the same domain, KBs are extremely heterogeneous both regarding how they semantically structure their data, as well as *Work conducted during the Ph.D research of the author at ICS-FORTH. 1https://lod-cloud.net © 2019 Copyright held by the owner/author(s). Published in Proceedings of the 22nd International Conference on Extending Database Technology (EDBT), March 26-29, 2019, ISBN 978-3-89318-081-3 on OpenProceedings.org. Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0. Figure 1: Parts of entity graphs, representing the Wikidata (left) and DBpedia (right) KBs. how diverse properties are used to describe even substantially similar entities (e.g., only 109 out of ∼ 2,600 LOD vocabularies are shared by more than one KB). Finally, KBs are of widely differing quality, with significant differences in the coverage, accuracy and timeliness of data provided [ 9 ]. Even in the same domain, various inconsistencies and errors in entity descriptions may arise, due to the limitations of the automatic extraction tools [ 34 ], or of the crowd-sourced contributions. The Web of Data essentially calls for novel ER solutions that relax a number of assumptions underlying state-of-the-art methods. The most important one is related to the notion of similarity that better characterizes entity descriptions in the Web of Data - we define an entity description to be a URI-identifiable set of attributevalue pairs, where values can be literals, or the URIs of other descriptions, this way forming an entity graph. Clearly, Variety results in extreme schema heterogeneity, with an unprecedented number of attribute names that cannot be unified under a global schema [ 15 ]. This situation renders all schema-based similarity measures that compare specific attribute values inapplicable [ 15 ]. We thus argue that similarity evidence of entities within and across KBs can be obtained by looking at the bag of strings contained in descriptions, regardless of the corresponding attributes. As this value-based similarity of entity pairs may still be weak, due to a highly heterogeneous description content, we need to consider additional sources of matching evidence; for instance, the similarity of neighboring entities , which are interlinked via various semantic relations. Figure 1 presents parts of the Wikidata and DBpedia KBs, showing the entity graph that captures connections inside them. For example, Restaurant2 and Jonny Lake are neighbor entities in this graph, connected via a “headChef” relation. If we compare John Lake A to Jonny Lake based on their values only, it is easy Series ISSN: 2367-2005 373 10.5441/002/edbt.2019.33 Figure 2: Value and neighbor similarity distribution of matches in 4 datasets (see Table 1 for more details). to infer that those descriptions are matching; they are strongly similar. However, we cannot be that sure about Restaurant1 and Restaurant2, if we only look at their values. Those descriptions are nearly similar and we have to look further at the similarity of their neighbors (e.g, John Lake A and Jonny Lake) to verify that they match. Figure 2 depicts both sources of similarity evidence (valueSim, neighborSim) for entities known to match (i.e., ground truth) in four benchmark datasets that are frequently used in the literature (details in Table 1). Every dot corresponds to a matching pair of entities, and its shape denotes its origin KBs. The horizontal axis reports the normalized value similarity (weighted Jaccard coefficient [ 21 ]) based on the tokens (i.e., single words in attribute values) shared by a pair of descriptions, while the vertical one reports the maximum value similarity of their neighbors. The value similarity of matching entities significantly varies across different KBs. For strongly similar entities , e.g., with a value similarity > 0.5, existing duplicate detection techniques work well. However, a large part of the matching pairs of entities is covered by nearly similar entities , e.g., with a value similarity < 0.5. To resolve them, we need to additionally exploit evidence regarding the similarity of neighboring entities. This also requires revisiting the blocking (aka indexing) techniques used to reduce the number of candidate pairs [ 7 ]. To avoid restricting candidate matches (i.e., descriptions placed on the same block) to strongly similar entities, we need to assess both value and neighbor similarity of candidate matches. In essence, rather than a unique indexing function, we need to consider a composite blocking that provides matching evidence from different sources, such as the content, the neighbors or even the names (e.g., rdfs:label ) of entities. Creating massively parallelizable techniques for processing the search space of candidate pairs formed by such composite blocking is an open research challenge. Overall, the main requirements for Web-scale ER are: (i) identify both strongly and nearly similar matches, (ii) do not rely on a given schema, (iii) do not rely on domain experts for aligning relations and matching rules, (iv) develop non-iterative solutions to avoid late convergence, and (v) scale to massive volumes of data. None of the existing ER frameworks proposed for the Web of Data (e.g., LINDA [ 4 ], SiGMa [ 21 ] and RiMOM [ 31 ]) simultaneously fulfills all these requirements. In this work, we present the MinoanER framework for a Web-scale ER 2 . More precisely, we make the following contributions: • We leverage a token-based similarity of entity descriptions, introduced in [ 27 ], to define a new metric for the similarity of a set of neighboring entity pairs that are linked via important relations to the entities of a candidate pair. Rather than requiring an a priori knowledge of the entity types or of their correspondences, we rely on simple statistics over two KBs to recognize the most important entity relations involved in their neighborhood, as well as, the most distinctive attributes that could serve as names of entities beyond the rdfs:label, which is not always available in descriptions. • We exploit several indexing functions to place entity descriptions in the same block either because they share a common token in their values, or they share a common name. Then, we introduce a novel abstraction of multiple sources of matching evidence regarding a pair of entities (from the content, neighbors, or the names of their descriptions) under the form of a disjunctive blocking graph. We present an efficient algorithm for weighting and then pruning the edges with low weights, which are unlikely to correspond to matches. As opposed to existing disjunctive blocking schemes [ 3 , 18 ], our disjunctive blocking is schema-agnostic and requires no (semi-)supervised learning. • We propose a non-iterative matching process that is implemented in Spark [ 36 ]. Unlike the data-driven convergence of existing systems (e.g., LINDA [ 4 ], SiGMa [ 21 ], RiMOM [ 31 ]), the matching process of MinoanER involves a specific number of predefined generic, schema-agnostic matching rules (R1-R4) that traverse the blocking graph. First, we identify matches based on their name (R1). This is a very effective method that can be applied to all descriptions, regardless of their values or neighbor similarity. Unlike the schema-based blocking keys of relational descriptions usually provided by domain experts, MinoanER automatically specifies distinctive names of entities from data statistics. Then, the value similarity is exploited to find matches with many common and infrequent tokens, i.e., strongly similar matches (R2). When value similarity is not high, nearly similar matches are identified based on both value and neighbors’ similarity using athreshold-free rank aggregation function (R3), as opposed to existing works that combine different matching evidence into an aggregated score. Finally, reciprocal evidence of matching is exploited as a verification of the returned results: only entities that are mutually ranked in the top positions of their unified ranking lists are considered matches (R4). Figure 2 abstractly illustrates the type of matching pairs that are covered by each matching rule. • We experimentally compare the effectiveness of MinoanER against state-of-the-art methods using established benchmark data that involve real KBs. The main conclusion drawn from our experiments is that MinoanER achieves at least equivalent performance over KBs exhibiting a low Variety (e.g., those originating from a common data source like Wikipedia) even though the latter make more assumptions about the input KBs (e.g., alignment of relations); yet, MinoanER significantly outperforms state-of-theart ER tools when matching KBs with high Variety. The source code and datasets used in our experimental study are publicly available3. The rest of the paper is structured as follows: we introduce our value and neighbor similarities in Section 2, and we delve into the 2A preliminary, abridged version of this paper appeared in [13]. 3http://csd.uoc.gr/~vefthym/minoanER 374 blocking schemes and the blocking graph that lie at the core of our approach in Section 3. Section 4 describes the matching rules of our approach along with their implementation in Spark, while Section 5 overviews the main differences with the state-of-the-art ER methods. We present our thorough experimental analysis in Section 6 and we conclude the paper in Section 7. 2 BASIC DEFINITIONS Given a KB E , an entity description with a URI identifier i , denoted by ei∈ E , is a set of attribute-value pairs about a realworld entity. When the identifier of an entity description ej appears in the values of another entity description ei , the corresponding attribute is called a relation and the corresponding value ( ej ) a neighbor of ei . More formally, the relations of ei are defined as relations(ei)={p|(p,j) ∈ ei∧ej∈ E} , while its neighbors as neiдhbors(ei)={ej|(p,j) ∈ ei∧ej∈ E} . For example, for the Wikidata KB in the left side of Figure 1 we have: relations(Restaurant1) = {hasChef, territorial, inCountry}, and neiдhbors(Restaurant1) = {John Lake A, Bray, United Kingdom}. In the following, we exclusively consider clean-clean ER, i.e., the sub-problem of ER that seeks matches among two duplicatefree (clean) KBs. Thus, we simplify the presentation of our approach, but the proposed techniques can be easily generalized to more than two clean KBs or a single dirty KB, i.e., a KB that contains duplicates. 2.1 Entity similarity based on values Traditionally, similarity between entities is computed based on their values. In our work, we apply a similarity measure based on the number and the frequency of common words between two values4. Definition 2.1. Given two KBs, E1 and E2 , the value similarity of two entity descriptions ei∈ E1,ej∈ E2 is defined as: valueSim(ei,ej)=Ít∈tokens(ei)∩tokens(ej) 1 loд2(EFE1(t)·EFE2(t)+1) , where EFE(t)=|{el|el∈ E ∧ t∈tokens(el)}| stands for “Entity Frequency”, which is the number of entity descriptions in E having token tin their values. This value similarity shares the same intuition as TF-IDF in information retrieval. If two entities share many, infrequent tokens, then they have high value similarity. On the contrary, very frequent words (resembling stopwords in information retrieval) are not considered an important matching evidence, when they are shared by two descriptions, and therefore, they only contribute insignificantly to the valueSim score. The number of common words is accounted by the number of terms that are considered in the sum and the frequency of those words is given by the inverse Entity Frequency (EF), similar to the inverse Document Frequency (DF) in information retrieval. Proposition 1. valueSim is a similarity metric, since it satisfies the following properties [5]: •valueSim(ei,ei) ≥ 0, •valueSim(ei,ej)=valueSim(ej,ei), •valueSim(ei,ei) ≥ valueSim(ei,ej), •valueSim(ei,ei)=valueSim(ej,ej)=valueSim(ei,ej) ⇔ei=ej , •valueSim(ei,ej)+valueSim(ej,ez) ≤ valueSim(ei,ez)+ valueSim(ej,ej). 4 We handle numbers and dates in the same way as strings, assuming string-dominated entities. PROOF. Please refer to the extended version of this paper 5 . □ Note that valueSim has the following properties: (i) it is not a normalized metric, since it can take any value in [0,+∞) , with 0 denoting the existence of no common tokens in the values of the compared descriptions. (ii) The maximum contribution of a single common token between two descriptions is 1, in case this common token does not appear in the values of any other entity description, i.e., when EFE1(t) · EFE2(t)=1 .(iii) It is a schema-agnostic similarity metric, as it disregards any schematic information6. 2.2 Entity similarity based on neighbors In addition to value similarity, we exploit the relations between descriptions to find the matching entities of the compared KBs. This can be done by aggregating the value similarity of all pairs of descriptions that are neighbors of the target descriptions. Given the potentially high number of neighbors that a description might have, we propose considering only the most valuable neighbors for computing the neighbor similarity between two target descriptions. These are neighbors that are connected with the target descriptions via important relations, i.e., relations that exhibit high support and discriminability. Intuitively, high support for a particular relation p indicates that p appears in many entity descriptions, while high discriminability for p indicates that it has many distinct values. More formally: Definition 2.2. The support of a relation p∈ P in a KB E is defined as: support(p)=|instances(p)| |E |2 , where instances(p)= {(i,j)|ei,ej∈ E ∧ (p,j) ∈ ei}. Definition 2.3. The discriminability of a relation p∈ P in a KB E is defined as: discriminability(p)=|objects(p)| |instances(p)| , where objects(p)={j|(i,j) ∈ instances(p)}. Overall, we combine support and discriminability via their harmonic mean in order to locate the most important relations. Definition 2.4. The importance of a relation p∈ P in a KB E is defined as: importance(p)=2·support(p)·discriminability(p) suppor t (p)+discriminability(p). On this basis, we identify the most valuable relations and neighbors for every single entity description (i.e., locally). We use topNrelations(ei) to denote the N relations in relations(ei) with the maximum importance scores. Then, the best neighbors for ei are defined as: topNneiдhbors(ei)={nei|(p,nei) ∈ ei∧p∈ topNrelations(ei)}. Intuitively, strong matching evidence (high value similarity) for the important neighbors leads to strong matching evidence for the target pair of descriptions. Hence, we formally define neighbor similarity as follows: Definition 2.5. Given two KBs, E1 and E2 , the neighbor similarity of two entity descriptions ei∈ E1,ej∈ E2is: neiдhborNSim(ei,ej)=Õ nei∈topN neiдhbors(ei) nej∈topN neiдhbors(ej) valueSim(nei,nej). Proposition 2. neiдhborNSim is a similarity metric. 5http://csd.uoc.gr/~vefthym/DissertationEfthymiou.pdf 6 Note that our value similarity metric is crafted for the token-level noise in literal values, rather than the character-level one. Yet, our overall approach is tolerant to character-level noise, as verified by our extensive experimental analysis with real datasets that include it. The reason is that it is highly unlikely for matching entities to have character-level noise in all their common tokens. 375 PROOF. Given that neiдhborNSim is the sum of similarity metrics (valueSim), it is a similarity metric, too [5]. □ Neither valueSim nor neiдhborNSim are normalized, since the number of terms that contribute in the sums is an important matching evidence that can be mitigated if the values were normalized. Example 2.6. Continuing our example in Figure 1, assume that the best two relations for Restaurant1 and Restaurant2 are: top2relations(Restaurant1)= {hasChef, territorial} and top2relations(Restaurant2)= {headChef, county}. Then, top2neiдhbors(Restaurant1)= {John Lake A, Bray} and top2neiдhbors(Restaurant2)= {Jonny Lake, Berkshire}, and neiдhbor2Sim(Restaurant1,Restaurant2)= valueSim(Bray,JonnyLake) + valueSim(John Lake A,Berkshire) + valueSim(Bray,Berkshire) + valueSim(John Lake A,JonnyLake) . Note that since we don’t have a relation mapping, we also consider the comparisons (Bray, JonnyLake) and (John Lake A, Berkshire). Entity Names. From every KB, we also derive the global topk attributes of highest importance, whose literal values act as names for any description ei that contains them. Their support is simply defined as: support(p)=|subjects(p)|/|E| , where subjects(p)= {i|(i,j) ∈ instances(p)} [ 32 ]. Based on these statistics, function name(ei) returns the names of ei , and Nx denotes all names in a KB Ex . In combination with topNneiдhbors(ei) , this function covers both local and global property importance, exploiting both the rare and frequent attributes that are distinctive enough to designate matching entities. 3 BLOCKING To enhance performance, blocking is typically used as a preprocessing step for ER in order to reduce the number of unnecessary comparisons, i.e., comparisons between descriptions that do not match. After blocking, each description can be compared only to others placed within the same block. The desiderata of blocking are [ 6 ]: (i) to place matching descriptions in common blocks (effectiveness), and (ii) to minimize the number of suggested comparisons (time efficiency). However, efficiency dictates skipping many comparisons, possibly yielding many missed matches, which in turn implies low effectiveness. Thus, the main objective of blocking is to achieve a good trade-off between minimizing the number of suggested comparisons and minimizing the number of missed matches [7]. In general, blocking methods are defined over key values that can be used to decide whether or not an entity description could be placed in a block using an indexing function [ 7 ]. The ‘uniqueness’ of key values determines the number of entity descriptions placed in the same block, i.e., which are considered as candidate matches. More formally, the building blocks of a blocking method can be defined as [3]: • An indexing function hkey:E → 2B is a unary function that, when applied to an entity description using a specific blocking key, it returns as a value the subset of the set of all blocks B , under which the description will be indexed. • Aco-occurrence function okey:E × E → {true,f alse} is a binary function that, when applied to a pair of entity descriptions, it returns ‘true’ if the intersection of the sets of blocks produced by the indexing function on its arguments, is non-empty, and ‘false’ otherwise; okey(ek,el)=true iff hkey(ek) ∩ hkey(el),∅. In this context, each pair of descriptions whose co-occurrence function returns ‘true’ shares at least one common block, and the distinct union of the block elements is the input entity collection (i.e., all the descriptions from a set of input KBs). Formally: Definition 3.1. Given an entity collection E , atomic blocking is defined by an indexing function hkey for which the generated blocks, Bkey = {bkey 1, . . . , bkey m} , satisfy the following conditions: (i) ∀ek,el∈bkey i:bkey i∈Bkey,okey(ek,el)=true, (ii) ∀(ek,el):okey(ek,el)=true,∃bkey i∈Bkey,ek,el∈bkey i, (iii) Ð bkey i∈Bkey bkey i=E. Given that a single key is not enough for indexing loosely structured and highly heterogeneous entity descriptions, we need to consider several keys that the indexing function will exploit to build different sets of blocks. Such a composite blocking method is characterized by a disjunctive co-occurrence function over the atomic blocks, and it is formally defined as: Definition 3.2. Given an entity collection E , disjunctive blocking is defined by a set of indexing functions H , for which the generated blocks B=Ð hkey∈H Bkeysatisfy the following conditions: (i) ∀ek,el∈b:b∈B,oH(ek,el)=true, (ii) ∀(ek,el):oH(ek,el)=true,∃b∈B,ek,el∈b, where oH(ek,el)=Ôhkey∈Hokey(ek,el). Atomic blocking can be seen as a special case of composite blocking, consisting of a singleton set, i.e., H={hkey}. 3.1 Composite Blocking Scheme To achieve a good trade-off between effectiveness and efficiency, our composite blocking scheme assesses the name and value similarity of the candidate matches in combination with similarity evidence provided by their neighbors on important relations. We consider the blocks constructed for all entities ei∈ E using the indexing function hi(·) both over entity names ( ∀nj∈names(ei): hN(nj) ) and tokens ( ∀tj∈tokens(ei):hT(tj) ). The composite blocking scheme O of MinoanER is defined by the following disjunctive co-occurrence condition of any two entities ei,ej∈ E : O(ei,ej)=oN(ei,ej) ∨ oT(ei,ej)∨ (Ô(e′ i,e′ j)∈topN neiдhbors(ei)×topN neiдhbors(ej)oT(e′ i,e′ j)), where oN , oT is the co-occurrence function applied on names and tokens, respectively. Intuitively, two entities are placed in a common block, and are then considered candidate matches, if at least one of the following three cases holds: (i) they have the same name, which is not used by any other entity, in which case the common block contains only those two entities, or (ii) they have at least one common word in any of their values, in which case the size of the common block is given by the product of the Entity Frequency ( EF ) of the common term in the two input collections, or (iii) their top neighbors share a common word in any of their values. Note that token blocking (i.e., hT ) allows for deriving valueSim from the size of blocks shared by two descriptions. As a result, no additional blocks are needed to assess neighbor similarity of candidate entities: token blocking is sufficient also for estimating neiдhborNsim according to Definition 2.5. 3.2 Disjunctive Blocking Graph The disjunctive blocking graph G is an abstraction of the disjunctive co-occurrence condition of candidate matches in blocks. Nodes represent candidates from our input entity descriptions, while edges represent pairs of candidates for which at least one 376 Figure 3: (a) Parts of the disjunctive blocking graph corresponding to Figure 1, and (b) the corresponding blocking graph after pruning. of the co-occurrence conditions is ‘true’. Each edge is actually labeled with three weights that quantify similarity evidence on names, tokens and neighbors of candidate matches. Specifically, the disjunctive blocking graph of MinoanER is a graph G= (V,E,λ) , with λ assigning to each edge a label ( α,β,γ ), where α is ‘1’ if oN(ei,ej) is true and the name block in which ei , ej co-occur is of size 2, and ‘0’ otherwise, β=valueSim(ei,ej) , and γ=neiдhborNSim(ei,ej). More formally: Definition 3.3. Given a block collection B=Ðhkey∈HBkey , produced by a set of indexing functions H , the disjunctive blocking graph for an entity collection E , is a graph G=(V,E,λ) , where each node vi∈V represents a distinct description ei∈ E , and each edge <vi,vj>∈Erepresents a pair ei,ej∈ E for which O(ei,ej)=‘true′ ; O(ei,ej) is a disjunction of the atomic cooccurrence functions ok defined along with H , and λ:E→Rn is a labeling function assigning a tuple [w1, . . . , wn] to each edge, where wk is a weight associated with each co-occurrence function okof H. Definition 3.3 covers the cases of an entity collection E being composed of one, two, or more KBs. When matching k KBs, assuming that all of them are clean, the disjunctive blocking graph is k -partite, with each of the k KBs corresponding to a different independent set of nodes, i.e., there are only edges between descriptions from different KBs. The only information needed to match multiple KBs is to which KB every description belongs, so as to add it to the corresponding independent set. Similarly, the disjunctive blocking graph covers dirty ER, as well. Example 3.4. Consider the graph of Figure 3(a), which is part of the disjunctive blocking graph generated from Figure 1. John Lake A and Jonny Lake have a common name (“J. Lake”), and there is no other entity having this name, so there is an edge connecting them with α=1 . Bray and Berkshire have common, quite infrequent tokens in their values, so their similarity ( β in the edge connecting them) is quite high ( β = 1.2). Since Bray is a top neighbor of Restaurant1 in Figure 1, and Berkshire is a top neighbor of Restaurant2, there is also an edge with a non-zero γ connecting Restaurant1 with Restaurant2. The γ score of this edge (1.6) is the sum of the β scores of the edges connecting Bray with Berkshire (1.2), and John Lake A with Jonny Lake (0.4). 3.3 Graph Weighting and Pruning Algorithms Each edge in the blocking graph represents a suggested comparison between two descriptions. To reduce the number of comparisons suggested by the disjunctive blocking graph, we keep for each node the K edges with the highest β and the K edges with the highest γ weights, while pruning edges with trivial weights (i.e., (α,β,γ )=(0,0,0)), since they connect descriptions unlikely to match. Given that nodes vi and vj may have different top K edges based on β or γ , we consider each undirected edge in G as two directed ones, with the same initial weights, and perform pruning on them. Example 3.5. Figure 3(b) shows the pruned version of the graph in Figure 3(a). Note that the blocking graph is only a conceptual model, which we do not materialize; we retrieve any necessary information from computationally cheap inverted indices. The process of weighting and pruning the edges of the disjunctive blocking graph is described in Algorithm 1. Initially, the graph contains no edges. We start adding edges by checking the name blocks BN (Lines 5-9). For each name block b that contains exactly two entities, one from each KB, we create an edge with α =1 linking those entities (note that in Algorithm 1, bk , k∈{1,2} , denotes the sub-block of b that contains the entities from Ek , i.e., bk⊆Ek ). Then, we compute the β weights (Lines 10-14) by running a variation of Meta-blocking [ 27 ], adapted to our value similarity metric (Definition 2.1). Next, we keep for each entity, its connected nodes from the K edges with the highest β (Lines 1518). Line 20 calls the procedure for computing the top in-neighbors of each entity, which operates as follows: first, it identifies each entity’s topNneiдbors (Lines 36-43) and then, it gets their reverse; for every entity ei , we get the entities topInNeiдhbors[i] that have ei as one of their topNneiдhbors (Lines 44-47). This allows for estimating the γ weights according to Definition 2.5. To avoid re-computing the value similarities that are necessary for the γ computations, we exploit the already computed β s. For each pair of entities ei∈ E1 , ej∈ E2 that are connected with an edge with β>0 , we assign to each pair of their inNeiдhbors , (ini,inj) , a partial γ equal to this β (Lines 20-27). After iterating over all such entity pairs ei,ej , we get their total neighbor similarity, i.e., γ[i,j]=neiдhborNsim(ei,ej) . Finally, we keep for each entity, its Kneighbors with the highest γ(Lines 28-33). The time complexity of Algorithm 1 is dominated by the processing of value evidence, which iterates twice over all comparisons in the token blocks BT . In the worst-case, this results in one computation for every pair of entities, i.e., O(|E1| · |E2|) . In practice, though, we bound the number of computations by removing excessively large blocks that correspond to highly frequent tokens (e.g., stop-words). Following [ 27 ], this is carried out by Block Purging [ 26 ], which ensures that the resulting blocks involve two orders of magnitude fewer comparisons than the bruteforce approach, without any significant impact on recall. This complexity is higher than that of name and neighbor evidence, which are both linearly dependent on the number of input entities. The former involves a single iteration over the name blocks BN , which amount to |N1∩ N2| , as there is one block for every name shared by E1 and E2 . For neighbor evidence, Algorithm 1 checks all pairs of N neighbors between every entity ei and its K most value-similar descriptions, performing K·N2· (|E1|+|E2|) operations; the cost of estimating the top in-neighbors for each entity is lower, dominated by the ordering of all relations in E1 and E2 (i.e., |Rmax | · loд|Rmax | ), where |Rmax | stands for the maximum number of relations in one of the KBs. 377 Algorithm 1: Disjunctive Blocking Graph Construction. Input: E1,E2, the blocks from name and token blocking, BNand BT Output: A disjunctive blocking graph G. 1procedure getCompositeBlockingGraph(E1,E2,BN,BT) 2V← E1∪ E2; 3E← ∅; 4W← ∅ ;// init. to (0,0,0) // Name Evidence 5for b∈BNdo 6if |b1|·|b2|=1then // only 1 comparison in b 7ei←b1.дet(0),ej←b2.дet(0);// entities in b 8E←E∪ {<vi,vj>}; 9W←W.set(α, < vi,vj>, 1); // Value Evidence 10 for ei∈ E1do 11 β[] ← ∅ ;// value weights wrt all ej∈ E2 12 for b∈BT∧b∩ei,∅do 13 for ej∈b2do // ej∈ E2 14 β[j]←β[j]+1/loд2(|b1|·|b2|+1) ; // valueSim 15 V alueCandidates ←дetT opCandidates(β[],K); 16 for ej∈V alueCandidates do 17 E←E∪ {<vi,vj>}; 18 W←W.set(β, < vi,vj>, β[j]); 19 for ei∈ E2do ...; // ...do the same for E2 // Neighbor Evidence 20 inN eiдhbors[] ← дetT opI nN eiдhbors(E1,E2); 21 γ[][] ← ∅ ;// neighbor weights wrt all ei,ej∈V 22 for ei∈ E1do 23 for ej∈ E2, s.t. W.дet(β, < vi,vj>)>0do 24 for inj∈inN eiдhbors[j]do 25 for ini∈inN eiдhbors[i]do // neighborNSim 26 γ[i][j] ← γ[i][j]+W.дet(β, < ni,nj>); 27 for ei∈ E2do ...; // ...do the same for E2 28 for ei∈ E1do 29 N eiдhborCandidates ←дetT opCandidates(γ[i][],K); 30 for ej∈N eiдhborCandidates do 31 E←E∪ {<vi,vj>}; 32 W.set(γ, < vi,vj>, γ[i][j]); 33 for ei∈ E2do ...; // ...do the same for E2 34 return G=(V,E,W); 35 procedure getTopInNeighbors(E1,E2) 36 topN eiдhbors[] ← ∅ ;// one list for each entity 37 дlobalOrder ←sort E1’s relations by importance; 38 for e∈ E1do 39 localOrder (e)←relations(e).sort By(дlobalOrder ); 40 topN r elations ←localOrder (e).topN ; 41 for (p,o) ∈ e, where p∈topN r elations do 42 topN eiдhbors[e].add(o); 43 for ei∈ E2do ...; // ...do the same for E2 44 topInN eiдhbors[]←∅;// the reverse of topNeighbors 45 for e∈ E1∪ E2do 46 for ne ∈topN eiдhbors[e]do 47 topInN eiдhbors[ne].add(e); 48 return topInN eiдhbors; 4 NON-ITERATIVE MATCHING PROCESS Our matching method receives as input the disjunctive blocking graph G and performs four steps – unlike most existing works, which involve a data-driven iterative process. In every step, a matching rule is applied with the goal of extracting new matches from the edges of G by analyzing their weights. The functionality of our algorithm is outlined in Algorithm 2. Next, we describe its rules in the order they are applied: Name Matching Rule (R1). The matching evidence of R1 comes from the entity names. It assumes that two candidate entities Algorithm 2: Non-iterative Matching. Input: E1,E2, The pruned, directed disjunctive blocking graph G. Output: A set of matches M. 1M← ∅;// The set of matches // Name Matching Value (R1) 2for <vi,vj>∈G.Edo 3if G.W.дet(α, < vi,vj>)=1then 4M←M∪ (ei,ej); // Value Matching Value (R2) 5for vi∈G.Vdo 6if ei∈ E1\Mthen // check the smallest KB for efficiency 7vj←arдmaxvk∈G.VG.W.дet(β, < vi,vk>);// top candidate 8if G.W.дet(β, < vi,vj>) ≥ 1then 9M←M∪ (ei,ej); // Rank Aggregation Matching Value (R3) 10 for vi∈G.Vdo 11 if ei∈ E1∪ E2\Mthen 12 aдд[] ← ∅;// Aggregate scores, init. zeros 13 valCands ←G.valCand(ei);// nodes linked to ei in decr. β 14 rank ← |valCands |; 15 for ej∈valCands do 16 aдд[ei].update(ej,θ·rank/|valCands |); 17 rank ←rank −1; 18 nдbCands ←G.nдbCand(ei) ; // nodes linked to ei in decr. γ 19 rank ← |nдbCands |; 20 for ej∈nдbCands do 21 aдд[ei].update(ej,(1−θ) · r ank/|nдbCands |); 22 rank ←rank −1; 23 M←M∪ (ei,дetT opCandidate(aдд[ei])); // Reciprocity Matching Value (R4) 24 for (ei,ej) ∈ Mdo 25 if <vi,vj><G.E∨<vj,vi><G.Ethen 26 M←M\ (ei,ej); 27 return M; match, if they, and only they, have the same name n . Thus, R1 traverses G and for every edge < vi,vj > with α = 1, it updates the set of matches M with the corresponding descriptions (Lines 2-4 in Alg. 2). All candidates matched by R1 are not examined by the remaining rules. Value Matching Rule (R2). It presumes that two entities match, if they, and only they, share a common token t , or, if they share many infrequent tokens. Based on Definition 2.1, R2 identifies pairs of descriptions with high value similarity (Lines 5-9). To this end, it goes through every node vi of G and checks whether the corresponding description stems from the smaller in size KB, for efficiency reasons (fewer checks), but has not been matched yet. In this case, it locates the adjacent node vj with the maximum β weight (Line 7). If β≥1 ,R2 considers the pair ( ei,ej ) to be a match. Matches identified by R2 will not be considered in the sequel. Rank Aggregation Matching Rule (R3). This rule identifies further matches for candidates whose value similarity is low ( β<1 ), yet their neighbor similarity ( γ ) could be relatively high. In this respect, the order of candidates rather than their absolute similarity values are used. Its functionality appears in Lines 10-23 of Algorithm 2. In essence, R3 traverses all nodes of G that correspond to a description that has not been matched yet. For every such node vi , it retrieves two lists: the first one contains adjacent edges with a non-zero β weight, sorted in descending order (Line 13), while 378 Figure 4: The architecture of MinoanER in Spark. the second one includes the adjacent edges sorted in decreasing non-zero γ weights (Line 18). Then, R3 aggregates the two lists by considering the normalized ranks of their elements: assuming the size of a list is K , the first candidate gets the score K/K , the second one (K−1)/K , while the last one 1/K . Overall, each adjacent node of vi takes a score equal to the weighted summation of its normalized ranks in the two lists, as determined through the trade-off parameter θ∈ (0,1) (Lines 16 & 21): the scores of the β list are weighted with θ and those of the γ list with 1θ . At the end, vi is matched with its top-1 candidate match vj , i.e., the one with the highest aggregate score (Line 23). Intuitively, R3 matches ei with ej , when, based on all available evidence, there is no better candidate for eithan ej. Reciprocity Matching Rule (R4). It aims to clean the matches identified by R1,R2 and R3 by exploiting the reciprocal edges of G . Given that the originally undirected graph G becomes directed after pruning (as it retains the best edges per node), a pair of nodes vi and vj are reciprocally connected when there are two edges between them, i.e., an edge from vi to vj and an edge from vj to vi . Hence, R4 aims to improve the precision of our algorithm based on the rationale that two entities are unlikely to match, when one of them does not even consider the other to be a candidate for matching. Intuitively, two entity descriptions match, only if both of them “agree” that they are likely to match. R4 essentially iterates over all matches detected by the above rules and discards those missing any of the two directed edges (Lines 24-26), acting more like a filter for the matches suggested by the previous rules. Given a pruned disjunctive blocking graph, every rule can be formalized as a function that receives a pair of entities and returns true ( T ) if the entities match according to the rule’s rationale, or false ( F ) otherwise, i.e., Rn :E1× E2→ {T,F} . In this context, we formally define the MinoanER matching process as follows: Definition 4.1. The non-iterative matching of two KBs E1 , E2 , denoted by the Boolean matrix M(E1,E2) , is defined as a filtering problem of the pruned disjunctive blocking graph G : M(ei,ej)=(R1(ei,ej) ∨ R2(ei,ej) ∨ R3(ei,ej)) ∧ R4(ei,ej). The time complexity of Algorithm 2 is dominated by the size of the pruned blocking graph G it receives as input, since R1,R2 and R3 essentially go through all directed edges in G (in practice, though, R1 reduces the edges considered by R2 and R3, and so does R2 for R3). In the worst case, G contains 2K directed edges for every description in E1∪ E2 , i.e., |V|max =2·K· (|E1|+|E2|) . Thus, the overall complexity is linear with respect to the number of input descriptions, i.e., O(|E1|+|E2|) , yielding high scalability. 4.1 Implementation in Spark Figure 4 shows the architecture of MinoanER implementation in Spark. Each process is executed in parallel for different chunks of input, in different Spark workers. Each dashed edge represents a synchronization point, at which the process has to wait for results produced by different data chunks (and different Spark workers). In more detail, Algorithm 1 is adapted to Spark by applying name blocking simultaneously with token blocking and the extraction of top neighbors per entity. Name blocking and token blocking produce the sets of blocks BN and BT , respectively, which are part of the algorithm’s input. The processing of those blocks in order to estimate the α and β weights (Lines 5-9 for BN and Lines 10-18 for BT ) takes place during the construction of the blocks. The extraction of top neighbors per entity (Line 20) runs in parallel to these two processes and its output, along with the β weights, is given to the last part of the graph construction, which computes the γ weights for all entity pairs with neighbors co-occuring in at least one block (Lines 21-33). To minimize the overall run-time, Algorithm 2 is adapted to Spark as follows: R1 (Lines 2-4) is executed in parallel with name blocking and the matches it discovers are broadcasted to be excluded from subsequent rules. R2 (Lines 5-9) runs after both R1 and token blocking have finished, while R3 (Lines 10-23) runs after both R2 and the computation of neighbor similarities have been completed, skipping the already identified (and broadcasted) matches. R4 (Lines 24-26) runs in the end, providing the final, filtered set of matches. Note that during the execution of every rule, each Spark worker contains only the partial information of the disjunctive blocking graph that is necessary to find the match of a specific node (i.e., the corresponding lists of candidates based on names, values, or neighbors). 5 RELATED WORK To the best of our knowledge, there is currently no other Webscale ER framework that is fully automated, non-iterative, schemaagnostic and massively parallel, at the same time. For example, WInte.r [ 22 ] is a framework that performs multi-type ER, also incorporating the steps of blocking, schema-level mapping and data fusion. However, it is implemented in a sequential fashion and its solution relies on a specific level of structuredness, i.e., on a schema followed by the instances to be matched. Dedoop [ 20 ] is a highly scalable ER framework that comprises the steps of blocking and supervised matching. However, it is the user that is responsible for selecting one of the available blocking and learning methods and for fine-tuning their internal parameters. This approach is also targeting datasets with a predefined schema. Dedupe [ 16 ] is a scalable open-source Python library (and a commercial tool built on this library) for ER; however, it is not fully automated, as it performs active learning, relying on human experts to decide for a first few difficult matching decisions. Finally, we consider progressive ER (e.g., [ 1 ]) orthogonal to our approach, as it aims to retrieve as many matches as possible as early as possible. In this context, we compare MinoanER independently to stateof-the-art matching and blocking approaches for Web data. Entity Matching. Two types of similarity measures are commonly used for entity matching [ 21 , 31 ]. (i) Value-based similarities (e.g., Jaccard, Dice) usually assess the similarity of two descriptions based on the values of specific attributes. Our value similarity is a variation of ARCS, a Meta-blocking weighting scheme [ 12 ], which disregards any schema information and considers each entity description as a bag of words. Compared to 379 ARCS, though, we focus more on the number than the frequency of common tokens between two descriptions. (ii) Relational similarity measures additionally consider neighbor similarity by exploiting the value similarity of (some of) the entities’ neighbors. Based on the nature of the matching decision, ER can be characterized as pairwise or collective. The former relies exclusively on the value similarity of descriptions to decide if they match (e.g., [ 20 ]), while the latter iteratively updates the matching decision for entities by dynamically assessing the similarity of their neighbors (e.g., [ 2 ]). Typically, the starting point for this similarity propagation is a set of seed matches identified by a value-based blocking. For example, SiGMa [ 21 ] starts with seed matches having identical entity names. Then, it propagates the matching decisions on the ‘compatible’ neighbors, which are linked with pre-aligned relations. For every new matched pair, the similarities of the neighbors are recomputed and their position in the priority queue is updated. LINDA [ 4 ] differs by considering as compatible neighbors those connected with relations having similar names (i.e., small edit distance). However, this requirement rarely holds in the extreme schema heterogeneity of Web data. RiMOM-IM [ 23 , 31 ] is a similar approach, introducing the following heuristic: if two matched descriptions e1,e′ 1 are connected via aligned relations r and r′ and all their entity neighbors via r and r′ , except e2 and e′ 2 , have been matched, then e2and e′ 2are also considered matches. All these methods employ Unique Mapping Clustering for detecting matches: they place all pairs into a priority queue, in decreasing similarity. At each iteration, the top pair is considered a match, if none of its entities has been already matched. The process ends when the top pair has a similarity lower than t. MinoanER employs Unique Mapping Clustering, too. Yet, it differs from SiGMa, LINDA and RiMOM-IM in five ways: (i) the matching process iterates over the disjunctive blocking graph, instead of the initial KBs. (ii) MinoanER employs statistics to automatically discover distinctive entity names and important relations. (iii) MinoanER exploits different sources of matching evidence (values, names and neighbors) to statically identify candidate matches already from the step of blocking. (iv) MinoanER does not aggregate different similarities in one similarity score; instead, it uses a disjunction of the different evidence it considers. (v) MinoanER is a static collective ER approach, in which all sources of similarity are assessed only once per candidate pair. By considering a composite blocking not only on the value but also on the neighbors similarity, we discover in a non-iterative way most of the matches returned by the data-driven convergence of existing systems, or even more (see Section 6). PARIS [ 33 ] uses a probabilistic model to identify matches, based on previous matches and the functional nature of entity relations. A relation is considered functional if, for a source entity, there is only one destination entity. If r(x,y) is a function in one KB and r(x,y′) a function in another KB, then y and y′ are considered matches. The functionality of a relation and the alignment of relations along with previous matching decisions determine the decisions in subsequent iterations. Unlike MinoanER, PARIS cannot deal with structural heterogeneity, while it targets both ontology and instance matching. Finally, [ 30 ] parallelizes the collective ER approach of [ 2 ], relying on a black-box matching and exploits a set of heuristic rules for structured entities. It essentially runs multiple instances of the matching algorithm in subsets of the input entities (similar to blocks), also keeping information for all the entity neighbors, needed for similarity propagation. Since some rules may require the results of multiple blocks, an iterative message-passing framework is employed. Rather than a block-level synchronization, the MinoanER parallel computations in Spark require synchronization only across the 4 generic matching rules (see Figure 4). Regarding the matching rules, the ones employed by MinoanER based on values and names are similar to rules that have already been employed in the literature individually (e.g., in [ 21 , 23 , 31 ]). In this work, we use a combination of those rules for the first time, also introducing a novel rank aggregation rule to incorporate value and neighbor matching evidence. Finally, the idea of reciprocity has been applied to enhance the results of Meta-blocking [ 28 ], but was never used in matching. Blocking. Blocking techniques for relational databases [ 6 ] rely on blocking keys defined at the schema-level. For example, the Sorted Neighborhood approach orders entity descriptions according to a sorting criterion and performs blocking based on it; it is expected that matching descriptions will be neighbors after the sorting, so neighbor descriptions constitute candidate matches [ 17 ]. Initially, entity descriptions are lexicographically ordered based on their blocking keys. Then, a window, resembling a block, of fixed length slides over the ordered descriptions, each time comparing only the contents of the window. An adaptive variation of the sorted neighborhood method is to dynamically decide on the size of the window [ 35 ]. In this case, adjacent blocking keys in the sorted descriptions that are significantly different from each other, are used as boundary pairs, marking the positions where one window ends and the next one starts. Hence, this variation creates non-overlapping blocks. In a similar line of work, the sorted blocks method [ 11 ] allows setting the size of the window, as well as the degree of desired overlap. Another recent schema-based blocking method uses Maximal Frequent Itemsets (MFI) as blocking keys [ 19 ] – an itemset can be a set of tokens. Abstractly, each MFI of a specific attribute in the schema of a description defines a block, and descriptions containing the tokens of an MFI for this attribute are placed in a common block. Using frequent itemsets to construct blocks may significantly reduce the number of candidates for matching pairs. However, since many matching descriptions share few, or even no common tokens, further requiring that those tokens are parts of frequent itemsets is too restrictive. The same applies to the requirement for a-priori schema knowledge and alignment, thus resulting in many missed matches in the Web of Data. Although blocking has been extensively studied for tabular data, the proposed approaches cannot be used for the Web of Data, since their blocking keys rely on the existence of a global schema. However, the use of schema-based blocking keys is inapplicable to the Web of Data, due to its extreme schema heterogeneity [ 15 ]: entity descriptions do not follow a fixed schema, as even a single description typically uses attributes defined in multiple LOD vocabularies. In this context, schema-agnostic blocking methods are needed instead. Yet, the schema-agnostic functionality of most blocking methods requires extensive fine-tuning to achieve high effectiveness [ 29 ]. The only exception is token blocking, which is completely parameter-free [ 26 ]. Another advantage of token blocking is that it allows for computing value similarity from its blocks, as they contain entities with identical blocking keys – unlike other methods like Dedoop [ 20 ] and Sorted Neighborhood [17], whose blocks contain entities with similar keys. SiGMa [ 21 ] considers descriptions with at least two common tokens as candidate matches, which is more precise than our token blocking, but misses more matches. The missed matches will be considered in subsequent iterations, if their neighbor similarity is 380 Table 1: Dataset statistics. RestauRexaBBCmusicYAGOrant DBLP DBpedia IMDb E1entities 339 18,492 58,793 5,208,100 E2entities 2,256 2,650,832 256,602 5,328,774 E1triples 1,130 87,519 456,304 27,547,595 E2triples 7,519 14,936,373 8,044,247 47,843,680 E1av. tokens 20.44 40.71 81.19 15.56 E2av. tokens 20.61 59.24 324.75 12.49 E1/E2attributes 7 / 7 114 / 145 27 / 10,953 65 / 29 E1/E2relations 2 / 2 103 / 123 9 / 953 4 / 13 E1/E2types 3 / 3 4 / 11 4 / 59,801 11,767 / 15 E1/E2vocab. 2 / 2 4 / 4 4 / 6 3 / 1 Matches 89 1,309 22,770 56,683 strong, whereas MinoanER identifies such matches from the step of blocking. RiMOM-IM [ 31 ] computes the tokens’ TF-IDF weights, takes the top-5 tokens of each entity, and constructs a block for each one, along with the attribute this value appears. Compared to the full automation of MinoanER, this method requires attribute alignment. [ 25 ] iteratively splits large blocks into smaller ones by adding attributes to the blocking key. This leads to a prohibitive technique for voluminous KBs of high Variety. Disjunctive blocking schemes have been proposed for KBs of high [ 18 ] and low [ 3 ] levels of schema heterogeneity. Both methods, though, are of limited applicability, as they require labelled instances for their supervised learning. In contrast, MinoanER copes with the Volume and Variety of the Web of Data, through an unsupervised, schema-agnostic, disjunctive blocking. Finally, LSH blocking techniques (e.g., [ 24 ]) hash descriptions multiple times, using a family of hash functions, so that similar descriptions are more likely to be placed into the same bucket than dissimilar ones. This requires tuning a similarity threshold between entity pairs, above which they are considered candidate matches. This tuning is non-trivial, especially for descriptions from different domains, while its effectiveness is limited for nearly similar entities (see Figure 2). 6 EXPERIMENTAL EVALUATION In this section, we thoroughly compare MinoanER to state-of-theart tools and a heavily fine-tuned baseline method. Experimental Setup. All experiments were performed on top of Apache Spark v2.1.0 and Java 8, on a cluster of 4 Ubuntu 16.04.2 LTS servers. Each server has 236GB RAM and 36 Intel(R) Xeon(R) E5-2630 v4 @2.20GHz CPU cores. Datasets. We use four established benchmark datasets with entities from real KBs. Their technical characteristics appear in Table 1. All KBs contain relations between the described entities. Restaurant 7 contains descriptions of restaurants and their addresses from two different KBs. It is the smallest dataset in terms of the number of entities, triples, entity types 8 , as well as the one using the smallest number of vocabularies. We use it for two reasons: (i) it is a popular benchmark, created by the Ontology Alignment Evaluation Initiative, and (ii) it offers a good example of a dataset with very high value and neighbor similarity between matches (Figure 2), involving the easiest pair of KBs to resolve. Rexa-DBLP 9 contains descriptions of publications and their authors. The ground truth contains matches between both publications and authors. This dataset contains strongly similar matches in terms of values and neighbors (Figure 2). Although it is relatively 7http://oaei.ontologymatching.org/2010/im/ 8Extracted using the attribute w3.org/1999/02/22-rdf-syntax-ns#type. 9oaei.ontologymatching.org/2009/instances/ Table 2: Block statistics. Restaurant RexaBBCmusicYAGODBLP DBpedia IMDb |BN|83 15,912 28,844 580,518 |BT|625 22,297 54,380 495,973 | |BN| | 83 6.71·1071.25·1076.59·106 | |BT| | 1.80·1036.54·1081.73·1082.28·1010 |E1| · | E2|7.65·1054.90·1010 1.51·1010 2.78·1013 Precision 4.95 1.81·10−40.01 2.46·10−4 Recall 100.00 99.77 99.83 99.35 F1 9.43 3.62·10−40.02 4.92·10−4 easy to resolve, Table 1 shows that it exhibits the greatest difference with respect to the size of the KBs to be matched (DBLP is 2 orders of magnitude bigger than Rexa in terms of descriptions, and 3 orders of magnitude in terms of triples). BBCmusic-DBpedia [ 14 ] contains descriptions of musicians, bands and their birthplaces, from BBCmusic and the BTC2012 version of DBpedia 10 . In our experiments, we consider only entities appearing in the ground truth, as well as their immediate inand out-neighbors. The most challenging characteristic of this dataset is the high heterogeneity between its two KBs in terms of both schema and values: DBpedia contains ∼ 11,000 different attributes, ∼ 60,000 entity types, 953 relations, the highest number of different vocabularies (6), while using on average 4 times more tokens than BBCmusic to describe an entity. The latter feature means that all normalized, set-based similarity measures like Jaccard fail to identify such matches, since a big difference in the token set sizes yields low similarity values (see Figure 2). A thorough investigation has shown that in the median case, an entity description in this dataset contains only 2 words in its values that are used by both KBs [14]. YAGO-IMDb [ 33 ] contains descriptions of movie-related entities (e.g., actors, directors, movies) from YAGO 11 and IMDb 12 . Figure 2 shows that a large number of matches in this dataset has low value similarity, while a significant number has high neighbor similarity. Moreover, this is the biggest dataset in terms of entities and triples, challenging the scalability of ER tools, while it is the most balanced pair of KBs with respect to their relative size. Baselines. In our experiments, we compare MinoanER against four state-of-the-art methods: SiGMa, PARIS, LINDA and RiMOM. PARIS is openly available, so we ran its original implementation. For the remaining tools, we report their performance from the original publications 13 . We also consider BSL, a custom baseline method that receives as input the disjunctive blocking graph G , before pruning, and compares every pair of descriptions connected by an edge in G . The resulting similarities are then processed by Unique Mapping Clustering. Unlike MinoanER, though, BSL disregards all evidence from entity neighbors, relying exclusively on value similarity. Yet, it optimizes its performance through a series of well-established string matching methods that undergo extensive fine-tuning on the basis of the ground-truth. In more detail, we consider numerous configurations for the four parameters of BSL in order to maximize its F1: (i) The schema-agnostic representation of the values in every entity. BSL uses token n -grams for this purpose, with n∈ {1,2,3} , thus representing every resource by the token uni-/bi-/tri-grams that appear 10datahub.io/dataset/bbc-music, km.aifb.kit.edu/projects/btc-2012/ 11www.yago-knowledge.org 12www.imdb.com 13 RiMOM-IM [ 31 ] is openly available, but no execution instructions were made available to us. 381