# How to reduce the search space of Entity Resolution: with Blocking or
Nearest Neighbor search? [Experiment, Analysis & Benchmark Papers]

George Papadakis1, Marco Fisichella2, Franziska Schoger2, George Mandilaras1,
Nikolaus Augsten3, Wolfgang Nejdl2 1National and Kapodistrian University of
Athens, Greece {gpapadis<EMAIL_ADDRESS>
2L3S Research Center, Germany {mfisichella, schoger<EMAIL_ADDRESS>
3University of Salzburg, Austria<EMAIL_ADDRESS>
###### Abstract.

Entity Resolution suffers from quadratic time complexity. To increase its time
efficiency, three kinds of filtering techniques are typically used for
restricting its search space: (i) blocking workflows, which group together
entity profiles with identical or similar signatures, (ii) string similarity
join algorithms, which quickly detect entities more similar than a threshold,
and (iii) nearest-neighbor methods, which convert every entity profile into a
vector and quickly detect the closest entities according to the specified
distance function. Numerous methods have been proposed for each type, but the
literature lacks a comparative analysis of their relative performance. As we
show in this work, this is a non-trivial task, due to the significant impact
of configuration parameters on the performance of each filtering technique. We
perform the first systematic experimental study that investigates the relative
performance of the main methods per type over 10 real-world datasets. For each
method, we consider a plethora of parameter configurations, optimizing it with
respect to recall and precision. For each dataset, we consider both schema-
agnostic and schema-based settings. The experimental results provide novel
insights into the effectiveness and time efficiency of the considered
techniques, demonstrating the superiority of blocking workflows and string
similarity joins.

PVLDB Reference Format: George Papadakis, Marco Fisichella, Franziska Schoger,
George Mandilaras, Nikolaus Augsten, Wolfgang Nejdl. How to reduce the search
space of Entity Resolution? With Blocking or Nearest Neighbor search? PVLDB,
14(1): XXX-XXX, 2020.
doi:XX.XX/XXX.XX ††This work is licensed under the Creative Commons BY-NC-ND
4.0 International License. Visit https://creativecommons.org/licenses/by-nc-
nd/4.0/ to view a copy of this license. For any use beyond those covered by
this license, obtain permission by emailing<EMAIL_ADDRESS>Copyright is held
by the owner/author(s). Publication rights licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097.
doi:XX.XX/XXX.XX

##  1\. Introduction

Entity Resolution (ER) is a well-studied problem that aims to identify so-
called duplicates or matches, i.e., different entity profiles that describe
the same real-world object (Getoor and Machanavajjhala, 2012). ER constitutes
a crucial task in a number of data integration tasks, which range from Link
Discovery for interlinking the sources of the Linked Open Data Cloud to data
analytics, query answering, object-oriented searching and data evolution (Dong
and Srivastava, 2015; Christen, 2012a; Elmagarmid et al., 2007).

Due to its quadratic time complexity, ER typically scales to large data
through the Filtering-Verification framework (Christen, 2012a; Getoor and
Machanavajjhala, 2012). The first step (_filtering_) constitutes a coarse-
grained, rapid phase that restricts the computational cost to the most
promising matches, a.k.a. candidate pairs. This is followed by the
_verification_ step, which analytically examines every candidate pair in order
to decide whether its constituent entity profiles are duplicates or not.

Verification is called _matching_ in the ER literature (Christen, 2012a; Dong
and Srivastava, 2015; Christophides et al., 2015). Numerous matching methods
have been proposed, with their majority relying on similarity functions that
compare the textual values of entity profiles (Dong and Srivastava, 2015;
Christophides et al., 2015; Papadakis et al., 2021; Christen, 2012a). Early
attempts were rule-based, comparing similarity values with thresholds, but
more recent techniques rely on learning, i.e., they usually model matching as
a binary classification task (match, non-match) (Papadakis et al., 2021).
Using a labelled training dataset, (semi-)supervised, active, and deep
learning techniques are adapted to ER (Barlaug and Gulla, 2021). In some
cases, a clustering step is subsequently applied on the resulting similarity
scores in order to refine the output (Hassanzadeh et al., 2009).

In this work, we are interested in filtering methods, which significantly
reduce the search space of ER. The performance of a filtering technique is
assessed along three dimensions: recall, precision, and runtime efficiency. A
good filter stands out by:

  1. (1)

High recall. The candidate pairs involve as many duplicates as possible, thus
limiting the impact on verification’s recall.

  2. (2)

High precision. The candidate pairs involve as few false positives (i.e., non-
matching pairs) as possible. The higher precision is, the higher is the
reduction in the search space.

  3. (3)

High time efficiency, so that the overhead of filtering on the overall run-
time of ER is limited.

Ideally, filtering should also be directly applicable to the input data. For
this reason, we exclusively consider methods that require no labelled training
instances, which often are not available or expensive to produce
(Thirumuruganathan et al., 2021).

The filtering methods can be organized in three main types (Papadakis et al.,
2020b):

  1. (1)

The blocking methods extract one or more signatures from every entity profile
and form clusters of profiles with identical or similar signatures (Papadakis
et al., 2016; Christen, 2012b, a).

  2. (2)

The string similarity join methods identify quickly pairs of profiles that
exceed a specific similarity threshold (Mann et al., 2016; Jiang et al.,
2014).

  3. (3)

The nearest neighbor (NN) methods index part or all of the input data and
treat every entity profile as a query, to which they return the most similar
candidates (Aumüller et al., 2020).

Although the three types of filtering techniques in part follow very different
approaches, they all receive the same input (the entity profiles) and produce
the same kind of output (candidate pairs).

To the best of our knowledge, no previous work systematically examines the
relative performance of these three different kinds of methods. Previous works
examine each type independently: the main blocking methods are empirically
evaluated in (Christen, 2012b; Papadakis et al., 2015, 2016), the string
similarity joins in (Fier et al., 2018; Mann et al., 2016; Jiang et al.,
2014), and the NN methods in (Aumüller et al., 2020). Note that all studies on
string similarity joins and NN methods are independent of ER, as explained in
Section 2. Note also that in some of the previous works, a representative
blocking method is used as baseline method for an NN method, e.g.,
Standard/Token Blocking is compared to DeepBlocker in (Thirumuruganathan et
al., 2021). Typically, though, the blocking method is treated as an
independent approach, instead of a part of a blocking workflow, as is common
in the literature (Papadakis et al., 2016).

Most importantly, comparing techniques from different categories is a
challenging, non-trivial task, because of their fundamentally different
functionality, which involves a diversity of configuration parameters that
significantly affect their performance. Yet, there is _no_ systematic fine-
tuning approach that is generic enough to apply to all filter methods. For
example, the step-by-step configuration optimization proposed in (Papadakis et
al., 2016) applies to blocking pipelines, but not to the single-stage
similarity joins and NN methods.

In this work, we perform the first thorough and systematic experimental study
that covers all three types of filtering methods. To ensure a fair comparison,
every approach is represented by its best performance per dataset, as it is
determined after an exhaustive fine-tuning with respect to a common
performance target that considers several thousand different parameter
configurations. This approach is applied to 5 blocking workflows, 3 string
similarity join algorithms and 6 NN methods over 10 real-world datasets. For
each type of methods, we also consider at least one baseline method with
default parameter configuration. In each dataset, we consider both schema-
agnostic and schema-based settings: the former take into account all
information within an entity, essentially treating it as a long textual value,
while the latter focus exclusively on the values of the most informative
attribute.

Overall, we make the following contributions:

  * •

We propose a configuration optimization task as a means of comparing all types
of filtering methods on an equal basis.

  * •

We present a qualitative analysis of the filtering methods for ER.

  * •

We perform a thorough experimental analysis that systematically compares 14
state-of-the-art, fine-tuned filtering approaches and 4 baseline methods with
default configurations over 10 real-world datasets and 2 schema settings – two
methods, SCANN and kNN-Join, are applied to ER for the first time. The end
results provide interesting insights into the behaviour of the considered
techniques, with blocking workflows and string similarity joins consistently
achieving the top performance. Among them, kNN-Join is the most usable, due to
its intuitive configuration parameters.

  * •

We have publicly released all our code and data111See
https://github.com/scify/JedAIToolkit for more details..

The main part of the paper is structured as follows: Section 2 discusses the
related works, while Section 3 provides background knowledge on filtering and
defines formally the configuration optimization task. We elaborate on the
filtering methods in Section 4 and present their qualitative and quantitative
analyses in Sections 5 and 6, respectively. Section 7 concludes with the main
findings of our experimental analysis along with directions for future
research.

##  2\. Related Work

There has been a plethora of works examining the relative performance of
blocking methods. The earliest systematic studies were presented in (Christen,
2012b, a). They focus exclusively on schema-based settings in combination with
several user-defined parameter configurations. Most importantly, they solely
consider the first step of blocking workflows, namely block building.

These studies were extended in (Papadakis et al., 2015), which examines the
same block building methods and configurations, but applies them to schema-
agnostic settings, too. The experimental outcomes suggest that recall raises
significantly, when compared to the schema-based settings, while requiring no
background knowledge about the given data and the quality of its schema. They
also suggest that the sensitivity to parameter configuration is significantly
reduced.

Building on these works, the experimental analysis in (Papadakis et al., 2016)
examines the relative performance of the blocking workflows in schema-agnostic
settings. In particular, it considers blocking workflows formed by exactly
three steps: block building, block filtering and comparison cleaning. In our
work, we extend this pipeline by adding block purging as a second step that
further reduces the candidate pairs. We also treat block purging and filtering
as optional steps, reporting the best performance among four different
pipelines.

Another major difference is that (Papadakis et al., 2016) optimizes the
configuration parameters in a step-by-step manner: first, the performance of
block building is optimized and then, block filtering is fine-tuned by
receiving as input the output of optimized block building as so on for
comparison cleaning. In contrast, we consider a holistic approach to
configuration optimization, fine-tuning all steps in a blocking workflow
simultaneously. As explained in (Papadakis et al., 2019; Papadakis et al.,
2020a), this approach consistently outperforms the step-by-step fine-tuning,
because it considers a significantly larger set of possible configurations and
because it is not confined to local maxima per workflow step.

We also go beyond (Papadakis et al., 2016, 2016; Christen, 2012b, a) in two
more ways: (i) we systematically fine-tune blocking workflows in the context
schema-based settings, and (ii) we compare blocking workflows with similarity
joins and NN methods. Based on the results of (Papadakis et al., 2016, 2016;
Christen, 2012b, a), we select the following top-performing methods for block
building: Standard, (Extended) Q-Grams and (Extended) Suffix Arrays Blocking.
For their configuration, we use the same parameters as in (Papadakis et al.,
2016).

The relative performance of similarity join methods is examined in (Fier et
al., 2018; Mann et al., 2016; Jiang et al., 2014). These analyses, though,
exclusively evaluate the runtime performance of the main methods. Recall and
precision are not considered, because they are identical across all
approaches, i.e., all methods retrieve the same pairs of entities that exceed
a similarity threshold. These pairs, which are not necessarily matching, have
not been evaluated with respect to the recall and precision of ER. As a
result, these studies are not useful in assessing the performance of string
similarity joins for ER.

The state-of-the-art NN methods are experimentally compared in (Aumüller et
al., 2020), but the evaluation measures are restricted to throughput, i.e.,
executed queries per second, and to recall, i.e., the portion of retrieved
vectors that are indeed the nearest ones with respect to a specific distance
function (e.g., the Euclidean one). This is different from ER recall, as the
closest vectors are not necessarily matching. Based on this analysis, we
select the following top-performing NN methods: Cross-polytope and Hyperplane
LSH, FAISS and SCANN.

##  3\. Preliminaries

We define an entity profile $e_{i}$ as the set of textual name-value pairs,
i.e., $e_{i}=\\{\langle n_{j},v_{j}\rangle\\}$, that describes a real-world
object (Papadakis et al., 2015, 2016). This model covers most established data
formats, such as the structured records in relational databases and the semi-
structured instance descriptions in RDF data. Two entities, $e_{i}$ and
$e_{j}$, that pertain to the same real-world object ($e_{i}\equiv e_{j}$) are
called duplicates or matches.

Entity Resolution is distinguished into two main tasks (Christophides et al.,
2015; Christen, 2012a):

  1. (1)

Clean-Clean ER or Record Linkage, which receives as input two sets of entity
profiles, $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ that are individually
duplicate-free, but overlapping, and

  2. (2)

Dirty ER or Deduplication, whose input comprises a single set of entity
profiles, $\mathcal{E}$, with duplicates in itself.

In both cases, the output consists of the detected duplicate profiles.
Following (Konda et al., 2016; Thirumuruganathan et al., 2021; Mudgal et al.,
2018a), we exclusively consider Clean-Clean ER in the following, which also
fits naturally to the index-query scheme of nearest neighbor search
algorithms, as shown in Figure 2.

In this work, we focus on filtering methods, which receive as input
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ and produce a set of candidate pairs
$\mathcal{C}$, which are highly likely to be duplicates and should be
analytically examined during the verification step. To measure the
effectiveness of filtering, the following measures are typically used
(Christophides et al., 2015; Papadakis et al., 2015, 2016; Christen, 2012b;
Elfeky et al., 2002):

  1. (1)

Pair Completeness ($PC$) expresses recall, estimating the portion of the
duplicate pairs in $\mathcal{C}$ with respect to those in the groundtruth:
$PC(\mathcal{C},\mathcal{E}_{1},\mathcal{E}_{2})=|\mathcal{D}(\mathcal{C})|/|\mathcal{D}(\mathcal{E}_{1}\times\mathcal{E}_{2})|$,
where $\mathcal{D}(x)$ denotes the set of duplicates in set $x$.

  2. (2)

Pairs Quality ($PQ$) captures precision, estimating the portion of comparisons
in $\mathcal{C}$ that correspond to real duplicates:
$PQ(\mathcal{C})=|\mathcal{D}(\mathcal{C})|/|\mathcal{C}|$.

All measures result in values in the range $[0,1]$, with higher values
indicating higher effectiveness. Note that there is a trade-off between $PC$
and $PQ$: the larger $C$ is, the higher $PC$ gets at the cost of lower $PQ$,
and vice versa for a smaller set of candidates. The goal of filtering is to
achieve a good balance between these measures.

In this context, we formalize the following configuration optimization task,
which enables the comparison of fundamentally different filtering techniques
on an equal basis:

###### Problem 1 (Configuration Optimization).

Given two sets of entity profiles, $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$, a
filter method, and a threshold $\tau$ on the pair completeness (PC),
configuration optimization fine-tunes the parameters of the filtering method
such that the resulting set of candidates $\mathcal{C}$ on $\mathcal{E}_{1}$
and $\mathcal{E}_{2}$ maximizes $PQ$ for $PC\geq\tau$.

In this study, we chose $\mathbf{\tau=0.9}$ for the threshold on pair
completeness. The reason we require high filtering recall is that it
determines the final recall ER; the duplicate pairs that are not included in
the set of candidates $C$ cannot be detected by most matching methods, as they
typically consider local information, e.g., the (deep) learning-based methods
that treat matching as a binary classification task (Konda et al., 2016;
Mudgal et al., 2018a). We could set a different limit for $PC$, e.g., 0.85 or
0.95, but we deem 0.9 as a good balance between those ER applications that
focus on recall and those focusing on precision.

Regarding time efficiency, the overall run-time ($RT$) measures the time that
intervenes between receiving the set(s) of entity profiles as input and
producing the set of candidate pairs as output. $RT$ should be minimized to
restrict the overhead of filtering on ER.

##  4\. Filtering Methods

###  4.1. The two paradigms of filtering

Blocking methods operate as follows: first, they associate every input entity
with one or (usually) more signatures and then, they cluster together entities
with identical or similar signatures into blocks. Every pair of entities that
appears in at least one block is considered a matching candidate. The
resulting blocks contain two unnecessary types of candidates in the sense that
verifying them lowers precision, without any benefit for recall:

  1. (1)

The redundant candidates are repeated across different blocks, because every
entity typically participates in multiple ones and, thus, the blocks are
overlapping.

  2. (2)

The superfluous candidates consist of non-matching entities.

To eliminate the former and reduce the latter, Block and comparison cleaning
are applied to the initial blocks, restructuring them based on global
patterns. Figure 1 depicts the complete workflow for blocking (Papadakis et
al., 2020b). Initially, a set of blocks is created by at least one Block
Building method. The initial block collection is then processed by two coarse-
grained block cleaning techniques, Block Purging and Block Filtering. Both
produce a new, smaller block collection, $B^{\prime}$ and $B^{\prime\prime}$,
respectively, but are optional and can be omitted, e.g., in the case of
schema-based blocks with low levels of redundant and/or superfluous
comparisons. Finally, a comparison cleaning technique is applied, whose fine-
grained functionality decides for individual comparisons whether they should
be retained or discarded; in this step, redundant and superfluous candidates
are subject to removal. This is a mandatory step, as at least the redundant
comparisons should be removed.

A fundamentally different approach is followed by string similarity joins and
NN methods. Instead of extracting signatures from the input entity profiles,
they organize the input set $\mathcal{E}_{1}$ into an index $I$ (e.g., an
inverted index) and use the other dataset as a query set, as shown in Figure
2. This means that the set of candidate pairs $C$ is formed by probing the
index $I$ for every entity profile $e_{2}\in\mathcal{E}_{2}$ and aggregating
all query results. To restrict the noise in this process, the textual
attribute values are typically cleaned from stop-words and reduced them to
their base/root form through lemmatization or stemming (e.g., “blocks” becomes
“block”) (Manning et al., 2008). The attribute values may also be transformed
into (pre-trained) embeddings, i.e., into fixed-length, dense and distributed
representations that give rise to semantic similarities (Wang et al., 2020).
These optional, preprocessing steps apply to both input sets of entity
profiles. After cleaning, we get $\mathcal{E}^{\prime}_{1}$ and
$\mathcal{E}^{\prime}_{2}$, which remain in textual form, but after embedding,
we get two sets of dense numeric vectors, $\mathcal{VE}_{1}$ and
$\mathcal{VE}_{2}$, respectively.

Note that the blocking workflows produce redundant comparisons as intermediate
results of block building, which are eliminated during comparison cleaning. In
contrast, the other filtering methods do not produce redundant comparisons, as
every query entity from $\mathcal{E}_{2}$ is associated with a set of indexed
entities from $\mathcal{E}_{1}$.

Figure 1. The complete blocking workflow. Dotted contours indicate optional
steps.

###  4.2. Blocking workflows

Block building. Based on the results of the past experimental studies
(Christen, 2012b; Papadakis et al., 2015, 2016), we consider the following
established techniques:

1) Standard Blocking. Given an entity, it tokenizes the considered attribute
values on whitespace and uses the resulting tokens as signatures. Hence, every
block corresponds to a distinct token, involving all entities that contain it
in the selected attribute value(s).

2) Q-Grams Blocking. To accommodate character-level errors, it defines as
signatures the set of $q$-grams that are extracted from the tokens of Standard
Blocking. In other words, every block corresponds to a distinct $q$-gram,
encompassing all entities with that $q$-gram in any of the considered values.

