Deduplication is a technique aimed at identifying and resolving duplicate metadata records in a collection with a special focus on the performances of the approach. This paper describes FDup(Flat Collections Deduper), a general-purpose software framework supporting a complete deduplication workflow to manage big data record collections: metadata record data model definition, identification of candidate duplicates, identification of duplicates. FDup brings two main innovations: first, it delivers a full deduplication framework in a single easy-to-use software package based on Apache Spark Hadoop framework, where developers can customize the optimal and parallel workflow steps of blocking, sliding windows, and similarity matching function via an intuitive configuration file; second, it introduces a novel approach to improve performance, beyond the known techniques of “blocking” and “sliding window”, by introducing a smart similarity-matching function T-match. T-match is engineered as a decision tree that drives the comparisons of the fields of two records as branches of predicates and allows for successful or unsuccessful early exit strategies. The eficacy of the approach is proved by experiments performed over big data collections of metadata records in the OpenAIRE Graph, a known open-access knowledge base in Scholarly communication.
Deduplication is a technique for the identification and purging of duplicate metadata records in
large datasets, addressing challenges like eficiency and flexibility in the wider context of entity
resolution[
Outline: Section 2 formally presents the functional architecture of FDup, focusing on the requirements, the model adopted, and the technical implementation of the framework, providing an example of its usage in the OpenAIRE infrastructure. Section 3 describes methods and techniques used to test both the framework eficiency and usability defining an innovative custom configuration for the deduplication. Section 4 provides experimental results and highlights how FDup overcomes traditional approaches for time consumption. Section 5 conclude the paper and delve into possible future works and developments of the framework.
FDup realizes the deduplication workflow shown in Figure 1. The workflow is intended to deduplicate large collections of records, processing them in four sequential phases: • Collection import, to set the record collection ready to process by mapping into a “flat” record with attributes (the use case of this paper is the publication deduplication, using PIDs, title, and authors list); • Candidate identification , to block the records to be matched by sorting them following an and scanning pairs using a sliding window mechanism; • Duplicates identification , to eficiently identify pairs of equivalent records via the T-match function; • Duplicates grouping, to identify groups of equivalent records via transitive closure.
The majority of deduplication frameworks in the literature encode record similarity-matching conditions via a similarity function of the form: ([1, . . . , ], [1′, . . . , ′]) = ∑︁ (, ′) × :0... where the ’s are the values of field , (, ′) are comparators, functions measuring the “distance” of and ′ for the field , and ’s are the weights assigned to the comparators ’s, such that ∑︀:0... = 1. As a result, returns a value in a given range, e.g. [0 . . . 1], scoring the “distance” between two records. The records are considered equivalent if the distance measure exceeds a given threshold.
For the example above, the similarity function ℎ ℎ, created using the GDup framework in OpenAIRE, encodes both equivalence by identity and by value as follows: ℎ ℎ(, ′) = ℎ(. , ′. ) × 0.5+ ℎ(., ′.) × 0.1+ ℎ ℎ(.ℎ, ′.ℎ) × 0.2+ ℎ (., ′.)) × 0.2 where ℎ, applied to the field PID, returns 1 if there is at least one PID in common in the two records; ℎ, applied to the titles, returns 1 if the two titles contain identical numbers or Roman numbers; ℎ returns 1 if the two (normalized) titles have a Levenshtein distance greater than 90%, and ℎ ℎ performs a “smart” matching of two lists of author name strings and returns 1 if they are 90% similar (the minimal equivalence threshold is computed over a manually validated ground truth of equivalent records). All comparators return 0 if their condition is not met. The minimal threshold for two records to be equivalent is 0.5, the threshold that can be reached by ℎ alone or by combining the positive results of the three functions ℎ, ℎ ℎ, and ℎ . All ’s in ℎ ℎ are computed and averagely require a constant execution time, despite the successful or unsuccessful match that those may feature.
Motivated by such observation, FDup introduces a similarity match function T-match that returns an equivalence match exploiting a decision tree, nesting the comparator functions. Each tree node verifies a condition, which can be the result of combining one or more comparators, and introduces a positive (MATCH ) or negative (NO_MATCH ) exit strategy. If the exit strategy is not fired, T-match heads to the next node. An early exit skips the full traversal of the tree and can turn the result into a MATCH, i.e., a simRel relationship between the two records is drawn, or into a NO_MATCH, i.e., no relationship is drawn. By doing this, T-match allows to save time by avoiding unnecessary computations.
A T-match decision is formed by a tree of named nodes with outgoing edges. The core elements of a T-match node are the aggregation function, the list of comparators, and a threshold value. The aggregation function collects the output of the comparators and delivers an “aggregated” result based on one of the following functions: maximum, minimum, average, and weighted mean. The execution of a T-match node must end with a decision, which may be: • positive, i.e. the result of the aggregation function is greater or equal to the threshold value; • negative, i.e. the result of the aggregation function is lower than the threshold; • undefined , i.e. one of the comparators cannot be computed (e.g. absence of values); a node also bears a flag ignoreUndefined that ignores the undefined edge even if one of the values is absent.
For each decision, the node provides the name of the next node to be executed. By default, T-match provides two nodes MATCH and NO_MATCH to be used to force a successful or unsuccessful early exit from the tree.
The example in Figure 2 shows the function ℎ, which uses the same comparators but exploits a T-match decision tree. The individual matches are lined up by introducing MATCH conditions early in the process, i.e. equivalence by identity via ℎ, and then ordering NO_MATCH conditions by ascendant execution time, i.e. equivalence by value via ℎ, ℎ, and ℎ ℎ.
T-match allows for the definition of multiple paths, hence the simultaneous application of alternative similarity match strategies in one single function. The experiments described in later sections will show that when the number of records is large, T-match significantly improves the overall performance of the deduplication process.
FDup’s software is structured in three modules, Pace_Core, Dedup_Workflow, and
Configuration file depicted in Figure 3. The framework is implemented in Java and Scala,
and grounds on the Apache Spark Framework, an open-source distributed general-purpose
cluster-computing framework. FDup exploits Apache Spark to define record collection parallel
processing strategies that distribute the computation workload and reduce the execution time
of the entire workflow. Scala is instead required to exploit the out-of-the-box library for the
calculation of a “closed mesh” in GraphX1. The software is published in Zenodo.org by [
The three modules implement the following aspects of FDup’s architecture: • Pace_Core includes the functions implementing the candidate identification phase (blocking and sliding window) and the T-match function, as well as the (extensible) libraries of comparators and clustering functions. • Dedup_Workflow is the code required to build a deduplication workflow in the Apache Spark Framework by assembling the functions in Pace_core according to the comparators, clustering functions, and parameters specified in the Configuration file. • Configuration file sets the parameters to configure the deduplication workflow steps, including record data model, blocking and clustering conditions, and T-match function strategy.
The deduplication workflow is implemented as an Oozie workflow that incapsulates jobs executing the three steps depicted in Figure 3, to compute: () the similarity relations (), () the merge relations ( ), and () the groups of duplicates and the related representative objects (). More specifically: • : uses classes in the Pace_Core module to divide entities into blocks (clusters) and subsequently computes according to the Configuration file settings for T-match; • : uses GraphX library to process the and close meshes they form; for each connected component, a master record ID is chosen and relationships are drawn between the master record and the connected records; • : uses to group connected records and create the representative objects. 1Apache Spark GraphX, https://spark.apache.org/graphx/
The experiment aims to show the performance gain yielded by the proper configuration of T-match in a deduplication workflow for the publication similarity match example presented in Figure 2. To this aim, the experiment sets two deduplication workflows with identical blocking and sliding window settings but distinct similarity-matching configurations. Both configurations address the similarity criteria but in opposite ways: • ℎ configuration : a configuration that implements the ℎ decision tree illustrated in Figure 2, taking advantage of early exits and the T-match ; • ℎ ℎ configuration : a configuration that implements the similarity match as the GDup (average mean) function ℎ ℎ described in Section 2.1 by combining all comparators in one node, whose final result is a MATCH or NO_MATCH decision.
Both configurations are based on the same settings for candidate identification and duplicate identification. In particular: • The clustering functions used to extract keys from publication records are the on the DOI (e.g. a record produces a key equal to the lowercase DOI, the result is a set of clusters composed by publications with the same DOI) and the on the publication title (e.g. a record entitled "Framework for generalpurpose deduplication" produces the key "orkgen", the result is a set of clusters composed by publications with potentially equivalent titles); both functions are described in ?? • the is set to 200 (empirically) to avoid the creation of big clusters requiring long execution time; • the to limit the number of comparisons inside a block is set to 100 (empirically).
Both ℎ and the ℎ ℎ configurations were
performed over the publication record collection published in [
Two tests were performed, comparing the performance of the configurations ℎ and ℎ ℎ over the 10M and the 230M collection respectively. The tests are intended to measure the added value of T-match in terms of performance gain, i.e. ℎ vs ℎ ℎ execution times.
The tests were performed with a driver memory set to 4 Gb, the number of executors to 32, the executor cores to 4, and the executor memory to 12 Gb. The Spark dynamic allocation has been disabled to ensure a fixed amount of executors in the Spark environment, so as to avoid aleatory behavior. Moreover, since Spark’s parallelization shows diferent execution times, depending on both the distribution of the records in the executors and the cutting operations on the blocking phase, each test has been executed 10 times and the average time has been calculated.
The execution time was measured in terms of processing time required by , where the pair-wise comparisons are performed, and by , where groups of duplicates are generated. It was observed that is dominant taking 70% of the overall processing time. As a consequence, for the sake of experiment evaluation, we: () reported and confronted the time consumed by under diferent tests to showcase the performance gain of T-match, and () reported the results of the to ensure that the tests are sound, i.e. yield the same number of groups, or with a small relative change percentage due to the aleatory behavior described above.
The results of the tests on the 10M publication records dataset and the 230M full publication datasets are depicted in Figure 4 and Figure 5, respectively. The graphs show the average time consumption of the phase for each execution of the test.
The average time of the stage in the test performed over 10M records dataset with the ℎ configuration is 750 seconds, while the ℎ ℎ configuration consumes 1, 536.4 seconds. The test on the 230M records dataset features an average time of 9, 637.6 seconds for ℎ and of 15, 224.5 seconds for ℎ ℎ .
The results reported in Table 1 show that the two scenarios produced a comparable but not identical amount of , , and due to the aleatory behavior Spark.
Based on such results, it can be stated that the ℎ configuration overtakes the ℎ ℎ configuration in terms of time consumption, by improving performance up to 50% in the first test and up to 37% in the second test.
This work presented FDup, a framework for the deduplication of record collections that allows: () to easily and flexibly configure the deduplication workflow depicted in Figure 1 and ( ) to add to the known execution time optimization techniques of clustering/blocking and sliding window, a new phase of similarity match optimization. The framework allows to customize a deduplication workflow using a configuration file and a rich set of available libraries for comparators and clustering functions. The record collection data model can be adapted to any specific context and T-match function allows for the definition of smart and eficient similarity functions, which may combine multiple and complementary similarity strategies. The implementation using Spark contributes to the computation optimization because of the parallelization of the tasks in the clustering and similarity-matching phase. T-match gains further execution time by anticipating the execution of NO_MATCH decisions and postponing time-consuming decisions, such as the ℎ ℎ in the example. As proven by the reported experiments the hypothesis is not only intuitively correct but brings in some scenarios substantial performance gains. When used to analyze big data collections, time-saving is key for many reasons: the execution of experiments to improve a configuration, speeding up the generation of quality data in production systems or saving time that can be “spent” to improve the recall and precision by relaxing clustering and sliding window approaches, i.e., large numbers of blocks and increased window size.
On the other hand, time-saving depends on the ability to identify smart exit strategies applicable to a considerable percentage of the pair-wise comparisons. For example, if the publication record collection used for the experiments features correct and corresponding PIDs for all records, the ℎ execution time would be further improved; on the contrary, if no PIDs are provided, the execution time would increase and get closer to the ℎ ℎ . The two functions would perform identically if the records feature no diferences in the title, making the ℎ ℎ title determinant of the final decision.
The work in this paper has been funded by the projects OpenAIRE-Nexus (grant agreement ID 101017452) and FAIRCORE4EOSC (grant agreement ID 101057264).