We introduce an approach that selects relevant attributes to the indexing step of data deduplication, reducing the whole processing time and improving the deduplication effectiveness. We evaluate the proposed method on synthetic and real datasets over distinct domains. We also evaluate the impact of choosing the indexing attributes over the other steps of the deduplication process, then concluding our solution is both efficient (time cost) and effective (results quality) as a whole.
Data deduplication identifies and eliminates duplicate records from datasets and
databases. Duplicate records are data instances that represent the same object
in the real world. Data deduplication has several applications. For example, it
helps identifying duplicate products in online stores [
The process of identifying and eliminating duplicate records is composed
by three steps: indexing (defines a key per record), record comparison (groups
records according to key values), and classification (compares records within the
groups). Our focus is on the indexing step, which creates block keys (BKs)
structures to group similar values [
Existing approaches use BKs for different purposes, such as sorting and
clustering. Examples include standard blocking [
Our Contributions. We propose a new method for indexing-oriented attribute selection and assess its performance through an extensive experimental evaluation. We measure the efficiency and effectiveness of the proposed strategy in real and synthetic datasets. The datasets cover a wide spectrum of data domains including bibliographic records, music CDs, personal information and restaurant data. Results show that using the best-ranked attribute by the proposed method yields the best F-Measure results on 10 out of 13 datasets. The deduplication outcome improves by about 88% in terms of F-Measure when using the best attribute instead of the worst one. Finally, the implementations of the methods and the datasets are publicly available1. 1 Sources: http://www.dcc.ufmg.br/~mirella/projs/deduplica
Let D be a dataset containing i records, such that D = fr1; r2; ::; rig. Each
record r is defined by a set of attributes Ar = fa1; a2; ::; aj g. Then, the data
deduplication process is composed of three steps: indexing, record comparison
and classification, each generating input to the following one. Next, we describe
such steps and the most commonly used algorithms to process each one [
The Standard Blocking Algorithm creates a set of blocks where each block groups similar records. Hence, records within a block are compared only against each other (i.e, reducing the original quadratic complexity). These groupings are defined according to the BK values generated for each record. For instance, in Table 1, when indexing records 1, 2, 3, 4 and 5 through the Artist column and using the Soundex encoding, three groups are created: K520 with records 1 and 2; E626 with 3; and A534 with records 4 and 5.
The Sorted Neighborhood Algorithm [
Classification Step. For evaluating how similar two values are, a similarity
function usually calculates the correspondence between them and returns a
number in [0; 1], where 1 means “perfect match”. The Jaro Winkler algorithm (a
popular extension of Jaro algorithm proposed by Winkler [
We now introduce our method for selecting the best indexing attribute. It creates a ranking for each attribute a 2 Ar based on a combination of metrics described ahead. It does not use machine learning algorithms, being adaptable to any data domain without needing a training dataset. It also works without requiring intervention of experts, huge advantage over existing approaches. Metrics Definition. Our proposed method is based on four metrics, computed for each attribute a 2 Ar: (1 ) Duplicity is the ratio between number of duplicate values and number of not-null instances; (2 ) Distinctiveness is the ratio between number of distinct values and number of not-null instances; (3 ) Density is the fraction of non-null instances; and (4 ) Repetition is the ratio between number of repeated records and number of distinct values, defined as follows.
Dup(a) = dupValues(a) (1) Dist(a) = distValues(a) (2) notNull(a) notNull(a) Dens(a) = (3) Rep(a) = T disdtiVstaVluaelus(eas)(a) (4) notNull(a)
T where notNull(a) is the number of valid, non-null instances for an attribute a, dupValues(a) is the number of duplicate values for a, distValues(a) is the total of distinct values for a, and T is the total of instances. We normalize each metric by its maximum over Ar and denote them by Dup(a), Dist(a), Dens(a) and Rep(a).
One advantage is that our metrics can be easily computed over any relational
dataset, being commonly present in the histogram features of relational systems.
Hence, the proposed method can be adaptable for several data domains. Also,
density and repetition are used by others to select relevant attributes for the
classification step [
R(a) = Dens(a) + Dup(a) + ((1
Dist(a))
Dens(a)) + (1
Rep(a)): (5) Intuitively, density and duplicity improve efficacy. High repetition and distinct values lead to large run times because they create few blocks with many records (i.e., many comparisons) or many blocks with few records (i.e., several accesses to the database to retrieve the records of each distinct BK). Hence, we consider their complement to improve efficiency, as attributes without much repetition and distinctiveness perform faster. Also, we multiply (1 Dist(a)) by Dens(a) to avoid that low distinctiveness and density have high scores. Last, we normalize R(a) by its maximum value to obtain the attribute relevance score R(a). Example. For the example in Table 1, we compute the metrics for each attribute a 2 {Source, Title, Artist, Category, Genre, Extra, Year } and calculate its relevance using Equation 5. Next, we sort each attribute a 2 Ar by its relevance R(a). Table 2 summarizes the resulting metric values and relevance of each attribute, making Artist the best attribute for the indexing step. Hence, we expect that using Artist in the indexing step will yield the best results (w.r.t. efficiency and efficacy) in data deduplication; whereas Extra will yield the worst ones (confirmed later on Figure 3(a) in Section 5). 4
Experimental Methodology. We implemented the data deduplication
algorithms from Section 2 in Java and performed the experiments on a Intel i7
(2:3 GHz) desktop computer with 16GB of RAM, running MAC OS X 10.11.3.
The experimental methodology consists in performing the complete data
deduplication process with different indexing setups for each attribute available in
the dataset. For the other steps, we use standard blocking or the sorted
neighborhood algorithm for record comparison, and the Jaro Winkler algorithm for
classification. In the classification step, we compute the similarity among the
most descriptive attributes of each dataset. Then, we compute efficiency and
effectiveness for each attribute. Specifically, at efficiency, we compute the time
to retrieve the distinct BK values and perform the data deduplication process
and, in effectiveness, we consider the F-Measure. Our goal is to evaluate whether
the most efficient and effective data deduplication results are achieved using the
best ranked attributes by the proposed method. We use 95% confidence interval
and 5% of maximum error to define replications as shown in Table 3.
Datasets. We use synthetic and real datasets with a variety of contexts and
attribute types. The synthetic datasets are created by the Data Set Generator
Program [
We also use three real datasets available from the DuDe toolkit2: CORA,
Restaurant and CD Information. These are widely used on data deduplication
research, e.g., [
Parameter Tuning and Evaluation Metrics. Regarding parameter tuning,
we empirically evaluated different setups to choose the values that provide the
best results. Overall, for Jaro Winkler the similarity threshold is 0:9, and for
sorted neighborhood the window sizes vary from 1% to 5% depending on the
dataset size. We compute the commonly used Precision, Recall and F-Measure to
evaluate the data deduplication process, attribute effectiveness and the proposed
method [
In this section we present experimental results on the performance of the proposed method on several domains of synthetic datasets and on the three real datasets. The deduplication results are described in terms of F-Measure and runtime. Let F (ai) be the F-measure yield by attribute ai 2 Ar and Fmax = maxai2Ar F (ai). We consider as candidates to best attribute the set B = faj 2 Ar : Fmax F (aj ) < 0:1g. The best attribute is defined as the candidate in B that has the smallest runtime. With this approach, we can guarantee efficiency without jeopardizing effectiveness. Due to space constrains, only the results in Standard Blocking algorithm are shown.
Synthetic Datasets Evaluation. This experimental evaluation with synthetic data aims to verify if: (i) the proposed method selects efficient and effective attributes in all datasets for various amounts of duplicate records; and (ii) the proposed method scales well for large datasets.
First, we measure the performance of the data deduplication process by using the standard blocking algorithm and varying the amount of duplicate records in the dataset (10%, 30%, 50%, 70% and 90% of duplicate records). Figure 1 presents the results in terms of F-measure (Y-axis) and runtime (X-axis) obtained by each possible choice of attribute in Ar for the indexing step. We only show the results in the datasets with 10%, 50% and 90% of duplicate records because the outcomes are similar in the others (i.e., 30% and 70%). The best data deduplication results are located on attributes near the top left of each chart (faster and more effective attributes). In this case, the performance of each attribute was consistent across datasets.
Next, we calculate the metrics defined in Section 2 for each attribute in each dataset. Then, Table 4 shows the normalized attribute relevance (Equation (5)) combining such metrics. We note that the proposed method selects the best attributes for all datasets, i.e., the most relevant attributes (largest R(a)) are those with the best data deduplication results (Figure 1). Similar to the attributes’ performance, the ranking obtained by R(a) was also consistent across datasets.
In all datasets, the best attribute is the Given Name. Specifically, in the dataset with 10% of duplicate records, Given Name has an F-Measure of 0:7467 (0:0101) and runtime of 4:184 (0:0350) seconds, and is almost two times more GivenName Surname Address1 Address2 Suburb Culture State
Title 0.00 10 20 R3U0NTIM4E(0s) 50 60 70 GivenName Surname Address1 Address2 Suburb Culture State
Title 0.00 10 20 R3U0NTIM4E(0s) 50 60 70 (a) 10% of Duplicates (b) 50% of Duplicates (c) 90% of Duplicates effective than Address2 and six times faster than State. In addition, the worst attributes (Title and Address2 ), i.e., fast but ineffective, are the least relevant attributes according to the proposed method for all datasets. These results indicate that the proposed solution selects efficient and effective attributes for datasets with various amount of duplicate data.
To address the second point, we evaluate the proposed method when using the standard blocking algorithm and varying the total number of instances in f102 106g instances. Figure 2 presents the performance results obtained by each possible choice of attribute in Ar for the indexing step. Note that we do not fix the X-axis scale because the goal is to pinpoint the best attributes for each dataset, instead of comparing the runtimes across datasets. Table 5 shows the attribute relevance ranking for each dataset.
We note that the proposed method selects the best attributes for all datasets except for those with 103 and 106 instances. In those datasets, the second most relevant attribute has the best data deduplication results. In addition, the worst attributes (Title and Address2 ) are ranked as the least relevant by the proposed method in all datasets. Address2 is fast but ineffective, whereas Title is ineffective in all datasets. In the dataset containing 106 instances, there are attributes that yield runtimes longer than one day (State), while others take approximately 15 hours. This highlights the importance of selecting the best attributes for the indexing step. These results indicate that the proposed method is efficient and effective for datasets of very different scales.
Real Datasets Evaluation. We now evaluate the proposed method in three real datasets from different domains – Cora, CDs and the Restaurant datasets, all of which are widely used in data deduplication experiments. We investigate whether the proposed method selects efficient and effective attributes for real datasets from different domains. Figure 3 presents the data deduplication results in terms of F-Measure and runtime, and Table 6 shows the attributes ranking in the corresponding datasets. We use the standard blocking algorithm for the record comparison step.
We observe that the proposed method also identifies the best performing attributes in the real datasets. For the CDs dataset, the most relevant attribute is Artist (Table 6), which has the best data deduplication result (Figure 3a). For the Restaurant dataset, the proposed method does not identify the best attribute. However, the second most relevant attribute (Address1 ) has significant efficiency and effectiveness in the data deduplication process. For CORA, the most relevant attributes (Author and Title) have the best results in deduplication. Overall, our results indicate that the best performing attributes in real datasets tend to be ranked first or at least high, regardless of the data domain. Hence, it can 0.00.0 0.2 0R.U4NTIME0(s.6) 0.8 (b) Restaurant Dataset 1.0 0.00.0 0.5 1.0 1.5
RUNTIME(s) (c) Cora Dataset
Author Title Booktitle Journal Publisher Address Editor
Tech 2.0 2.5 be applied to other relational datasets, being advantageous relative to machine learning algorithms, since it does not require training data.
Results Discussion. This evaluation showed the indexing attribute has a large impact on the efficiency and effectiveness of data deduplication. Regarding effectiveness, in the 10% of duplicate records dataset, attributes Culture and Address2 differ by about 88% (F-Measure of 0:7857 vs. 0:4179). Furthermore, there may be at least four attribute scenarios in the data deduplication results: efficient and effective attribute (Given Name); efficient and ineffective attributes (Title and Address2 ); inefficient attribute (State); and effective but less efficient attributes (Address1, Surname, Suburb and Culture). Regarding runtime, using inefficient attributes for deduplication can take more than one day to run for large datasets, while using more efficient attributes allows it finish in about 15 hours. Thus, selecting the best attribute for indexing is a crucial step. 6
In this work, we presented a method for automatically selecting the best attributes for the first step on data deduplication processing: indexing. The goal was to rank attributes, enabling to identify those that would provide more efficient and effective deduplication. In the experimental evaluation, we evaluated the proposed method on synthetic and on real datasets. Moreover, we assessed questions related to: the efficiency and effectiveness of the indexing attribute considering two of the main methods for record comparison (blocking and neighbor); the indexing functions (agnostic and configurations-based), and the combination of indexing attributes. Due to space constraints, we only showed the results in standard blocking algorithm. Finally, we also verified the effectiveness of the proposed method for selecting relevant attributes.
Our main conclusion is the most efficient and effective data deduplication results are achieved by using the best ranked attributes as given by our method. We are in the process of comparing the proposed method against baselines. In the future, we plan to evaluate our solution over other datasets, analyze cases of failures in which it does not identify the best attribute (Restaurant Dataset) as well as evaluate metrics of false positives and negatives.
Acknowledgments. Research partially funded by CNPq and FAPEMIG, Brazil. The authors also thank PPGCC/UFMG for financial support.