3) Extended Q-Grams Blocking. Instead of individual $q$-grams, the signatures
of this approach are constructed by concatenating at least $L$ $q$-grams,
where $L=max(1,\lfloor k\cdot T\rfloor)$, $k$ is the number of $q$-grams
extracted from the original key/token and $T\in[0,1)$ is a threshold that
reduces the number of combinations as its value increases. Compared to Q-Grams
Blocking, the resulting blocks are smaller, but contain candidate pairs that
share more content.

4) Suffix Arrays Blocking. Another way of accommodating character-level errors
in the signatures of Standard Blocking is to consider their suffixes, as long
as they comprise a minimum number of characters $l_{min}$. In fact, every
block corresponds to a token suffix that is longer than $l_{min}$ and appears
in less than $b_{max}$ entities.

5) Extended Suffix Arrays Blocking. This approach generalizes the previous one
by converting the signatures of Standard Blocking in all substrings longer
than $l_{min}$ and less frequent than $b_{max}$ entities.

Example. To illustrate the difference between these blocking methods, consider
as an example the attribute value “Joe Biden”. Standard Blocking produces 2
blocking keys: {Joe, Biden}. With $q=3$, Q-Grams Blocking produces 4 keys:
{Joe, Bid, ide, den}. For $T$=0.9, Extended Q-Grams Blocking combines at least
two $q$-grams from each token, defining the following 5 blocking keys: {Joe,
Bid_ide_den, Bid_ide, Bid_den, ide_den}. Using $l_{min}$=3 and a large enough
$b_{max}$, Suffix Arrays Blocking yields 4 keys: {Joe, Biden, iden, den},
while Extended Suffix Arrays extracts 7 keys: {Joe, Biden, Bide, iden, Bid,
ide, den}.

Note that we exclude Attribute Clustering Blocking (Papadakis et al., 2013),
because it is incompatible with the schema-based settings we are considering
in this work. Note also that we experimented with Sorted Neighborhood
(Papadakis et al., 2015; Christen, 2012a, b), but do not report its
performance, since it consistently underperforms the above methods. The reason
is that this method is incompatible with block and comparison cleaning
techniques that could reduce its superfluous comparisons (Papadakis et al.,
2020b, 2016).

Block cleaning. We consider two complementary methods:

Figure 2. The complete workflow of similarity joins and NN methods. Dotted
contours indicate optional steps.

1) Block Purging (Papadakis et al., 2013). This parameter-free approach
assumes that the larger a block is, the less likely it is to convey matching
pairs that share no other block. Such blocks emanate from signatures that are
stop-words. Therefore, it removes the largest blocks (e.g., those containing
more than half the input entities) in order to significantly increase
precision at a negligible (if any) cost in recall.

2) Block Filtering (Papadakis et al., 2015). It assumes that for a particular
entity $e$, its largest blocks are less likely to associate $e$ with its
matching entity. For every entity $e$, it orders its blocks in increasing size
and retains it in $r$% of the top (smaller) ones – $r$ is called filtering
ratio. This increases precision to a significant extent for slightly lower
recall.

Comparison cleaning. We consider two established methods, but only one of them
can be applied in a blocking workflow, as in (Papadakis et al., 2016):

1) Comparison Propagation (Papadakis et al., 2013). This parameter-free
approach removes all redundant pairs from any block collection without missing
any matches, i.e., it increases precision at no cost in recall. In essence, it
associates every entity with the list of its block ids and retains every
candidate pair only in the block with least common id.

2) Meta-blocking (Papadakis et al., 2014). It targets both redundant and
superfluous comparisons using (i) a weighting scheme, which associates every
candidate pair with a numerical score proportional to the matching likelihood
that is extracted from the blocks shared by its constituent entities, and (ii)
a pruning algorithm, which leverages these scores to decide which candidate
pairs will be retained in the restructured block collection that is returned
as output.

The rationale behind weighting schemes is that the more and smaller blocks two
entities share (i.e., the more and less frequent signatures they share), the
more likely they are to be matching. In this context, the following schemes
have been proposed (Papadakis et al., 2014; Simonini et al., 2016; Papadakis
et al., 2020b): ARCS promotes pairs that share smaller blocks; CBS counts the
blocks the two entities have in common; ECBS extends CBS by discounting the
contribution of entities participating in many blocks; JS computes the Jaccard
coefficient of the block ids associated with the two entities; EJS extends JS
by discounting the contribution of entities participating in many non-
redundant pairs; $\chi^{2}$ estimates to which degree the two entities appear
independently in blocks.

The following pruning algorithms have been proposed in the literature
(Papadakis et al., 2014; Simonini et al., 2016): BLAST retains a pair if its
weight exceeds the average maximum weight of its constituent entities; CEP and
CNP retain the overall top-K pairs and the top-k pairs per entity,
respectively (K and k are automatically configured according to input blocks
characteristics); Reciprocal CNP (RCNP) requires that every retained pair is
ranked in the top-k positions of both constituent entities; WEP discards all
pairs with a weight lower than the overall average one; WNP keeps only pairs
with a weight higher than the average one of at least one of their entities;
Reciprocal WNP (RWNP) requires a weight higher than the average of both
entities.

###  4.3. String similarity joins

Set- or token-based similarity joins. This family of approaches represents
each input entity by a set of so-called _tokens_ ; the similarity of two
entities is assessed as the similarity of their token sets. The similarity
between two sets $A$ and $B$ may be computed using one of the following
normalized measures (Mann et al., 2016) (value range $[0,1]$):

  1. (1)

Cosine similarity $C(A,B)=|A\cap B|/\sqrt{|A|\cdot|B|}$.

  2. (2)

Dice similarity $D(A,B)=2\cdot|A\cap B|/(|A|+|B|)$.

  3. (3)

Jaccard coefficient $J(A,B)=|A\cap B|/|A\cup B|$.

The tokens are extracted from string attributes (the concatenation of all
attribute values in the schema-agnostic settings) by considering the character
$n$-grams (Gravano et al., 2001) (as in Q-Grams Blocking) or by splitting the
strings on whitespace (as in Standard Blocking). Duplicate tokens within one
string are either ignored or de-duplicated by attaching a counter to each
token (Augsten and Böhlen, 2013) (e.g.,
$\\{a,a,b\\}\rightarrow\\{a_{1},a_{2},b_{1}\\}$).

Candidate pairs are formed based on the similarity of two entities according
to some _matching principles_ (Augsten, 2018). The matching principle defines
the policy for forming candidate pairs. We consider two well-known matching
principles in combination with all the aforementioned similarity measures and
tokenization schemes (Silva et al., 2013):

1) _Range join ( $\varepsilon$-Join) (Silva et al., 2013)._ It pairs all
entities that have a similarity no smaller than a user-defined threshold
$\varepsilon$. Numerous efficient algorithms for $\varepsilon$-Join between
two collections of token sets have been proposed (Bayardo et al., 2007;
Chaudhuri et al., 2006; Bouros et al., 2012; Deng et al., 2015; Deng et al.,
2018; Zhu et al., 2019; Mann et al., 2016; Xiao et al., 2011). All of these
techniques produce the exact same set of candidates, but most of them are
crafted for high similarity thresholds (above 0.5), which is not the case in
ER, as shown in Table 9. For this reason, we employ _ScanCount_ (Li et al.,
2008), which is suitable for low similarity thresholds. In essence, it builds
an inverted list on all tokens in token set collection $B$ and for lookup of a
query token set $a\in A$, it performs merge-counts on the posting lists of all
tokens in $a$. Then, it returns all sets that exceed the similarity threshold
$\varepsilon$.

2) _k-nearest-neighbor join (kNN-Join)(Silva et al., 2013)._ Given two
collections, $A$ and $B$, it pairs each element in $a\in A$ with the $k$ most
similar elements in $B$ that have distinct similarity values, i.e., $a$ may be
paired with more than $k$ elements if some of these elements are equidistant
from $a$. The kNN-Join is not commutative, i.e., the order of the join
partners matters. An efficient technique that leverages an inverted list on
tokens that are partitioned into size stripes is the _Cone_ algorithm (Kocher
and Augsten, 2019), which is crafted for label sets in the context of top-$k$
subtree similarity queries. To increase the limited scope of the original
algorithm, we adapted it to leverage ScanCount.

Note that the so-called top-$k$ set similarity joins (Xiao et al., 2009; Yang
et al., 2020) compute the $k$ token set pairs between $A$ and $B$ with the
highest similarities among all possible pairs. This means that they perform a
global join that returns the $k$ top-weighted pairs. In principle, this is
equivalent to $\varepsilon$-Join, if the $k^{th}$ has a similarity equal to
$\varepsilon$. Instead, the kNN-Join performs a local join that returns at
least $k$ pairs per element a$\in$A.

Edit-based similarity joins. A well-known similarity measure between strings
is the _edit distance_ (Navarro, 2001) (also known as Levenshtein distance),
which is the minimum number of character insertions, deletions, or renames
that transforms one string into the other. Computing the edit distance has
quadratic runtime in the length of the strings. Join techniques for the edit
distance strive to avoid edit distance computations by leveraging indices and
filters (Yu et al., 2016). In our experiments, we use PassJoin (Li et al.,
2011), which is the state-of-the-art (Jiang et al., 2014).

###  4.4. Nearest-neighbor (NN) methods

LSH. Locality Sensitive Hashing (Indyk and Motwani, 1998; Fisichella et al.,
2014) constitutes an established solution to the approximate nearest neighbor
problem in high-dimensional spaces. Its goal is to find entities/vectors that
are within $c\cdot R$ distance from a query vector, where $c>1$ is a real
number that represents a user-specified approximation ratio, while $R$ is the
maximum distance of any nearest neighbor vector from the query. LSH is
commonly used as a filtering technique for ER (Karapiperis et al., 2016; Kim
and Lee, 2010; Zhang et al., 2020b; Ebraheem et al., 2018) because of its sub-
linear query performance, which is coupled with a fast and small index
maintenance, and its mathematical guarantee on the query accuracy. We consider
three popular versions:

1) Hyperplane LSH (HP-LSH) (Charikar, 2002). The vectors are assumed to lie on
a unit hypersphere divided by a random hyperplane at the center, formed from a
random direction $r$ and the positioning of the hypersphere with a line
perpendicular to the direction r and through the center. This creates two
equal parts of the hypersphere with $+1$ on the one side and $-1$ on the
other. A vector $v$ is hashed into $h(v)=sgn<r,v>$. For two vectors $v_{1}$
and $v_{2}$ with angle $\alpha$ between them, the probability of collision is
$Pr[h(v_{1})=h(v_{2})]=1-\frac{\alpha}{\pi}$

2) Cross-Polytope LSH (CP-LSH) (et al., 2018). It is a generalization of HP-
LSH. At their core, both HP- and CP-LSH are random spatial partitions of a
d-dimensional unit sphere centered at the origin. The two hash families differ
in how granular these partitions are. The cross-polytope is also known as an
l1-unit ball, where all vectors on the surface of the cross-polytope have the
l1-norm. In CP-LSH, the hash value is the vertex of the cross-polytope closest
to the (randomly) rotated vector. Thus, a cross-polytope hash function
partitions the unit sphere according to the Voronoi cells of the vertices of a
randomly rotated cross-polytope. In the 1-dimensional case, the cross-polytope
hash becomes the hyperplane LSH family.

3) MinHash LSH (MH-LSH) (Broder, 1997; Leskovec et al., 2020). Given two token
sets, this approach approximiates their Jaccard coefficient by representing
each set as a minhash, i.e., a sequence of hash values that are derived from
the minimum values of random permutations. The minhashes are decomposed into a
series of bands consisting of an equal number of rows. This decomposition has
a direct impact on performance: if there are few bands with many rows, there
will be collisions between pairs of objects with a very high Jaccard
similarity; in contrast, when there are many bands with few rows, collisions
occur between pairs of objects with very low similarity. The selected number
of bands ($\\#bands$) and rows ($\\#rows$) approximates a step function, i.e.,
a high-pass filter, which indicates the probability that two objects share the
same hash value: $(1/\\#bands)^{(1/\\#rows)}$.

kNN-Search. We consider three popular frameworks:

1) FAISS (Johnson et al., 2021). This framework provides methods for kNN
searches222FAISS also supports range, i.e., similarity, search. However, our
experiments showed that it consistently underperforms kNN search. For this
reason, we exclude it from our analysis.. Given two sets of (embedding)
vectors, it associates every entry $q$ from the query set with the $k$ entries
from the indexed set that have the smallest distance to $q$. Two approximate
methods are provided: a hierarchical, navigable small world graph method and a
cell probing method with Voroni cells, possibly in combination with product
quantization. We experimented with both of them, but they do not outperform
the exhaustive search (Flat index) with respect to Problem 1. The Flat index
is also recommended by (Johnson et al., 2021), as most of our datasets involve
less than 20,000 entities. For these reasons, we exclude the approximate
methods in the following.

2) SCANN (Guo et al., 2020). This is another versatile framework with very
high throughput. Two are the main similarity measures it supports: dot product
and Euclidean distance. It also supports two types of scoring: brute-force,
which performs exact computations, and asymmetric hashing, which performs
approximate computations, trading higher efficiency for slightly lower
accuracy. In all cases, SCANN leverages partitioning, splitting the indexed
dataset into disjoint sets during training so that every query is answered by
applying scoring to the most relevant partitions.

3) DeepBlocker (Thirumuruganathan et al., 2021). It is the most recent method
based on deep learning, consistently outperforms all others, e.g., AutoBlock
(Zhang et al., 2020b) and DeepER (Ebraheem et al., 2018). It converts
attribute values into embedding vectors using fastText and performs indexing
and querying with FAISS. Its novelty lies in the tuple embedding module, which
converts the set of embeddings associated with an individual entity into a
representative vector. Several different modules are supported, with the
Autoencoder constituting the most effective one under the schema-based
settings. In the schema-agnostic settings, the top-performing is the Hybrid
module, which couples Autoencoder with cross-tuple training, with the
Autoencoder lying in close distance.

##  5\. Qualitative Analysis

Table 1. The scope per type of filtering methods. Scope | Blocking | Similarity Joins | NN methods
---|---|---|---
Set- | Edit- | Sparse | Dense
based | based | vectors | vectors
Syntactic | Schema-based | ✓ | ✓ | ✓ | ✓ | -
Representation | Schema-agnostic | ✓ | ✓ | - | ✓ | -
Semantic | Schema-based | - | - | - | - | ✓
Representation | Schema-agnostic | - | - | - | - | ✓

Taxonomies. To facilitate the use and understanding of the above techniques,
we organize them into two novel taxonomies.

The first one pertains to scope, i.e., the entity representation that lies at
the core of every filtering method. There are two types:

  1. (1)

The syntactic or symbolic representations consider the actual text in an
entity profile, leveraging the co-occurrences of tokens or characters.

  2. (2)

The semantic representations consider the embedding vectors that encapsulate a
textual value, leveraging word-, character- or transformer-based models. In
this work, we exclusively consider the unsupervised, pre-trained embeddings of
fastText (Bojanowski et al., 2017) that have been experimentally verified to
effectively address the out-of-vocabulary cases in ER tasks, which abound in
domain-specific terminology (Thirumuruganathan et al., 2021; Mudgal et al.,
2018b; Fu et al., 2020; Yao et al., 2021; Zhang et al., 2020a).

These types can be combined with both schema-based and schema-agnostic
settings, yielding four fields of scope, as shown in Table 1.

The distinctions introduced by this taxonomy are crucial for two reasons: (i)
the syntactic representations have the advantage of producing intelligible and
interpretable models. That is, it is straightforward to justify a candidate
pair, unlike the semantic representations, whose interpretation is obscure to
non-experts. (ii) the semantic representations involve a considerable overhead
for transforming the textual values into embeddings, even when using pre-
trained models. They also require external resources, which are typically
loaded in main memory, thus increasing the space complexity. Instead, the
methods using syntactic representations are directly applicable to the input
data.

We observe that the NN methods have the broadest scope, being compatible with
all four combinations. The syntactic representations are covered by the sparse
numeric vectors of MinHash LSH; its dimensions correspond to character
k-grams, called k-shingles, and are weighted according to their term frequency
(Leskovec et al., 2020). All other NN methods employ semantic representations
in the form of the dense numeric vectors that are derived from fastText.

In contrast, the edit-based similarity joins have the most narrow scope, as
they are compatible only with schema-based syntactic representations. They
cannot be applied to the schema-agnostic ones, because of the arbitrary order
of words: the attribute values are concatenated into a long text in no
particular order and, thus, two consecutive words might originate from
different attributes, having no semantic relation. This violates the core
assumption of edit-based joins, because they are sensitive to the order of
tokens and characters. For example, the distance of “John Smith” from “Smith
John” is the same (10 edits) as that from the random string “xYXS1.fklt”.
Further, the length difference of the strings has a major impact on the edit
distance, because missing characters must be inserted. For example, “John” is
more similar to “Mike” (4 edits) than to “John Smith” (6 edits). Therefore,
edit-based techniques are not effective in schema-agnostic settings, where the
length of strings that should be similar may vary to a great extent. Instead,
they are more suitable for comparing short textual values that correspond to a
specific attribute, e.g., to detect typos.

In the middle of these two extremes lie the blocking methods and the set-based
similarity joins, which cover both settings of syntactic similarities, being
agnostic to the word order in attribute values.

Table 2. The functionality per non-blocking filtering method. Operation | Similarity Threshold | Cardinality Threshold
---|---|---
Deterministic |  $\varepsilon$-Join, edit-based Join | kNN-Join, FAISS, SCANN
Stochastic | MH-, HP-, CP-LSH | DeepBlocker

The second taxonomy pertains to the internal functionality of filtering
methods. The blocking techniques are already distinguished into lazy and
proactive ones (Papadakis et al., 2016). The former impose no restrictions on
the blocks resulting from their signatures and rely on generic block and
comparison cleaning techniques in order to refine their candidates. To this
category belong Standard and (Extended) Q-Grams Blocking. In contrast, the
proactive methods impose restrictions on their blocks so as to produce a
better set of candidates already from the block building phase. This is the
case with (Extended) Suffix Arrays Blocking, which sets an upper bound on the
size of blocks ($b_{max}$). In general, the lazy methods are simpler than the
proactive ones, which require fine-tuning more parameters.

For the rest of the filtering methods, we define the taxonomy in Table 2,
which comprises two dimensions:

  1. (1)

The type of operation, which can be deterministic, lacking any randomness, or
stochastic, relying on randomness.

  2. (2)

The type of threshold, which can be similarity- or cardinality-
based. The former specifies the minimum similarity of candidate pairs, while
the latter determines the maximum number of candidates per query entity.

The distinctions introduced by this taxonomy are important for two reasons:
(i) The stochastic methods yield slightly different results in each run,
unlike the deterministic ones, which yield a stable performance. This is
crucial in the context of Problem 1, which sets a specific limit on a
particular evaluation measure. For this reason, we set the performance of
stochastic methods as the average one after 10 repetitions. (ii) The
configuration of cardinality-based methods is straightforward and can be
performed a-priori, because it merely depends on the number of input entities.
In contrast, the similarity-based methods depend on data characteristics – the
distribution of similarities, in particular.

Overall, the deterministic, cardinality-based methods offer the highest
usability. To this category belong kNN-Join, FAISS and SCANN. DeepBlocker uses
a cardinality threshold, too, but its tuple embedding model employs neural
networks with random initialization that are trained on automatically
generated random synthetic data, which renders it a stochastic approach. Among
the similarity-based methods, $\varepsilon$-Join and edit-based Join involve a
deterministic operation, unlike the three LSH methods, which are stochastic by
definition: MinHash LSH involves random permutations of the input token sets,
while Hyperplane and CrossPolytope LSH constitute random spatial partitions of
a d-dimensional unit sphere.

Table 3. The configuration space per blocking workflow. | Parameter | Domain
---|---|---
Common |  Block Purging ($BP$) | { -, ✓}
Block Filtering ratio ($BFr$) | [0.025, 1.00] with a step of 0.025
Weighting Scheme ($WS$) |  {ARCS, CBS, ECBS, JS, EJS, $\chi^{2}$}
Pruning Algorithm ($PA$) | CP or {BLAST, CEP, CNP,
RCNP, RWNP, WEP, WNP}
Standard | Block Building | parameter-free
Blocking | Maximum Configurations | 3,440
Q-Grams | $q$ |  $[2,6]$ with a step of 1
Blocking | Maximum Configurations | 17,200
Extended | $q$ |  $[2,6]$ with a step of 1
Q-Grams | $t$ |  $[0.8,1.0)$ with a step of 0.05
Blocking | Maximum Configurations | 68,800
(Ex.) Suffix | $l_{min}$ |  $[2,6]$ with a step of 1
Arrays | $b_{max}$ |  $[2,100]$ with a step of 1
Blocking | Maximum Configurations | 1,702,800

Configuration space. As explained in Section 1, a major aspect of filtering
techniques is the fine-tuning of their configuration parameters, which has a
decisive impact on their performance. For this reason, we combine every method
with a wide range of values for each parameter through grid search. The
domains we considered per parameter and method are reported in Tables 3, 4 and
5.

Starting with Table 3, the common parameters of the blocking workflows include
the presence or absence of Block Purging and the ratio used by Block
Filtering. For the latter, we examined at most 40 values in $[0,1]$, with 1
indicating the absence of Block Filtering. Given that these two steps
determine the upper bound of recall for the subsequent steps, we terminate
their grid search as soon as the resulting $PC$ drops below the target one
(0.9) – in these cases, the number of tested configurations is lower than the
maximum possible one. For comparison cleaning, all methods are coupled with
the parameter-free Comparison Propagation (CP) or one of the 42 Meta-blocking
configurations, which stem from the 6 weighting schemes and the 7 pruning
algorithms.

Standard Blocking involves only the common parameters, unlike the rest of the
block building methods. For their fine-tuning, we experiment with the same
settings as in (Papadakis et al., 2016). Hence, Standard Blocking yields the
lowest maximum configurations, with the proactive (Extended) Suffix Arrays
Blocking yielding by far the highest ones.

In Table 4, we notice that the common parameters of set-based similarity joins
include the absence or presence of cleaning (i.e., stop-word removal and
stemming), the similarity measure as well as the representation model. For the
last two parameters, we consider all options discussed in Section 4.3, i.e.,
three similarity measures in combination with 10 models: whitespace
tokenization (T1G) or character $n$-grams (CnG), with $n\in\\{2,3,4,5\\}$; for
each model, we consider both the set and the multiset of its tokens, with the
latter denoted by appending M at the end of its name (e.g., T1GM).

In addition to these common settings, $\varepsilon$-Join is combined with up
to 100 similarity thresholds. We start with the largest one and terminate the
grid search as soon $PC$ drops below target recall. kNN-Join is coupled with
at most 100 cardinality thresholds, starting from the smallest one and
terminating the grid search as soon $PC$ exceeds the target recall. Another
crucial parameter for kNN-Join is $RVS$, which is true ($\checkmark$) if
$\mathcal{E}_{2}$ should be indexed and $\mathcal{E}_{1}$ should used as the
query set, instead of the opposite. In theory, kNN-Join involves double as
many configurations as $\varepsilon$-Join, but in practice its cardinality
threshold does not exceed 26 (see Table 9 in ), thus reducing significantly
the maximum number of its configurations.

Note that the edit-based join is excluded from Table 4, because its only
parameter is the absence or presence of cleaning. There is no threshold
associated with its distances, since their values depend on the length of the
compared strings. For this reason, we employ a dynamic threshold that
considers as matches the strings whose distance is less than half the length
of the shortest one.

Table 4. The configuration space per set-based similarity join. | Parameter | Domain
---|---|---
Common |  Cleaning ($CL$) | { -, ✓}
Similarity Measure ($SM$) | {Cosine, Dice, Jaccard}
Representation | {T1G, T1GM, C2G, C2GM, C3G,
Model ($RM$) | C3GM, C4G, C4GM, C5G, C5GM}
$\varepsilon$-Join |  Similarity threshold ($t$) | [0.00, 1.00] with a step of 0.01
Maximum Configurations | 6,000
kNN-Join |  Candidates per query ($K$) | [1, 100] with a step of 1
Reverse Datasets ($RVS$) | { -, ✓}
Maximum Configurations | 12,000
Table 5. The configuration space per NN method. | Parameter | Domain
---|---|---
Common |  Cleaning ($CL$) | { -, ✓}
MH-LSH | $\\#bands$ |  $\\#bands\in P(2),\\#rows\in P(2):$ $\\#bands\times\\#rows\in\\{128,256,512\\}$
$\\#rows$
$k$ |  $[2,5]$ with a step of 1
Configurations | 168
HP- & CP- LSH | $\\#tables$ | $2^{n}:n\in\\{0,9\\}$
$\\#hashes$ |  $[1,20]$ with a step of 1
cp dimension | $2^{n}:n\in\\{0,9\\}$
Configurations | 400 (HP), 2,000 (CP)
(a) Threshold-based algorithms
Common |  Rev. Datasets ($RVS$) | { -, ✓}
$K$ |  $[1,5000]$ with an increasing step
FAISS | Max. Configurations | 2,720
SCANN | index | { AH, BF }
similarity |  { DP, LP2 }
Max. Configurations | 10,880
DeepBlocker | Max. Configurations | 2,720
(b) Cardinality-based algorithms

The parameters of NN methods are listed in Table 5. The common parameter is
the absence or presence of cleaning. In MinHash LSH, we configured the number
of bands and rows, restricting both of them to powers of two such that their
product is also a power of two, i.e., 2n with $n\in\\{7,8,9\\}$. For
$k$-shingles, we considered four common values for $k$, i.e., $[2,5]$.

Hyperplane and CrossPolytope LSH two parameters: the number of hash tables
($\\#tables$), i.e., cross-polytopes and hyperplanes, respectively, and the
number of hash functions ($\\#hashes$). We tested the values reported in Table
5, because higher ones increased the query time, without increasing precision.
The number of probes for multi-probe was automatically set to achieve the
target recall.333We used the approach in https://github.com/FALCONN-
LIB/FALCONN/blob/master/src/examples/glove/glove.py. A parameter applying only
to CrossPolytope LSH is the $cp$ dimensionality, which is chosen between 1 and
the smallest power of two larger than the dimension of the embeddings vector
(here 512) (Andoni et al., 2015).

Among the kNN-search NN methods, there are two more common parameters: $RVS$,
which has the same meaning as in kNN-Join, and the cardinality-threshold, $K$.
For the latter, we consider all values in $[1,100]$ with a step of 1, as in
kNN-Join. Given, though, that this is not sufficient in some datasets, we
additionally consider all values in $[105,1000]$ with a step of 5 and all
values in $[1010,5000]$ with a step of 10. In each case, the grid search
starts from the lowest values and terminates as soon as $PC$ reaches the
target recall.

FAISS does not use any other parameter apart from the common ones. It uses the
Flat index in all cases, due to the small size of the input datasets
($<$20,000 vectors in most cases) (Johnson et al., 2021). Our experiments also
demonstrated that the embedding vectors should always be normalized and
combined with the Euclidean distance.

SCANN adds to the common parameters the type of index – asymmetri – hashing
(AH) or brute-force (BF) – and the similarity measure – dot product or
Euclidean distance. There is no clear winner among these options, as shown in
Table 10 (cf. ).

Finally, DeepBlocker adds to the common parameters the tuple embedding model.
We experimented with both top-performing modules, namely AutoEncoder and
Hybrid. In most cases, though, the latter, raised out-of-memory exceptions,
while being a whole order of magnitude slower than the former, as documented
in (Thirumuruganathan et al., 2021). For this reason, we exclusively consider
AutoEncoder in the following.

##  6\. Quantitative Analysis

Setup. All experiments were performed on a laptop with an Intel i7-4710MQ @
2.50GHz with 16GB of RAM, running Ubuntu 18.04.3 LTS. The available memory
should suffice, given that all datasets occupy few MBs on the disk in their
original form. For each time measurement, we performed 10 repetitions and
report the average value. These measurements do not include the time required
to load the input data into main memory.

For the implementation of blocking workflows and similarity join methods, we
employed JedAI’s latest version,
3.2.1444https://github.com/scify/JedAIToolkit. All experiments were run on
Java 15. For MH-LSH, we used java-LSH, version
0.12555https://github.com/tdebatty/java-LSH. For HP- and CP-LSH, we used the
Python wrapper of FALCONN (Andoni et al., 2015), version
1.3.1666https://github.com/FALCONN-LIB/FALCONN. For FAISS, we used the Python
wrapper of version 1.7.2 provided by Facebook
Research777https://github.com/facebookresearch/faiss. For SCANN, we used the
Python implementation of version 1.2.5 provided by Google
Research888https://github.com/google-research/google-
research/tree/master/scann. For DeepBlocker, we used the implementation
provided by the authors999https://github.com/saravanan-
thirumuruganathan/DeepBlocker. FAISS, SCANN and DeepBlocker can exploit GPU
optimizations, but all methods were run on a single CPU to ensure a fair
comparison.

Datasets. We use 10 real-world datasets for Clean-Clean ER that are popular in
the literature (Thirumuruganathan et al., 2021; Mudgal et al., 2018a; Köpcke
et al., 2010; Papadakis et al., 2016). Their technical characteristics are
reported in Table 6. $D_{1}$, which was first used in OAEI
2010101010http://oaei.ontologymatching.org/2010/im, contains restaurant
descriptions. $D_{2}$ encompasses duplicate products from the online retailers
Abt.com and Buy.com (Köpcke et al., 2010). $D_{3}$ matches product
descriptions from Amazon.com and the Google Base data API (GB) (Köpcke et al.,
2010). $D_{4}$ entails bibliographic data from DBLP and ACM (Köpcke et al.,
2010). $D_{5}-D_{7}$ involve descriptions of television shows from TheTVDB.com
(TVDB) and of movies from IMDb and themoviedb.org (TMDb) (Obraczka et al.,
2021). $D_{8}$ matches product descriptions from Walmart and Amazon (Mudgal et
al., 2018a). $D_{9}$ involves bibliographic data from publications in DBLP and
Google Scholar (GS) (Köpcke et al., 2010). $D_{10}$ interlinks movie
descriptions from IMDb and DBpedia (Papadakis et al., 2020a), with the former
corresponding to a different snapshot of IMDb than $D_{5}$ and $D_{6}$. All
datasets are publicly available through the JedAI data repository
(https://github.com/scify/JedAIToolkit/tree/master/data).

Schema settings. In each dataset, we consider both schema-agnostic and schema-
based settings. The former takes into account the content of all attributes,
regardless of their attribute names, while the latter focuses on the values of
the most suitable attribute in terms of coverage and distinctiveness. We
define coverage of attribute $a$ as the portion of entities that contain a
non-empty value for $a$, while distinctiveness expresses the portion of
different values among these entities (e.g., an attribute like year for
publications or movies has very low distinctiveness in contrast to their
titles). Based on these criteria, we selected the attributes at the bottom of
Table 6 for the schema-based settings.

Table 6. Technical characteristics of the real datasets for Clean-Clean ER in increasing computational cost.  | $\mathbf{D_{c1}}$ | $\mathbf{D_{c2}}$ | $\mathbf{D_{c3}}$ | $\mathbf{D_{c4}}$ | $\mathbf{D_{c5}}$ | $\mathbf{D_{c6}}$ | $\mathbf{D_{c7}}$ | $\mathbf{D_{c8}}$ | $\mathbf{D_{c9}}$ | $\mathbf{D_{c10}}$
---|---|---|---|---|---|---|---|---|---|---
$E_{1}$ / $E_{2}$ | Rest. 1 / Rest. 2 | Abt / Buy | Amazon / GB | DBLP / ACM | IMDb / TMDb | IMDb / TVDB | TMDb / TVDB | Walmart / Amazon | DBLP / GS | IMDb / DBpedia
$E_{1}$ / $E_{2}$ entities | 339 / 2,256 | 1,076 / 1,076 | 1,354 / 3,039 | 2,616 / 2,294 | 5,118 / 6,056 | 5,118 / 7,810 | 6,056 / 7,810 | 2,554 / 22,074 | 2,516 / 61,353 | 27,615 / 23,182
Duplicates | 89 | 1,076 | 1,104 | 2,224 | 1,968 | 1,072 | 1,095 | 853 | 2,308 | 22,863
Cartesian Product |  7.65$\cdot 10^{5}$ |  1.16$\cdot 10^{6}$ |  4.11$\cdot 10^{6}$ |  6.00$\cdot 10^{6}$ |  3.10$\cdot 10^{7}$ |  4.00$\cdot 10^{7}$ |  4.73$\cdot 10^{7}$ |  5.64$\cdot 10^{7}$ |  1.54$\cdot 10^{8}$ |  6.40$\cdot 10^{8}$
$E_{1}$ / $E_{2}$ n-v pairs | 1,130 / 7,519 | 2,568 / 2,308 | 5,302 / 9,110 | 10,464 / 9,162 | 21,294 / 23,761 | 21,294 / 20,902 | 23,761 / 20,902 |  14,143 / 1.14$\cdot 10^{5}$ |  10,064 / 1.98$\cdot 10^{5}$ |  1.6$\cdot 10^{5}$ / 8.2$\cdot 10^{5}$
$E_{1}$ / $E_{2}$ attributes | 7 / 7 | 3 / 3 | 4 / 4 | 4 /4 | 13 / 30 | 13 / 9 | 30 / 9 | 6 / 6 | 4 / 4 | 4 / 7
$E_{1}$ / $E_{2}$ av. profile | 3.33 / 3.33 | 2.39 / 2.14 | 3.92 / 3.00 | 4.00 / 3.99 | 4.16 / 3.92 | 4.16 / 2.68 | 3.92 / 2.68 | 5.54 / 5.18 | 4.00 / 3.24 | 5.63 / 35.20
Best Attribute | Name | Name | Title | Title | Title | Name | Name | Title | Title | Title

Figure 3. (a) The coverage of the best attribute per each dataset, (b) the
vocabulary size in schema-agnostic and schema-based settings, and (c) the
overall character length in the textual content of the datasets for both
schema settings.

The actual coverage of these attributes per dataset is reported in Figure 3(a)
along with their groundtruth coverage, i.e., the portion of duplicate profiles
that have at least one non-empty value for the respective attribute. We
observe that for half the datasets ($D_{2}$-$D_{4}$, $D_{8}$, $D_{9}$), the
selected attribute has perfect (groundtruth) coverage. In $D_{5}$-$D_{7}$,
though, the overall coverage fluctuates between 55% and 75%, dropping to
30%-53% for duplicates, even though we have selected the most frequent
attribute in each case. For these datasets, no filtering technique can satisfy
the target recall specified in Section 3. As a result, we exclude the schema-
based settings of $D_{5}$-$D_{7}$ from our analysis. The same applies to
$D_{10}$, even though the inadequate coverage pertains only to one of its
constituent datasets. An interesting exception is $D_{1}$, where the selected
attribute covers just 2/3 of all profiles, but all of duplicate ones.

Note that the low coverage for distinctive attributes like “Name” and “Title”
does not mean that there are entities missing the corresponding values. In
most cases, these values are misplaced, being associated with a different
attribute, due to extraction errors or other forms of noise (Thirumuruganathan
et al., 2021; Mudgal et al., 2018a). The schema-agnostic settings inherently
tackle this form of noise, unlike the schema-based ones.

For the datasets that have both settings, it is worth comparing their
computational cost in terms of vocabulary size (i.e., total number of distinct
tokens) and overall character length (i.e., total number of characters). These
measures appear in Figures 3(b) and (c), respectively. In each case, we also
consider the values of these measures after cleaning, i.e., after removing the
stop-words and stemming all tokens, as required by the workflow in Figure 2.
We used nltk (Bird et al., 2009) for this purpose.

We observe that on average, the schema-based settings reduce the vocabulary
size and the character length by 66.0% and 67.7%, respectively. The reason is
that in most cases, the schema-agnostic settings include 3-4 name-value pairs,
on average, as indicated in Table 6 (av. profile). The more attributes and the
more name value (n-v) pairs a dataset includes, the larger is the difference
between the two settings. Cleaning further reduces the vocabulary size by
11.9% and the character length by 13.5%, on average. As a result, the schema-
based settings are expected to significantly reduce the run-time of filtering
methods, especially when combined with cleaning.

Table 7. The performance of the blocking workflows, the similarity join and the NN methods.  | Schema-agnostic Settings | Schema-based Settings
---|---|---
| $\mathbf{D_{a1}}$ | $\mathbf{D_{a2}}$ | $\mathbf{D_{a3}}$ | $\mathbf{D_{a4}}$ | $\mathbf{D_{a5}}$ | $\mathbf{D_{a6}}$ | $\mathbf{D_{a7}}$ | $\mathbf{D_{a8}}$ | $\mathbf{D_{a9}}$ | $\mathbf{D_{a10}}$ | $\mathbf{D_{b1}}$ | $\mathbf{D_{b2}}$ | $\mathbf{D_{b3}}$ | $\mathbf{D_{b4}}$ | $\mathbf{D_{b8}}$ | $\mathbf{D_{b9}}$
SBW | 1.000 | 0.902 | 0.901 | 0.903 | 0.922 | 0.924 | 0.909 | 0.904 | 0.915 | 0.904 | 0.933 | 0.901 | 0.922 | 0.976 | 0.904 | 0.906
QBW | 0.978 | 0.912 | 0.902 | 0.915 | 0.910 | 0.910 | 0.903 | 0.904 | 0.993 | 0.900 | 0.933 | 0.914 | 0.915 | 0.952 | 0.903 | 0.928
EQBW | 0.910 | 0.901 | 0.905 | 0.918 | 0.905 | 0.904 | 0.905 | 0.900 | 0.913 | 0.900 | 0.944 | 0.902 | 0.905 | 0.913 | 0.903 | 0.910
SABW | 1.000 | 0.901 | 0.900 | 0.969 | 0.900 | 0.903 | 0.901 | 0.912 | 0.902 | 0.900 | 0.910 | 0.903 | 0.909 | 0.997 | 0.900 | 0.900
ESABW | 0.921 | 0.901 | 0.902 | 0.902 | 0.900 | 0.900 | 0.901 | 0.900 | 0.900 | 0.901 | 0.910 | 0.901 | 0.901 | 0.902 | 0.900 | 0.900
PBW | 1.000 | 0.981 | 0.971 | 0.999 | 0.998 | 0.995 | 0.991 | 1.000 | 1.000 | 0.980 | 0.989 | 0.746 | 0.936 | 0.838 | 0.996 | 0.935
DBW | 1.000 | 0.930 | 0.936 | 1.000 | 0.943 | 0.894 | 0.984 | 0.996 | 0.997 | 0.922 | 0.607 | 0.888 | 0.894 | 0.999 | 0.931 | 0.995
$\epsilon$-Join | 0.921 | 0.903 | 0.911 | 0.901 | 0.911 | 0.901 | 0.900 | 0.902 | 0.901 | 0.902 | 0.900 | 0.901 | 0.900 | 0.913 | 0.907 | 0.901
kNN-Join | 1.000 | 0.924 | 0.900 | 0.996 | 0.961 | 0.910 | 0.972 | 0.910 | 0.957 | 0.903 | 0.978 | 0.925 | 0.914 | 0.994 | 0.900 | 0.970
DkNN-Join | 1.000 | 0.915 | 0.804 | 0.998 | 0.882 | 0.921 | 0.984 | 0.939 | 0.995 | 0.887 | 1.000 | 0.916 | 0.934 | 0.998 | 0.831 | 0.989
MH-LSH | 0.910 | 0.987 | 0.903 | 0.903 | 0.903 | 0.985 | 0.936 | 0.948 | 0.923 | - | 0.900 | 0.942 | 0.936 | 0.973 | 0.955 | -
CP-LSH | 0.910 | 0.908 | 0.900 | 0.900 | 0.901 | 0.905 | 0.900 | 0.900 | 0.901 | 0.901 | 0.910 | 0.911 | 0.902 | 0.901 | 0.917 | 0.908
HP-LSH | 0.910 | 0.901 | 0.900 | 0.900 | 0.900 | 0.900 | 0.900 | 0.900 | 0.900 | 0.900 | 0.910 | 0.900 | 0.900 | 0.917 | 0.900 | 0.900
FAISS | 0.933 | 0.902 | 0.900 | 0.961 | 0.901 | 0.900 | 0.908 | 0.900 | 0.900 | 0.900 | 0.955 | 0.906 | 0.900 | 0.971 | 0.900 | 0.912
SCANN | 0.933 | 0.902 | 0.900 | 0.961 | 0.901 | 0.900 | 0.908 | 0.900 | 0.900 | 0.900 | 0.966 | 0.906 | 0.900 | 0.970 | 0.900 | 0.912
DeepBlocker | 0.943 | 0.903 | 0.900 | 0.983 | 0.901 | 0.900 | 0.926 | 0.900 | 0.908 | - | 0.976 | 0.900 | 0.900 | 0.964 | 0.900 | 0.919
DDB | 0.970 | 0.732 | 0.652 | 0.996 | 0.822 | 0.745 | 0.949 | 0.938 | 0.966 | - | 0.992 | 0.800 | 0.839 | 0.990 | 0.900 | 0.972
(a) recall ($\mathbf{PC}$) – values in red correspond to $PC\ll 0.9$
SBW | 0.533 | 0.216 | 0.017 | 0.957 | 0.382 | 0.189 | 0.154 | 0.117 | 0.470 | 0.475 | 0.769 | 0.259 | 0.211 | 0.822 | 0.028 | 0.524
QBW | 0.465 | 0.740 | 0.013 | 0.897 | 0.210 | 0.078 | 0.112 | 0.116 | 0.254 | 0.347 | 0.755 | 0.750 | 0.240 | 0.783 | 0.030 | 0.232
EQBW | 0.757 | 0.204 | 0.012 | 0.926 | 0.220 | 0.078 | 0.124 | 0.087 | 0.149 | 0.390 | 0.764 | 0.261 | 0.188 | 0.854 | 0.021 | 0.182
SABW | 0.767 | 0.384 | 0.015 | 0.804 | 0.217 | 0.065 | 0.146 | 0.096 | 0.322 | 0.020 | 0.757 | 0.390 | 0.226 | 0.695 | 0.010 | 0.014
ESABW | 0.469 | 0.759 | 0.010 | 0.751 | 0.201 | 0.059 | 0.136 | 0.088 | 0.130 | 0.014 | 0.743 | 0.780 | 0.131 | 0.545 | 0.009 | 0.010
PBW | 0.307 | 0.015 | 0.002 | 0.020 | 0.006 | 0.004 | 0.003 |  4.5$\cdot$10-4 | 0.001 |  3.3$\cdot$10-4 | 0.162 | 0.175 | 0.047 | 0.230 |  5.8$\cdot$10-4 | 0.005
DBW |  2.7$\cdot$10-4 | 0.065 | 0.005 | 0.042 | 0.036 | 0.008 | 0.008 | 0.002 | 0.003 | 0.009 | 0.199 | 0.163 | 0.069 | 0.063 | 0.005 | 0.003
$\epsilon$-Join | 0.732 | 0.095 | 0.010 | 0.945 | 0.018 | 0.001 | 0.192 | 0.068 | 0.765 | 0.033 | 0.381 | 0.147 | 0.144 | 0.886 | 0.020 | 0.669
kNN-Join | 0.224 | 0.229 | 0.028 | 0.954 | 0.305 | 0.122 | 0.130 | 0.150 | 0.877 | 0.149 | 0.309 | 0.295 | 0.240 | 0.836 | 0.049 | 0.647
DkNN-Join | 0.047 | 0.181 | 0.130 | 0.190 | 0.053 | 0.024 | 0.026 | 0.062 | 0.182 | 0.147 | 0.100 | 0.173 | 0.149 | 0.187 | 0.054 | 0.166
MH-LSH |  2.6$\cdot$10-4 | 0.001 |  2.7$\cdot$10-4 | 0.005 |  6.6$\cdot$10-5 |  2.7$\cdot$10-5 |  3.4$\cdot$10-5 |  1.6$\cdot$10-5 |  2.1$\cdot$10-5 | - | 0.007 | 0.001 |  2.9$\cdot$10-4 | 0.036 |  1.7$\cdot$10-5 | -
CP-LSH | 0.003 | 0.006 | 0.001 | 0.079 | 0.001 |  2.1$\cdot$10-4 | 0.002 |  4.0$\cdot$10-4 |  2.2$\cdot$10-4 |  7.8$\cdot$10-5 | 0.130 | 0.008 | 0.003 | 0.876 | 0.001 | 0.002
HP-LSH | 0.002 | 0.004 | 0.001 | 0.059 |  4.4$\cdot$10-4 |  2.1$\cdot$10-4 | 0.001 |  2.6$\cdot$10-4 |  1.5$\cdot$10-4 |  7.3$\cdot$10-5 | 0.061 | 0.007 | 0.002 | 0.859 |  4.0$\cdot$10-4 | 0.024
FAISS | 0.082 | 0.032 | 0.001 | 0.932 | 0.012 | 0.005 | 0.041 | 0.001 | 0.012 | 1.5$\cdot$10-4 | 0.376 | 0.050 | 0.024 | 0.942 | 0.004 | 0.836
SCANN | 0.082 | 0.032 | 0.001 | 0.932 | 0.012 | 0.005 | 0.041 | 0.002 | 0.013 | 1.5$\cdot$10-4 | 0.381 | 0.050 | 0.024 | 0.941 | 0.005 | 0.836
DeepBlocker | 0.247 | 0.026 | 0.002 | 0.953 | 0.011 | 0.003 | 0.130 | 0.018 | 0.167 | - | 0.256 | 0.029 | 0.073 | 0.935 | 0.012 | 0.211
DDB | 0.008 | 0.146 | 0.047 | 0.169 | 0.053 | 0.020 | 0.027 | 0.007 | 0.007 | - | 0.008 | 0.160 | 0.061 | 0.168 | 0.007 | 0.007
(b) $\mathbf{PQ}$ – values in red correspond to $PC\ll 0.9$
SBW | 27 ms | 225 ms | 359 ms | 58 ms | 316 ms | 1.1 s | 252 ms | 741 ms | 3.5 s | 57.7 s | 36 ms | 113 ms | 127 ms | 64 ms | 2.7 s | 4.0 s
QBW | 46 ms | 75 ms | 340 ms | 92 ms | 234 ms | 1.2 s | 273 ms | 787 ms | 70.0 s | 158.6 s | 21 ms | 38 ms | 237 ms | 45 ms | 6.0 s | 3.6 s
EQBW | 303 ms | 347 ms | 2.2 s | 2.6 s | 411 ms | 603 ms | 704 ms | 1.2 s | 6.9 s | 68.1 s | 37 ms | 198 ms | 251 ms | 738 ms | 3.9 s | 5.0 s
SABW | 49 ms | 142 ms | 676 ms | 238 ms | 305 ms | 347 ms | 436 ms | 674 ms | 3.0 s | 9.8 s | 19 ms | 58 ms | 114 ms | 337 ms | 645 ms | 4.5 s
ESABW | 161 ms | 281 ms | 891 ms | 745 ms | 388 ms | 481 ms | 750 ms | 1.2 s | 5.6 s | 13.3 s | 23 ms | 187 ms | 418 ms | 201 ms | 1.3 s | 2.2 s
PBW | 29 ms | 32 ms | 135 ms | 44 ms | 76 ms | 81 ms | 125 ms | 243 ms | 579 ms | 5.1 s | 20 ms | 14 ms | 24 ms | 21 ms | 164 ms | 255 ms
DBW | 209 ms | 55 ms | 435 ms | 153 ms | 252 ms | 368 ms | 526 ms | 1.0 s | 2.5 s | 8.2 s | 17 ms | 35 ms | 111 ms | 76 ms | 637 ms | 1.7 s
$\epsilon$-Join | 278 ms | 703 ms | 811 ms | 575 ms | 2.8 s | 8.8 s | 2.8 s | 15.1 s | 30.9 s | 39.4 s | 128 ms | 418 ms | 235 ms | 163 ms | 8.2 s | 24.6 s
kNN-Join | 1.1 s | 874 ms | 4.5 s | 4.4 s | 1.8 s | 1.2 s | 1.8 s | 12.2 s | 26.2 s | 93.9 s | 130 ms | 490 ms | 660 ms | 921 ms | 15.0 s | 47.6 s
DkNN-Join | 969 ms | 750 ms | 4.4 s | 2.0 s | 3.6 s | 3.0 s | 3.6 s | 10.7 s | 24.1 s | 70.2 s | 136 ms | 291 ms | 488 ms | 698 ms | 4.1 s | 9.1 s
MH-LSH | 212 ms | 717 ms | 1.6 s | 1.3 s | 9.0 s | 38.4 s | 10.7 s | 14.2 s | 29.4 s | - | 153 ms | 598 ms | 1.2 s | 3.3 s | 18.8 s | -
CP-LSH | 181 ms | 902 ms | 4.3 s | 2.0 s | 1.7 s | 1.8 s | 3.6 s | 4.8 s | 19.9 s | 63.9 s | 208 ms | 420 ms | 927 ms | 646 ms | 7.5 s | 7.4 s
HP-LSH | 168 ms | 940 ms | 4.2 s | 1.9 s | 1.6 s | 3.5 s | 4.4 s | 7.5 s | 17.5 s | 71.1 s | 246 ms | 430 ms | 930 ms | 943 ms | 5.2 s | 7.0 s
FAISS | 164 ms | 790 ms | 4.2 s | 1.5 s | 1.4 s | 1.8 s | 2.1 s | 7.5 s | 17.7 s | 53.3 s | 204 ms | 264 ms | 787 ms | 901 ms | 5.1 s | 7.4 s
SCANN | 182 ms | 828 ms | 4.6 s | 1.8 s | 2.1 s | 2.5 s | 3.0 s | 9.5 s | 29.5 s | 74.4 s | 741 ms | 319 ms | 841 ms | 1.1 s | 9.4 s | 7.8 s
DeepBlocker | 6.7 s | 7.5 s | 26.1 s | 18.6 s | 40.9 s | 43.4 s | 47.0 s | 89.0 s | 230.9 s | - | 5.8 s | 5.6 s | 12.2 s | 12.5 s | 86.5 s | 194.0 s
DDB | 6.7 s | 7.1 s | 22.7 s | 16.7 s | 40.7 s | 43.8 s | 47.1 s | 87.2 s | 216.1 s | - | 5.0 s | 5.2 s | 11.4 s | 13.5 s | 82.5 s | 191.2 s
(c) the overall run-time ($RT$) in milliseconds ($ms$) or seconds ($s$) –
values in red correspond to $PC\ll 0.9$

Baseline methods. To highlight the impact of fine-tuning, our analysis
includes at least one baseline per type of methods that requires no parameter
configuration. Instead, it employs default parameters that are common across
all datasets.

In more detail, we consider two baseline blocking workflows:

(i) Parameter-free BW (PBW). It combines three methods that involve no
configuration parameter: Standard Blocking, Block Purging and Comparison
Propagation (see Section 4.2 for more details). It constitutes a Standard
Blocking pipeline with no configuration.

(ii) Default BW (DBW). We experimented with the default configurations
specified in (Papadakis et al., 2016) for the five blocking workflows
discussed in Section 4.2 and opted for the one achieving the best performance,
on average, across all settings. This configuration is Q-Grams Blocking with
$q=6$ for block building, Block Filtering with ratio=0.5 for block cleaning
and $WEP+ECBS$ for comparison cleaning.

For similarity joins, we use the Default kNN-Join as a baseline. The reason is
that kNN-Join outperforms the other algorithms of this type in most cases,
while being easy to configure, since it constitutes a deterministic,
cardinality-based approach. Table 9 shows that its best performance is usually
achieved when it is combined with cosine similarity, pre-processing to clean
the attribute values and a very low number of nearest neighbors per query
entity $K$. We used the smallest input dataset as the query set, minimizing
the candidate pairs, set $K$=$5$ and selected $C5GM$ as the default
representation model, because it achieves the best average performance.

Among the NN methods, we selected DeepBlocker as the baseline approach, given
that it typically outperforms all others in terms of effectiveness (cf. Table
7). Table 10 shows that it typically works best when cleaning the attribute
values with stemming and stop-word removal, when using the smallest input
dataset as the query set and when using a small number of candidates per
query. We set $K$=$5$ so that the Default DeepBlocker (DDB) is directly
comparable with Default kNN-Join.

Schema-agnostic Settings. The experimental results are reported in Table
7.111111See for more detailed results and diagrams. For the schema-agnostic
settings, we observe that all fine-tuned methods consistently exceed the
target recall ($PC\geq 0.9$), regardless of their type. Only Default kNN-Join
(DkNN-Join) and (DDB) violate the desired recall level in few cases. For this
reason, the relative effectiveness of the considered methods is primarily
determined by their precision ($PQ$).

The best precision per dataset and schema settings is underlined, while the
overall best across all filtering methods is marked in bold. We notice that
the precision of all methods is highly correlated. In fact, the Pearson
correlation coefficient between any pair of method exceeds 0.5. This means
that the performance of filtering depends heavily on the dataset
characteristics. For example, datasets like $D_{a3}$ yield very low precision
for all methods, because their duplicate entities share only generic/noisy
content that appears in many non-matching profiles, too (e.g., stop words). In
contrast, datasets like $D_{a4}$ entail duplicates that have very
distinguishing content in common, yielding an almost perfect performance in
most cases.

Regarding the blocking workflows, the Standard Blocking workflow (SBW)
outperforms all others in the eight largest datasets. Compared to its
parameter-free counterpart, i.e., PBW, its $PQ$ is substantially higher, with
their difference increasing for larger datasets: it raises from 1 order of
magnitude over $D_{a2}$ to more than 3 orders over $D_{a10}$. This highlights
the benefits of fine-tuning. Among the remaining methods, the Q-Grams Blocking
workflow (QBW) lies very close to the top performing on in most datasets. On
average, its precision is lower than the best one by 27.7%, as in many cases
it ranks second (e.g., in $D_{a8}$). Compared to its default configuration,
DBW, $PQ$ gets higher by a whole order of magnitude, which also verifies the
benefits of parameter fine-tuning. The Extended Q-Grams Blocking workflow
(EQBW) ranks third with its precision being lower than the best one by 33.7%,
on average. The Suffix Arrays Blocking workflow (SABW) lies in very close
distance, being 33.8% lower than the best $PQ$, on average. Both of them rank
second in several cases (e.g., EQBW in $D_{a10}$), but the latter achieves the
overall best precision for $D_{a1}$, while being consistently faster than
EQBW. Finally, the Extended Suffix Arrays Blocking workflow (ESABW) ranks as
the last fine-tuned blocking workflow, since its mean deviation from the
highest precision amounts to 42.1% – even though it achieves the overall best
$PQ$ for $D_{a2}$.

These patterns suggest that attribute value tokens offer the best granularity
for blocking signatures in the schema-agnostic settings. Even though some
candidates might be missed by typographical errors, they typically share
multiple other tokens, due to the schema-agnostic settings. Using substrings
of tokens (i.e., q-grams and suffix arrays) as signatures increases
significantly the number of candidate pairs, without any benefit in recall.
These pairs are significantly reduced by the block and comparison cleaning,
but to a lesser extent than those of SBW, thus leading to lower precision. The
only exception are the two smallest datasets, where the maximum block size
limit of (E)SABW is capable of raising precision to the highest levels among
all considered techniques.

Among the similarity join methods, we observe that kNN-Join outperforms
$\epsilon$-Join in eight datasets. In half of these cases, kNN-Join actually
achieves the best precision among all considered methods. On average,
$\epsilon$-Join underperforms kNN-Join by 57.8%, which suggests that the
cardinality thresholds are significantly more effective in reducing the search
space of ER than the similarity ones. The reason is that the latter apply a
global condition, unlike the former, which operate locally, selecting the best
candidates per query entity. Comparing kNN-Join with its baseline method,
DkNN-Join, the former consistently outperforms the latter, as expected.
However, the difference between the two in terms of precision is 68.3%, on
average, across all datasets where DkNN-Join achieves the target recall. This
verifies the benefits of parameter fine-tuning, but also highlights the
robustness of kNN-Join, given that their difference is much lower than that
between the blocking workflows and the corresponding baseline approaches. In
fact, DkNN-Join outperforms $\epsilon$-Join over $D_{a2}$ and $D_{a6}$ with
respect to both precision and run-time.

Regarding the NN methods, we observe that the similarity-based ones
consistently achieve the lowest by far precision among all fine-tuned
techniques. CP-LSH typically outperforms MH- and HP-LSH, but underperforms all
baseline methods (i.e., PBW, DBW and DkNN-Join) in most of the cases,
especially over the largest datasets. The reason is that the similarity-based
methods achieve high recall for both sparse syntactic and dense embedding
vectors only by producing an excessively large number of candidate pairs –
their precision raises to high levels only for $PC\ll 0.9$. As a result, MH-
LSH runs out of memory when processing $D_{a10}$.

Significantly better performance is achieved by the cardinality-based NN
methods. FAISS and SCANN exhibit practically identical performance across all
datasets, because they perform an exhaustive search of the nearest neighbors.
They differ only in $D_{a3}$, $D_{a8}$ and $D_{a7}$, where SCANN outperforms
FAISS by using approximate scoring (AH). The two algorithms outperform all
others in four datasets, with DeepBlocker being the top performer in the
remaining six cases. DeepBlocker actually lies closer to the highest precision
than FAISS/SCANN in cases where it is ranked second: their average distance
from the maximum $PQ$ is 19.8% and 63.6%, respectively. This means that the
learning-based tuple embedding module raises significantly the precision of NN
methods. However, it does not scale to $D_{a10}$ with the available memory
resources, unlike FAISS/SCANN, due to the extremely large set of candidate
pairs.

The same applies to its default configuration, DDB, which also fails to
achieve the target recall in four datasets. For the remaining five datasets,
its average distance from the maximum $PQ$ is 82.6%. This means that fine-
tuning is necessary for DeepBlocker.

Comparing the top performing methods from each category in terms of precision,
we notice that SBW takes a clear lead, followed in close distance by kNN-Join
and DeepBlocker in the last place. SBW achieves the maximum $PQ$ in four
datasets, kNN-Join in three and DeepBlocker in none of them. Most importantly,
SBW’s $PQ$ is lower than the highest one by 23.1%, on average, kNN-Join’s by
29.8% and DeepBlocker’s by 82.7%. However, kNN-Join constitutes a more robust
approach that is easier to configure and apply in practice. Its default
configuration, DkNN-Join, exhibits a precision that is lower than the best one
by 78.7%, on average, whereas all other baseline methods underperform it by
more than a whole order of magnitude: 94.2% for PBW, 94.7% for DBW and 92.4%
for DDB (we considered only the cases where $PC\geq 0.9$).

Regarding time efficiency, we observe that the blocking workflows excel in
run-time. Most of them require less than a second to process all datasets up
to $D_{a8}$, few seconds for $D_{a9}$ and less than a minute for $D_{a10}$. In
most cases, the fastest workflow is PBW, due to its simple comparison
cleaning, which merely applies Comparison Propagation to eliminate the
redundant candidate pairs. All other workflows are always coupled with a Meta-
blocking approach that assigns a weight to every candidate pair and prunes the
lowest-weighted ones in an effort to reduce the superfluous pairs,
too121212See the configurations of Table 8 in for more details.. Comparison
cleaning actually dominates the run-time of blocking workflows, with $RT$
being proportional to the number of candidate pairs resulting from block
cleaning. For this reason, EQBW and ESABW are typically slower than QBW and
SABW, respectively.

Among the similarity join algorithms, kNN-Join is much faster than
$\epsilon$-Join in half the datasets, $D_{a5}$-$D_{a9}$ in particular. This is
counter-intuitive, given that the former approach involves a more complex
functionality, sorting the candidate pairs per query entity. For these
datasets, though, $k$=1 (2 in $D_{a8}$ – cf. Table 9 in ), thus minimizing its
overhead. This also explains why DkNN-Join, which uses $k=5$, is slower than
both other techniques in $D_{a5}$-$D_{a7}$; for $D_{a8}$-$D_{a10}$, DkNN-Join
is faster than kNN-Join, because the latter uses shorter $q$-grams, thus
generating more candidate pairs. Overall, the run-time of similarity join
algorithms is dominated by the querying time, which consistently accounts for
more than half of $RT$. In contrast, indexing time accounts for less than 10%
in practically all cases, with the rest corresponding to cleaning.

Regarding the NN-methods, they are all implemented in Python and, thus, a
direct comparison with the Java-based blocking workflows and the similarity
join algorithms might lead to wrong conclusions. For this reason, we
exclusively compare the $RT$ of NN methods between them. Among the similarity-
based NN-methods, we observe that MH-LSH is by far the slowest one for
$D_{a5}$ on, even though it is implemented in Java and does not apply cleaning
(i.e., stop-word removal and stemming) in most cases, thus saving its
overhead. This should be attributed to the very large number of candidates it
generates during the querying phase, which prevents it from scaling to
$D_{a10}$. The lowest run-time corresponds to CP-LSH, because it exhibits the
highest $PQ$ among the three methods.

Among the cardinality-based NN methods, we observe that FAISS is consistently
the fastest one. It is significantly faster than SCANN in all cases, even
though they have an almost identical effectiveness, because FAISS saves the
overhead of data partitioning. Most importantly, both versions of DeepBlocker
are slower than the other NN methods by a whole order of magnitude in most
cases. This should be attributed to the cost of automatically creating a
labelleled dataset and using it for training the tuple embedding module – the
number of candidates per query entity plays a minor role, which can be
inferred from the relative run-time of DDB and DeepBlocker and its
configuration in Table 10 in . Therefore, we can conclude that DeepBlocker
emphasizes effectiveness at the cost of very low time efficiency. Note also
that the Hybrid tuple embedding module is a whole order of magnitude slower
than Autoencoder (Thirumuruganathan et al., 2021).

Schema-based settings. Starting with $PC$, we observe that all fine-tuned
methods achieve the target recall, but the baseline methods fail in two
datasets – except for DkNN-Join, which fails only once. Taking into account
the four datasets with insufficient coverage, this means that without fine-
tuning, the schema-based settings fall short of high recall in half the cases.

Regarding precision, we observe that SBW and QBW outperform all blocking
workflows in two datasets each, but the latter has a better performance, on
average: its $PQ$ is lower than the top one by just 11.6%, leaving SBW in the
second place with 14.9%. EQBW ranks third (30.4%) and SABW fourth (40.1%),
even though each method is the top performer in one dataset. ESABW exhibits
the largest average distance from the top (42.3%).

As regards the similarity join algorithms, we observe a balance between
$\epsilon$\- and kNN-Join, as each method achieves the top precision in half
the datasets. Yet, the kNN-Join lies very close to $\epsilon$-Join in the
cases where the latter is the top performer, but not vice versa: the average
deviation from the maximum $PQ$ amounts to 49.7% and 9.3% for the $\epsilon$\-
and the kNN-Join, respectively. DkNN-Join exhibits a robust, high performance
that remains very close to kNN-Join in all datasets, but $D_{b8}$ (where it
fails to reach the target recall), outperforming $\epsilon$-Join over $D_{b2}$
and $D_{b3}$. These settings verify that the cardinality thresholds are
superior to the similarity ones.

Note that the schema-based settings also include the edit-based join. For
brevity, though, we do not report its performance in Table 7. The reason is
that its recall is extremely low, fluctuating between 0.011 ($D_{b1}$) and
0.382 ($D_{b8}$). The only exceptions are $D_{b4}$ and $D_{b9}$, where its
$PC$ raises up to 0.978 and 0.933, respectively. This should be attributed to
the almost identical values shared by the duplicate entities for the selected
attribute names, unlike the rest of the datasets, where duplicate entities
have significant differences, typically at the level of entire tokens. The
corresponding precision is very high, but significantly lower than that of
$\epsilon$\- and kNN-Join, amounting to 0.728 and 0.331. This means that the
edit-based join consistently underperforms the other forms of joins and given
its limited scope, is inappropriate for filtering.

Regarding the NN methods, we observe that similarity-based methods, i.e., the
LSH variants, consistently outperform the rest of the fine-tuned methods,
which leverage cardinality thresholds. MH-LSH actually does not scale to
$D_{b9}$, due to very large set of candidates it produces, which do not fit
into the available memory. We also notice that FAISS and SCANN, which exhibit
practically identical performance, outperform DeepBlocker in four datasets.
Their average distance from the maximum $PQ$ amounts to 21%, while for
DeepBlocker raises to 25.1%. Its default configuration, DDB, exhibits low
precision, merely outperforming MH-LSH.

With respect to the run-time, we observe the same patterns as in the schema-
agnostic settings. $RT$ has significantly improved in most cases, especially
for the largest datasets, due to the lower vocabulary size and character
length. Thus, all methods are capable of processing all datasets in less than
1 second (few seconds for $D_{b9}$). Yet, DeepBlocker and DDB typically remain
a whole order of magnitude slower than all other methods, due to the inelastic
computational cost of creating a labelled dataset and using it to train the
neural-based tuple embedding module.

Among the top performing fine-tuned methods per category, kNN-Join exhibits
the best and most robust performance. It achieves the overall best $PQ$ in two
datasets and the lowest deviation from maximum $PQ$, on average: 26%. This
deviation raises to 38.8% for QBW and to 54% for FAISS/SCANN. Its default
configuration also outperforms all other baseline methods in most cases.

##  7\. Conclusions

Our experimental results lead to the following conclusions:

1) Fine-tuning vs default parameters. For all types of methods, optimizing the
internal parameters with respect to a performance goal (i.e., Problem 1)
raises significantly the performance of filtering. This field has been
overlooked in the literature (Papadakis et al., 2020b), and the few relevant
methods require the involvement of experts (Li et al., 2018; Maskat et al.,
2016). Instead, more emphasis should be placed on a-priori fine-tuning the
configuration parameters of filtering methods through an automatic, data-
driven approach that requires no labelled set.

2) Schema-based vs schema-agnostic settings. The former improve significantly
the time efficiency at the cost of unstable effectiveness, whereas the latter
offer robust effectiveness, as they inherently address the misplaced and
missing values that are common in ER settings (Thirumuruganathan et al., 2021;
Mudgal et al., 2018a). Even when the schema-based settings exhibit high
recall, their maximum $PQ$ outperforms the schema-agnostic settings only in
half the cases ($D_{1}$–$D_{3}$). The schema-agnostic settings also exceed the
target recall even in combination with default configurations, i.e., the
baseline blocking workflows, unlike the schema-based settings, where all
baseline methods fall short of the target recall at least once. For these
reasons, the schema-agnostic settings should be preferred to the schema-based
ones.

3) Similarity vs cardinality thresholds. The edit-based join exceeds the
target recall only in datasets with very high attribute similarity between
duplicates. The LSH variants achieve high recall only by producing an
excessively large number of candidates: compared to the brute-force approach,
MH-, CP- and HP-LSH reduce the candidate pairs by 48%, 91% and 89%,
respectively, on average, across all datasets in Table 7. This might seem high
(a whole order of magnitude for CP-/HP-LSH), but depends quadratically on the
total size of the input, while being inferior to the cardinality-based
filtering methods. This applies even to $\varepsilon$-Join, which reduces the
Cartesian product by 99% (i.e., multiple orders of magnitude), but
underperforms kNN-Join in 9 out of 16 cases. For the cardinality-based
methods, the number of candidates depends linearly on the size of the indexed
dataset, which is usually the smallest one, i.e., $|C|=k\cdot
min{|E_{1}|,|E_{2}|}$; in almost all cases, $k\ll 100$ for all cardinality-
based methods, especially kNN-Join. Therefore, cardinality thresholds should
be preferred to similarity ones.

4) Syntactic vs semantic representations. The blocking workflows and the
similarity join algorithms assume that the pairs of duplicates share textual
content; the rarer this content is, the more likely are two entities to be
matching. In contrast, most NN methods assume that the duplicate entities
share syntactically different, but semantically similar content that can be
captured by pre-trained character-level embeddings. The latter assumption is
true for the matching step of ER (Thirumuruganathan et al., 2021), but our
experiments advocate that filtering violates this assumption: semantic-based
representations outperform the syntactic ones only in two cases ($D_{b4}$ and
$D_{b9}$). Comparing kNN-Join with cardinality-based NN methods, we observe
that the former consistently uses a lower threshold (see Tables 9 and 10 in ).
This means that the semantic representations introduce more false positives
than the syntactic ones, probably due to the out-of-vocabulary domain-specific
terms in ER datasets. Hence, the syntactic representations should be preferred
to the semantic ones.

5) Best overall filtering method. The only method that combines a cardinality
threshold with a syntactic representation is kNN-Join. In the schema-agnostic
settings, its performance is slightly lower than the Standard Blocking
workflow, but offers two qualitative advantages: (i) its number of candidates
depends linearly on the input size, unlike SBW, and (ii) its configuration is
rather easy, as verified by the performance of DkNN-Join. Even though its
recall fluctuates in $[0.8,0.9]$ in three datasets, it outperforms the default
configuration of SBW, PBW, in almost all other cases.

In the future, we will examine methods for automatically configuring the kNN-
Join.

## References

  * (1)
  * Andoni et al. (2015) Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, and Ludwig Schmidt. 2015\.  Practical and Optimal LSH for Angular Distance. In _NIPS_. 1225–1233.
  * Augsten (2018) Nikolaus Augsten. 2018\.  A Roadmap towards Declarative Similarity Queries. In _EDBT_. 509–512.
  * Augsten and Böhlen (2013) Nikolaus Augsten and Michael H. Böhlen. 2013.  _Similarity Joins in Relational Database Systems_.  Morgan & Claypool Publishers.
  * Aumüller et al. (2020) Martin Aumüller, Erik Bernhardsson, and Alexander John Faithfull. 2020.  ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms.  _Inf. Syst._ 87 (2020).
  * Barlaug and Gulla (2021) Nils Barlaug and Jon Atle Gulla. 2021.  Neural Networks for Entity Matching: A Survey.  _ACM Trans. Knowl. Discov. Data_ 15, 3 (2021), 52:1–52:37.
  * Bayardo et al. (2007) Roberto J. Bayardo, Yiming Ma, and Ramakrishnan Srikant. 2007\.  Scaling up all pairs similarity search. In _WWW_. 131–140.
  * Bird et al. (2009) Steven Bird, Ewan Klein, and Edward Loper. 2009.  _Natural language processing with Python: analyzing text with the natural language toolkit_.  O’Reilly Media, Inc.
  * Bojanowski et al. (2017) Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomás Mikolov. 2017.  Enriching Word Vectors with Subword Information.  _Trans. Assoc. Comput. Linguistics_ 5 (2017), 135–146.
  * Bouros et al. (2012) Panagiotis Bouros, Shen Ge, and Nikos Mamoulis. 2012\.  Spatio-textual similarity joins.  _Proc. VLDB Endow._ 6, 1 (2012), 1–12.
  * Broder (1997) Andrei Z. Broder. 1997\.  On the resemblance and containment of documents. In _SEQUENCES_. 21–29.
  * Charikar (2002) Moses S. Charikar. 2002\.  Similarity estimation techniques from rounding algorithms. In _STOC_. 380–388.
  * Chaudhuri et al. (2006) Surajit Chaudhuri, Venkatesh Ganti, and Raghav Kaushik. 2006\.  A Primitive Operator for Similarity Joins in Data Cleaning. In _ICDE_. 5.
  * Christen (2012a) Peter Christen. 2012a.  _Data Matching - Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection_.  Springer.
  * Christen (2012b) Peter Christen. 2012b.  A Survey of Indexing Techniques for Scalable Record Linkage and Deduplication.  _IEEE Trans. Knowl. Data Eng._ 24, 9 (2012), 1537–1555.
  * Christophides et al. (2015) Vassilis Christophides, Vasilis Efthymiou, and Kostas Stefanidis. 2015.  _Entity Resolution in the Web of Data_.  Morgan & Claypool Publishers.
  * Deng et al. (2015) Dong Deng, Guoliang Li, He Wen, and Jianhua Feng. 2015\.  An Efficient Partition Based Method for Exact Set Similarity Joins.  _Proc. VLDB Endow._ 9, 4 (2015), 360–371.
  * Deng et al. (2018) Dong Deng, Yufei Tao, and Guoliang Li. 2018.  Overlap Set Similarity Joins with Theoretical Guarantees. In _Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018_ , Gautam Das, Christopher M. Jermaine, and Philip A. Bernstein (Eds.). ACM, 905–920.  https://doi.org/10.1145/3183713.3183748
  * Dong and Srivastava (2015) Xin Luna Dong and Divesh Srivastava. 2015.  _Big Data Integration_.  Morgan & Claypool Publishers.
  * Ebraheem et al. (2018) Muhammad Ebraheem, Saravanan Thirumuruganathan, Shafiq R. Joty, Mourad Ouzzani, and Nan Tang. 2018\.  Distributed Representations of Tuples for Entity Resolution.  _Proc. VLDB Endow._ 11, 11 (2018), 1454–1467.
  * Elfeky et al. (2002) Mohamed G. Elfeky, Ahmed K. Elmagarmid, and Vassilios S. Verykios. 2002.  TAILOR: A Record Linkage Tool Box. In _ICDE_. 17–28.
  * Elmagarmid et al. (2007) Ahmed K. Elmagarmid, Panagiotis G. Ipeirotis, and Vassilios S. Verykios. 2007.  Duplicate Record Detection: A Survey.  _IEEE Trans. Knowl. Data Eng._ 19, 1 (2007), 1–16.
  * et al. (2018) Benjamin Nelson et al. 2018\.  MultiProbe-LSH.  https://github.com/gopalmenon/Multi-Probe-LSH.
  * Fier et al. (2018) Fabian Fier, Nikolaus Augsten, Panagiotis Bouros, Ulf Leser, and Johann-Christoph Freytag. 2018\.  Set Similarity Joins on MapReduce: An Experimental Survey.  _Proc. VLDB Endow._ 11, 10 (2018), 1110–1122.
  * Fisichella et al. (2014) Marco Fisichella, Andrea Ceroni, Fan Deng, and Wolfgang Nejdl. 2014\.  Predicting Pair Similarities for Near-Duplicate Detection in High Dimensional Spaces. In _DEXA_. 59–73.
  * Fu et al. (2020) Cheng Fu, Xianpei Han, Jiaming He, and Le Sun. 2020\.  Hierarchical Matching Network for Heterogeneous Entity Resolution. In _IJCAI_. 3665–3671.
  * Getoor and Machanavajjhala (2012) Lise Getoor and Ashwin Machanavajjhala. 2012.  Entity Resolution: Theory, Practice & Open Challenges.  _Proc. VLDB Endow._ 5, 12 (2012), 2018–2019.
  * Gravano et al. (2001) Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, and Divesh Srivastava. 2001.  Approximate String Joins in a Database (Almost) for Free. In _VLDB_. 491–500.
  * Guo et al. (2020) Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020.  Accelerating Large-Scale Inference with Anisotropic Vector Quantization. In _ICML_. 3887–3896.
  * Hassanzadeh et al. (2009) Oktie Hassanzadeh, Fei Chiang, Renée J. Miller, and Hyun Chul Lee. 2009.  Framework for Evaluating Clustering Algorithms in Duplicate Detection.  _Proc. VLDB Endow._ 2, 1 (2009), 1282–1293.
  * Indyk and Motwani (1998) Piotr Indyk and Rajeev Motwani. 1998.  Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In _STOC_. 604–613.
  * Jiang et al. (2014) Yu Jiang, Guoliang Li, Jianhua Feng, and Wen-Syan Li. 2014\.  String Similarity Joins: An Experimental Evaluation.  _Proc. VLDB Endow._ 7, 8 (2014), 625–636.
  * Johnson et al. (2021) Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2021\.  Billion-Scale Similarity Search with GPUs.  _IEEE Trans. Big Data_ 7, 3 (2021), 535–547.
  * Karapiperis et al. (2016) Dimitrios Karapiperis, Dinusha Vatsalan, Vassilios S. Verykios, and Peter Christen. 2016.  Efficient Record Linkage Using a Compact Hamming Space. In _EDBT_. 209–220.
  * Kim and Lee (2010) Hung-sik Kim and Dongwon Lee. 2010.  HARRA: fast iterative hashed record linkage for large-scale data collections. In _EDBT_. 525–536.
  * Kocher and Augsten (2019) Daniel Kocher and Nikolaus Augsten. 2019.  A Scalable Index for Top-k Subtree Similarity Queries. In _SIGMOD_. 1624–1641.
  * Konda et al. (2016) Pradap Konda, Sanjib Das, Paul Suganthan G. C., AnHai Doan, Adel Ardalan, Jeffrey R. Ballard, Han Li, Fatemah Panahi, Haojun Zhang, Jeffrey F. Naughton, Shishir Prasad, Ganesh Krishnan, Rohit Deep, and Vijay Raghavendra. 2016\.  Magellan: Toward Building Entity Matching Management Systems.  _Proc. VLDB Endow._ 9, 12 (2016), 1197–1208.
  * Köpcke et al. (2010) Hanna Köpcke, Andreas Thor, and Erhard Rahm. 2010\.  Evaluation of entity resolution approaches on real-world match problems.  _Proc. VLDB Endow._ 3, 1 (2010), 484–493.
  * Leskovec et al. (2020) Jure Leskovec, Anand Rajaraman, and Jeffrey David Ullman. 2020\.  _Mining of massive data sets_.  Cambridge university press.
  * Li et al. (2008) Chen Li, Jiaheng Lu, and Yiming Lu. 2008.  Efficient Merging and Filtering Algorithms for Approximate String Searches. In _ICDE_. 257–266.
  * Li et al. (2011) Guoliang Li, Dong Deng, Jiannan Wang, and Jianhua Feng. 2011\.  PASS-JOIN: A Partition-based Method for Similarity Joins.  _Proc. VLDB Endow._ 5, 3 (2011), 253–264.
  * Li et al. (2018) Han Li, Pradap Konda, Paul Suganthan G. C., AnHai Doan, Benjamin Snyder, Youngchoon Park, Ganesh Krishnan, Rohit Deep, and Vijay Raghavendra. 2018.  MatchCatcher: A Debugger for Blocking in Entity Matching. In _EDBT_. 193–204.
  * Mann et al. (2016) Willi Mann, Nikolaus Augsten, and Panagiotis Bouros. 2016\.  An Empirical Evaluation of Set Similarity Join Techniques.  _Proc. VLDB Endow._ 9, 9 (2016), 636–647.
  * Manning et al. (2008) Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. 2008.  _Introduction to information retrieval_.  Cambridge University Press.
  * Maskat et al. (2016) Ruhaila Maskat, Norman W. Paton, and Suzanne M. Embury. 2016\.  Pay-as-you-go Configuration of Entity Resolution.  _Trans. Large Scale Data Knowl. Centered Syst._ 29 (2016), 40–65.
  * Mudgal et al. (2018a) Sidharth Mudgal, Han Li, Theodoros Rekatsinas, AnHai Doan, Youngchoon Park, Ganesh Krishnan, Rohit Deep, Esteban Arcaute, and Vijay Raghavendra. 2018a.  Deep Learning for Entity Matching: A Design Space Exploration. In _SIGMOD_. ACM, 19–34.
  * Mudgal et al. (2018b) Sidharth Mudgal, Han Li, Theodoros Rekatsinas, AnHai Doan, Youngchoon Park, Ganesh Krishnan, Rohit Deep, Esteban Arcaute, and Vijay Raghavendra. 2018b.  Deep Learning for Entity Matching: A Design Space Exploration. In _SIGMOD_. 19–34.
  * Navarro (2001) Gonzalo Navarro. 2001\.  A guided tour to approximate string matching.  _ACM Comput. Surv._ 33, 1 (2001), 31–88.
  * Obraczka et al. (2021) Daniel Obraczka, Jonathan Schuchart, and Erhard Rahm. 2021\.  Embedding-Assisted Entity Resolution for Knowledge Graphs. In _ESWC_ , Vol. 2873.
  * Papadakis et al. (2015) George Papadakis, George Alexiou, George Papastefanatos, and Georgia Koutrika. 2015.  Schema-agnostic vs Schema-based Configurations for Blocking Methods on Homogeneous Data.  _Proc. VLDB Endow._ 9, 4 (2015), 312–323.
  * Papadakis et al. (2013) George Papadakis, Ekaterini Ioannou, Themis Palpanas, Claudia Niederée, and Wolfgang Nejdl. 2013.  A Blocking Framework for Entity Resolution in Highly Heterogeneous Information Spaces.  _IEEE Trans. Knowl. Data Eng._ 25, 12 (2013), 2665–2682.
  * Papadakis et al. (2021) George Papadakis, Ekaterini Ioannou, Emanouil Thanos, and Themis Palpanas. 2021.  _The Four Generations of Entity Resolution_.  Morgan & Claypool Publishers.
  * Papadakis et al. (2014) George Papadakis, Georgia Koutrika, Themis Palpanas, and Wolfgang Nejdl. 2014.  Meta-Blocking: Taking Entity Resolution to the Next Level.  _IEEE Trans. Knowl. Data Eng._ 26, 8 (2014), 1946–1960.
  * Papadakis et al. (2020a) George Papadakis, Georgios M. Mandilaras, Luca Gagliardelli, Giovanni Simonini, Emmanouil Thanos, George Giannakopoulos, Sonia Bergamaschi, Themis Palpanas, and Manolis Koubarakis. 2020a.  Three-dimensional Entity Resolution with JedAI.  _Inf. Syst._ 93 (2020), 101565.
  * Papadakis et al. (2020b) George Papadakis, Dimitrios Skoutas, Emmanouil Thanos, and Themis Palpanas. 2020b.  Blocking and Filtering Techniques for Entity Resolution: A Survey.  _ACM Comput. Surv._ 53, 2 (2020), 31:1–31:42.
  * Papadakis et al. (2016) George Papadakis, Jonathan Svirsky, Avigdor Gal, and Themis Palpanas. 2016.  Comparative Analysis of Approximate Blocking Techniques for Entity Resolution.  _Proc. VLDB Endow._ 9, 9 (2016), 684–695.
  * Papadakis et al. (2019) George Papadakis, Leonidas Tsekouras, Emmanouil Thanos, George Giannakopoulos, Themis Palpanas, and Manolis Koubarakis. 2019.  Domain- and Structure-Agnostic End-to-End Entity Resolution with JedAI.  _SIGMOD Rec._ 48, 4 (2019), 30–36.
  * Silva et al. (2013) Yasin N. Silva, Walid G. Aref, Per-Åke Larson, Spencer Pearson, and Mohamed H. Ali. 2013\.  Similarity queries: their conceptual evaluation, transformations, and processing.  _VLDB J._ 22, 3 (2013), 395–420.
  * Simonini et al. (2016) Giovanni Simonini, Sonia Bergamaschi, and H. V. Jagadish. 2016\.  BLAST: a Loosely Schema-aware Meta-blocking Approach for Entity Resolution.  _Proc. VLDB Endow._ 9, 12 (2016), 1173–1184.
  * Thirumuruganathan et al. (2021) Saravanan Thirumuruganathan, Han Li, Nan Tang, Mourad Ouzzani, Yash Govind, Derek Paulsen, Glenn Fung, and AnHai Doan. 2021\.  Deep Learning for Blocking in Entity Matching: A Design Space Exploration.  _Proc. VLDB Endow._ 14, 11 (2021), 2459–2472.
  * Wang et al. (2020) Shirui Wang, Wen’an Zhou, and Chao Jiang. 2020.  A survey of word embeddings based on deep learning.  _Computing_ 102, 3 (2020), 717–740.
  * Xiao et al. (2009) Chuan Xiao, Wei Wang, Xuemin Lin, and Haichuan Shang. 2009\.  Top-k Set Similarity Joins. In _ICDE_. 916–927.
  * Xiao et al. (2011) Chuan Xiao, Wei Wang, Xuemin Lin, Jeffrey Xu Yu, and Guoren Wang. 2011.  Efficient similarity joins for near-duplicate detection.  _ACM Trans. Database Syst._ 36, 3 (2011), 15:1–15:41.
  * Yang et al. (2020) Zhong Yang, Bolong Zheng, GuoHui Li, Xi Zhao, Xiaofang Zhou, and Christian S. Jensen. 2020.  Adaptive Top-k Overlap Set Similarity Joins. In _ICDE_. 1081–1092.
  * Yao et al. (2021) Zijun Yao, Chengjiang Li, Tiansi Dong, Xin Lv, Jifan Yu, Lei Hou, Juanzi Li, Yichi Zhang, and Zelin Dai. 2021.  Interpretable and Low-Resource Entity Matching via Decoupling Feature Learning from Decision Making. In _ACL/IJCNLP_. 2770–2781.
  * Yu et al. (2016) Minghe Yu, Guoliang Li, Dong Deng, and Jianhua Feng. 2016\.  String similarity search and join: a survey.  _Frontiers Comput. Sci._ 10, 3 (2016), 399–417.
  * Zhang et al. (2020a) Dongxiang Zhang, Yuyang Nie, Sai Wu, Yanyan Shen, and Kian-Lee Tan. 2020a.  Multi-Context Attention for Entity Matching. In _WWW_. 2634–2640.
  * Zhang et al. (2020b) Wei Zhang, Hao Wei, Bunyamin Sisman, Xin Luna Dong, Christos Faloutsos, and David Page. 2020b.  AutoBlock: A Hands-off Blocking Framework for Entity Matching. In _WSDM_. 744–752.
  * Zhu et al. (2019) Erkang Zhu, Dong Deng, Fatemeh Nargesian, and Renée J. Miller. 2019.  JOSIE: Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes. In _SIGMOD_. 847–864.

## Appendix

### A. Detailed Configuration.

In this section, we present the detailed configuration of every filtering
method that corresponds to its performance in Table 7.

Table 8. The best configuration of each blocking workflow across all datasets, both in schema-agnostic and schema-based settings. $BP$ stands for the use of Block Purging or not (it is a parameter-free approach), $BFr$ indicates the filtering ratio used by Block Filtering, $PA$ denotes the pruning algorithm that is used by the Meta-blocking step and $WS$ stands for the corresponding weighting scheme. Table 3 reports the domain of each parameter. | Schema-agnostic | Schema-based
---|---|---
| $\mathbf{D_{a1}}$ | $\mathbf{D_{a2}}$ | $\mathbf{D_{a3}}$ | $\mathbf{D_{a4}}$ | $\mathbf{D_{a5}}$ | $\mathbf{D_{a6}}$ | $\mathbf{D_{a7}}$ | $\mathbf{D_{a8}}$ | $\mathbf{D_{a9}}$ | $\mathbf{D_{a10}}$ | $\mathbf{D_{b1}}$ | $\mathbf{D_{b2}}$ | $\mathbf{D_{b3}}$ | $\mathbf{D_{b4}}$ | $\mathbf{D_{b8}}$ | $\mathbf{D_{b9}}$
| $BP$ | - | - | ✓ | ✓ | ✓ | - | - | - | ✓ | - | - | - | - | - | - | -
Standard | $BFr$ | 0.050 | 0.875 | 0.925 | 0.225 | 1.000 | 0.975 | 0.350 | 0.225 | 0.625 | 0.800 | 0.900 | 0.875 | 0.800 | 0.250 | 0.650 | 0.525
Blocking | $PA$ | WEP | BLAST | RCNP | RCNP | RCNP | RCNP | RCNP | RCNP | RCNP | BLAST | RCNP | BLAST | BLAST | RWNP | BLAST | RCNP
| $WS$ | ARCS | $\chi^{2}$ | $\chi^{2}$ | EJS | CBS | CBS | CBS | ARCS | JS | $\chi^{2}$ | CBS | $\chi^{2}$ | $\chi^{2}$ | ECBS | $\chi^{2}$ | CBS
Q-Grams Blocking | $q$ | 4 | 4 | 6 | 6 | 6 | 6 | 6 | 5 | 3 | 4 | 6 | 4 | 3 | 6 | 3 | 6
$BP$ | ✓ | - | ✓ | ✓ | - | - | - | ✓ | - | ✓ | - | - | - | - | ✓ | -
$BFr$ | 0.325 | 0.325 | 0.875 | 0.100 | 0.425 | 0.875 | 0.225 | 0.275 | 0.525 | 0.950 | 0.950 | 0.475 | 0.450 | 0.100 | 0.675 | 0.325
$PA$ | RCNP | BLAST | CEP | WEP | RCNP | RCNP | RCNP | RCNP | BLAST | BLAST | RCNP | BLAST | BLAST | WEP | RCNP | RCNP
$WS$ | CBS | ARCS | $\chi^{2}$ | EJS | ARCS | ECBS | ECBS | ARCS | $\chi^{2}$ | $\chi^{2}$ | CBS | ARCS | $\chi^{2}$ | EJS | $\chi^{2}$ | ECBS
Extended Q-Grams Blocking | $q$ | 4 | 4 | 3 | 2 | 6 | 6 | 6 | 6 | 6 | 3 | 3 | 3 | 4 | 3 | 3 | 6
$t$ | 0.80 | 0.90 | 0.90 | 0.85 | 0.90 | 0.90 | 0.80 | 0.80 | 0.90 | 0.90 | 0.90 | 0.80 | 0.90 | 0.85 | 0.90 | 0.90
$BP$ | - | - | - | ✓ | ✓ | - | - | - | ✓ | - | - | - | - | - | - | -
$BFr$ | 0.025 | 0.900 | 0.500 | 0.025 | 0.775 | 0.675 | 0.175 | 0.175 | 0.475 | 0.750 | 0.975 | 0.325 | 0.750 | 0.025 | 0.750 | 0.400
$PA$ | WEP | BLAST | WNP | WEP | RCNP | RCNP | RCNP | RCNP | RCNP | BLAST | RCNP | WNP | BLAST | WEP | BLAST | RCNP
$WS$ | ECBS | $\chi^{2}$ | ARCS | EJS | ARCS | ARCS | EJS | ARCS | ECBS | $\chi^{2}$ | CBS | ARCS | $\chi^{2}$ | EJS | $\chi^{2}$ | ECBS
Suffix Arrays Blocking | $l_{min}$ | 4 | 2 | 3 | 2 | 6 | 6 | 6 | 5 | 6 | 6 | 6 | 2 | 2 | 2 | 3 | 6
$b_{max}$ | 2 | 46 | 65 | 16 | 35 | 79 | 20 | 52 | 100 | 96 | 10 | 35 | 46 | 97 | 92 | 100
$PA$ | WEP | BLAST | RCNP | BLAST | RWNP | RWNP | BLAST | RCNP | RCNP | WNP | RCNP | BLAST | BLAST | BLAST | WEP | WNP
$WS$ | ECBS | $\chi^{2}$ | $\chi^{2}$ | $\chi^{2}$ | ARCS | ARCS | ARCS | ARCS | $\chi^{2}$ | $\chi^{2}$ | CBS | $\chi^{2}$ | $\chi^{2}$ | $\chi^{2}$ | $\chi^{2}$ | CBS
Extended | $l_{min}$ | 2 | 3 | 6 | 2 | 6 | 6 | 6 | 6 | 6 | 5 | 6 | 2 | 2 | 6 | 6 | 6
Suffix | $b_{max}$ | 3 | 10 | 84 | 8 | 39 | 86 | 23 | 24 | 84 | 100 | 100 | 18 | 98 | 20 | 91 | 100
Arrays | $PA$ | RWNP | BLAST | WNP | BLAST | RWNP | RWNP | BLAST | RWNP | RCNP | CNP | RCNP | BLAST | BLAST | BLAST | WNP | CEP
Blocking | $WS$ | ARCS | ARCS | ARCS | $\chi^{2}$ | ARCS | ARCS | ARCS | ARCS | $\chi^{2}$ | $\chi^{2}$ | CBS | ARCS | JS | ARCS | ARCS | ECBS
Table 9. The best configuration per token-based similarity join across all datasets. $CL$ stands for the use of pre-processing for cleaning an attribute value, $SM$ for the similarity measure, $RM$ for the representation model that is used, $t$ for the similarity threshold and $K$ for the number of nearest neighbors, while $RVS$ indicates whether $\mathcal{E}_{2}$ is indexed and $\mathcal{E}_{1}$ is used as the query set, instead of the opposite. Table 4 reports the domain of each parameter. | Schema-agnostic | Schema-based
---|---|---
| $\mathbf{D_{a1}}$ | $\mathbf{D_{a2}}$ | $\mathbf{D_{a3}}$ | $\mathbf{D_{a4}}$ | $\mathbf{D_{a5}}$ | $\mathbf{D_{a6}}$ | $\mathbf{D_{a7}}$ | $\mathbf{D_{a8}}$ | $\mathbf{D_{a9}}$ | $\mathbf{D_{a10}}$ | $\mathbf{D_{b1}}$ | $\mathbf{D_{b2}}$ | $\mathbf{D_{b3}}$ | $\mathbf{D_{b4}}$ | $\mathbf{D_{b8}}$ | $\mathbf{D_{b9}}$
$\epsilon$-Join | $CL$ | ✓ | ✓ | ✓ | - | ✓ | - | ✓ | ✓ | ✓ | - | ✓ | ✓ | - | - | ✓ | -
$RM$ | T1G | C3G | C5G | T1G | C5GM | C2G | T1GM | C3GM | C3GM | T1G | C4G | C3GM | C3G | T1G | C3G | C3GM
$SM$ | Cosine | Cosine | Cosine | Jaccard | Cosine | Cosine | Cosine | Jaccard | Jaccard | Cosine | Cosine | Cosine | Cosine | Cosine | Cosine | Cosine
$t$ | 0.82 | 0.26 | 0.08 | 0.58 | 0.16 | 0.34 | 0.49 | 0.28 | 0.35 | 0.15 | 0.63 | 0.38 | 0.39 | 1.00 | 0.41 | 0.81
kNN-Join | $CL$ | ✓ | ✓ | ✓ | - | - | - | - | ✓ | - | - | ✓ | ✓ | ✓ | - | ✓ | -
$RVS$ | ✓ | - | ✓ | - | - | - | - | ✓ | ✓ | ✓ | ✓ | - | ✓ | - | ✓ | ✓
$RM$ | C4GM | C3GM | G5GM | C2GM | C5G | C5G | C5G | C4GM | C4G | C4G | C5G | C2G | C3G | C3G | C2G | C2GM
$SM$ | Dice | Cosine | Cosine | Cosine | Cosine | Cosine | Cosine | Cosine | Cosine | Cosine | Cosine | Cosine | Cosine | Cosine | Cosine | Cosine
$K$ | 1 | 4 | 26 | 1 | 1 | 1 | 1 | 2 | 1 | 5 | 1 | 3 | 3 | 1 | 6 | 1
Table 10. The best configuration of each vector-based NN method across all datasets. CL denotes the use of pre-processing for cleaning an attribute value, $t$ the corresponding Jaccard similarity threshold, $k$ the size of the k-shingles that are used as representation model and RVS whether the indexed and the query dataset should be reversed or not. Table 5 reports the domain of each parameter. | Schema-agnostic | Schema-based
---|---|---
| $\mathbf{D_{a1}}$ | $\mathbf{D_{a2}}$ | $\mathbf{D_{a3}}$ | $\mathbf{D_{a4}}$ | $\mathbf{D_{a5}}$ | $\mathbf{D_{a6}}$ | $\mathbf{D_{a7}}$ | $\mathbf{D_{a8}}$ | $\mathbf{D_{a9}}$ | $\mathbf{D_{a10}}$ | $\mathbf{D_{b1}}$ | $\mathbf{D_{b2}}$ | $\mathbf{D_{b3}}$ | $\mathbf{D_{b4}}$ | $\mathbf{D_{b8}}$ | $\mathbf{D_{b9}}$
| $CL$ | - | - | - | ✓ | - | ✓ | - | - | - | - | ✓ | ✓ | - | ✓ | ✓ | -
MinHash | $\\#bands$ | 4 | 32 | 16 | 4 | 32 | 32 | 16 | 32 | 16 | - | 4 | 32 | 32 | 2 | 32 | -
LSH | $\\#buckets$ | 64 | 8 | 8 | 128 | 16 | 8 | 16 | 16 | 16 | - | 128 | 16 | 16 | 256 | 16 | -
| $k$ | 2 | 2 | 2 | 2 | 2 | 5 | 2 | 2 | 2 | - | 2 | 2 | 2 | 5 | 2 | -
| $CL$ | - | ✓ | ✓ | ✓ | - | - | ✓ | - | ✓ | - | ✓ | ✓ | ✓ | - | ✓ | -
| $\\#tables$ | 16 | 60 | 20 | 5 | 10 | 50 | 8 | 50 | 50 | 100 | 24 | 43 | 65 | 1 | 500 | 5
Cross-Polytope | $\\#hashes$ | 2 | 1 | 1 | 2 | 1 | 1 | 2 | 2 | 1 | 1 | 2 | 1 | 1 | 3 | 2 | 1
LSH | cp dimension | 32 | 256 | 256 | 256 | 512 | 256 | 128 | 128 | 512 | 128 | 128 | 256 | 512 | 16 | 128 | 512
| $\\#probes$ | 180 | 60 | 159 | 400 | 87 | 50 | 339 | 1548 | 51 | 114 | 24 | 43 | 65 | 1 | 500 | 6
| $CL$ | - | ✓ | ✓ | ✓ | - | ✓ | ✓ | ✓ | ✓ | - | - | - | ✓ | ✓ | ✓ | -
Hyperplane | $\\#tables$ | 13 | 50 | 19 | 28 | 17 | 200 | 200 | 150 | 100 | 200 | 13 | 100 | 19 | 2 | 150 | 100
LSH | $\\#hashes$ | 15 | 11 | 9 | 18 | 12 | 14 | 16 | 15 | 13 | 12 | 14 | 11 | 12 | 20 | 14 | 19
| $\\#probes$ | 297 | 385 | 275 | 602 | 461 | 1450 | 226 | 878 | 643 | 1961 | 33 | 181 | 577 | 2 | 360 | 111
| $CL$ | - | ✓ | ✓ | ✓ | - | - | - | ✓ | ✓ | ✓ | ✓ | - | ✓ | ✓ | ✓ | -
FAISS | $RVS$ | ✓ | - | - | - | ✓ | ✓ | ✓ | - | ✓ | - | ✓ | - | ✓ | - | ✓ | ✓
| $K$ | 3 | 28 | 545 | 1 | 30 | 40 | 4 | 24 | 71 | 4,860 | 1 | 18 | 31 | 1 | 78 | 1
| $CL$ | - | ✓ | ✓ | ✓ | - | - | - | ✓ | ✓ | ✓ | ✓ | - | ✓ | ✓ | ✓ | -
| $RVS$ | ✓ | - | - | - | ✓ | ✓ | ✓ | - | ✓ | ✓ | ✓ | - | ✓ | - | ✓ | ✓
SCANN | $K$ | 3 | 28 | 475 | 1 | 30 | 40 | 4 | 19 | 63 | 4,860 | 1 | 18 | 31 | 1 | 60 | 1
| index | BF | BF | AH | BF | BF | BF | BF | AH | AH | BF | AH | BF | BF | BF | AH | BF
| similarity | DP |  L22 |  L22 |  L22 |  L22 |  L22 | DP |  L22 |  L22 | DP |  L22 |  L22 |  L22 | DP |  L22 | DP
| $CL$ | - | ✓ | ✓ | ✓ | ✓ | - | ✓ | ✓ | ✓ | - | ✓ | - | - | ✓ | - | ✓
DeepBlocker | $RVS$ | - | ✓ | ✓ | ✓ | - | - | ✓ | - | - | - | - | ✓ | - | ✓ | - | -
| $K$ | 1 | 35 | 180 | 1 | 31 | 63 | 1 | 17 | 5 | - | 1 | 31 | 10 | 1 | 25 | 4

## B. Run-time Analysis

The overall run-time of blocking workflows is broken into the run-times of the
four steps:

  1. (1)

block building time ($t_{b}$),

  2. (2)

block purging time ($t_{p}$),

  3. (3)

block filtering time ($t_{f}$), and

  4. (4)

comparison cleaning time ($t_{c}$).

The overall run-time for the rest of the filtering methods is divided into:

  1. (1)

pre-processing time ($t_{r}$),

  2. (2)

indexing time ($t_{i}$), and

  3. (3)

querying time ($t_{q}$).

Figure 4. Portion of run-time per step in blocking workflows in (a) schema-
agnostic and (b) schema-based settings.