Anastasiia Sheveleva

Saïd Hamdi

Aurélien Coillet

Christophe Finot

Pierre Colman
email: pierre.colman@u-bourgogne.fr

Analysis of Dispersive Fourier Transform dataset using Dynamic Mode Decomposition: evidence of multiple vibrational modes, and their interplay in a three-soliton molecule

We demonstrate that the Dynamic Mode Decomposition technique can effectively reduce the amount of noise in Dispersive Fourier Transform dataset; and allow for finer quantitative analysis of the experimental data. We therefore were able to demonstrate that the oscillation pattern of a soliton molecule actually results from the interplay of several elementary vibration modes.

Since its first demonstration, the Dispersive Fourier Transform (DFT) is a key technique to investigate experimentally ultrafast fiber ring laser cavities [START_REF] Jannson | Real-time fourier transformation in dispersive optical fibers[END_REF][START_REF] Goda | Dispersive fourier transformation for fast continuous single shot measurements[END_REF][START_REF] Mahjoubfar | Time stretch and its applications[END_REF][START_REF] Wang | Recent advances in real-time spectrum measurement of soliton dynamics by dispersive fourier transformation[END_REF][START_REF] Godin | Recent advances on time-stretch dispersive fourier transform and its applications[END_REF]. As a convenient way to observe the pulse evolution round-trip after round-trip, this technique allows indeed a better comprehension of the nonlinear phenomena governing these systems. If the main features of fiber ring laser cavities are now well understood, it appears that weaker effects are also of importance because they can built-up to the point where their contribution to the dynamics becomes also determinant [START_REF] Jang | Ultraweak long-range interactions of solitons observed over astronomical distances[END_REF][START_REF] Hamdi | Superlocalization reveals long-range synchronization of vibrating soliton molecules[END_REF]. Correspondingly, DFT experiments would now require either very long record time -so that the long-term dynamics caused by the weaker effects can fully develop; and more acute measurements -so that minute phenomena can be observed. Experimentally, the bottleneck would therefore come from the oscilloscope which records the DFT trace. Indeed, the electronic noise and the discretization granularity prevent recording the single shot spectra with utmost precision.

Using the example of a three-soliton molecule, we demonstrate in this letter that the Dynamic Mode Decomposition (DyMD) allows minimizing experimental noise without compromising the quality of the information. We show in particular that this technique is more efficient than any other curve smoothing techniques, for instance, the Savitzky-Golay filter [START_REF] Savitzky | Smoothing and differentiation of data by simplified least squares procedures[END_REF]. Namely, we fully characterize the oscillations of a 3-Soliton Molecule (SM) and demonstrate that it comprises two nonlinear oscillators of different timescales that are coupled to each other. On a minor side, DyMD permits lossless compression of the DFT dataset by at least a 90 % factor. This demonstration is the occasion to show that DyMD can greatly help to get a finer qualitative analysis of the dynamics of SMs, which are bound states formed by dissipative solitons [START_REF] Lapre | Real-time characterization of spectral instabilities in a mode-locked fibre laser exhibiting soliton-similariton dynamics[END_REF] travelling around the laser cavity in close interaction [START_REF] Stratmann | Experimental observation of temporal soliton molecules[END_REF][START_REF] Akhmediev | Multisoliton solutions of the complex ginzburglandau equation[END_REF]. The large variety of mechanisms responsible for their existence, for instance, gain recovery dynamics, cross-phase modulation effect [START_REF] Nimmesgern | Soliton molecules in femtosecond fiber lasers: universal binding mechanism and direct electronic control[END_REF], laser noise [START_REF] Weill | Noise-mediated casimir-like pulse interaction mechanism in lasers[END_REF][START_REF] Zhou | Oscillatory self-organization dynamics between soliton molecules induced by gain fluctuation[END_REF], emission of dis-persive waves [START_REF] Soto-Crespo | Quantized separations of phaselocked soliton pairs in fiber lasers[END_REF], or acoustic phenomena [START_REF] Jaouën | Transverse brillouin effect produced by electrostriction in optical fibers and its impact on soliton transmission systems[END_REF], results in the SMs exhibiting numerous distinct vibration patterns . In detail, we consider here a 5-m long fiber ring laser cavity comprising 3 meters of Erbium doped fiber and a polarizer (see Fig. 1-(a)). Mode-locking is ensured by nonlinear polarization rotation followed by discrimination through a polarization beam splitter, also acting as the output coupler. After dispersion of the laser output in a -50 ps/nm Highly Dispersive Fiber (HDF), the DFT spectra are recorded by an 80 GS/s, 40 GHz electrical bandwidth, 8-bit depth oscilloscope. The photodiode has a 25 GHz bandwidth, and acts as a low pass filter for higher frequencies. This laser architecture can support the propagation of a 3-SM, characterized by the distinct interferometric fringes seen on the DFT spectra (Fig. 1-(b)). As detailed later in this letter, this molecule can be described as two coupled oscillators. It exhibits in Fig. 2 a complex oscillatory pattern with a principal periodicity of about 71 round-trips (RTs). Note that the SM under investigation here is not a soliton crystal because the solitons do not have the same optical phase: the leading and the trailing soliton are actually π-shifted, resulting in a more unstable interaction. Therefore, the separation between the middle an the last soliton is slightly larger that the one between the leading and middle soliton. Another consequence is that the soliton pairs have radically different properties and exhibit a very complex dynamics [START_REF] Igbonacho | Dynamics of distorted and undistorted soliton molecules in a mode-locked fiber laser[END_REF]. If the vibrations associated to the two closest pairs of solitons can be easily retrieved from the Fourier transform of the DFT spectra, the last oscillatory pattern created by the interaction of the two soliton located at each bound of the molecule clearly suffers from strong measurement noise (Fig. 2-(c,f), black dots) despite the noise level being already drastically reduced by the use of a Savitzky-Golay [START_REF] Savitzky | Smoothing and differentiation of data by simplified least squares procedures[END_REF] filter (hence a 4 th order polynomial fit over a sliding window). This type of filtering does indeed reduce the amount of noise, but it cannot suppress low frequency noise (aka. drift) and, furthermore, filter out any fast-varying data. Consequently, this signal processing helps improving the precision of the measurement to some extend, but it leaves at the same time some residual artifacts that will ultimately limit the former. In brief, the main limitation of such a filtering originates from the fact that it is conducted independently on each single shot spectrum; and therefore it does not benefit from the knowledge of the whole evolution of the single-shot spectra in order to identify truly random features, namely noise. Therefore, we performed a DyMD [START_REF] Schmid | Dynamic mode decomposition of numerical and experimental data[END_REF][START_REF] Schmid | Application of the dynamic mode decomposition to experimental data[END_REF] on the DFT dataset (Fig. 1-(b)) in order to improve the quality of the data. It consists in decomposing the instantaneous snapshot spectra S(λ, n)

at round-trip n as S(λ, n) = k ( M ode k (λ)b k (n) ).
The temporal dynamics of the laser system is then encoded in the b k coefficients (Fig. 3-(c,d), Fig. 4-(b)), whereas the M ode k contains the information related to vibration modes (Fig. 3-(a-b), Fig. 4). This decomposition method makes use of the full DFT dataset, hence it is more accurate than any local filtering and fitting technique. As the DyMD would rely on a round-trip-shifted covariance, we believe that it is very well suited for DFT data because the spectrum evolves nonchaotically round-trip after round-trip. The impact of the DyMD performed with respectively 1, 2, and 4 modes is shown in Fig. 2. First we see in Fig. 2-(c,d) that the relative motion of the trailing and heading solitons is now retrieved correctly, whereas it suffers from very strong noise as seen for the raw data. This validates the possibility for DyMD to investigate larger soliton molecules that would otherwise remained hidden by the electronic noise (the corresponding signal is barely visible in Fig. 1-(d)). In details, we see first that the vibration patterns obtained by mean of the 4-Mode decomposition (Fig. 2, orange lines) follow almost exactly the original data. The 2-mode decomposition (yellow lines in Fig. 2) reconstructs the experimental data with an average error of 1 bit, and the maximal error never exceeds 2 bits. Indeed, if we look at Fig. 1-(b,c) where are shown the original DFT data, the reconstruction is done with little error (Fig. 1-(e)). A reconstruction error below -24 dB would actually correspond to a lossless reconstruction for a 8-bits digitization of a full scale signal. True lossless reconstruction is obtained for 8-mode decomposition (not shown here). As a side remark, the memory requirement for such a decomposition (2 10 points per spectrum, 2 14 Round-Trips, 32 bits resolution) would correspond to a compression of the experimental raw data by 93%. In contrast, the decomposition using a single mode clearly misses a few important features, like, for instance, the fast over-modulation in Fig. 2-(d).

The 2-mode DyMD appears here to be the best choice; and the corresponding modes are shown in Fig. 3-(a,b). An important point is that this decomposition does not only reduce the amount of noise, it also allows a finer interpretation of the SM vibration pattern. The b k coefficients (Fig. 3-(c,d)) are indeed completely correlated to the molecule oscillations shown in Fig. 2. We see that the weak over-modulation of 5.24 RTs periodicity that is over-imposed on the main oscillation originates almost exclusively from the second mode, whose b 2 coefficient exhibits clearly fast varying features. In contrast b 1 evolves more slowly, following a periodic pattern with high harmonic content. Detailed Fourier analysis in Fig. 3-(e) confirms this relative distribution of fast and slow oscillations between the two modes. Statistically, independent oscillators are described by different modes; this is then the case here. It is actually the reason behind the failure of the single-mode DyMD as it cannot reproduce concomitantly the dynamics of two independent modes. Knowing the shape of the modes, their impact on the SM's motion can then be traced back in Fig. 4. The first vibration mode does not impact much the relative distance between the leading and trailing solitons. This fact does not change even if more modes are included in the DyMD. As a good approximation, the first mode involves the motion of the middle pulse, along with the corresponding dephasing of the first dissipative soliton. In the second mode, the middle pulse acts as an anchor, and the two other pulses move (and dephase) in an anti-symmetric manner. We can conclude that each of the two fundamental vibration patterns does not necessarily involve a single soliton pair, and that it spans over the whole molecule. Therefore, the oscillation experienced by the 3-soliton, or more complex, SM must not be simply described by looking only at the vibrations of soliton pairs. If the two oscillators are independent entities, they, however, interplay with each other. Indeed both b 1 and b 2 show, respectively, modulations at high and low frequencies, which is characteristic of an interac-tion between the two vibration modes (Fig. 3-(e)). In detail b 2 encodes the fast oscillation of about 5 RTs periodicity, but exhibits at the same time a modulation at the main fundamental oscillation period (71 RTs). In Fig. 3-(e) the tone of the fast oscillation (located at about 0.2 RT -1 ) is modulated by the main slow oscillation, resulting in the creation of two equally spaced sidebands. This is the direct consequence of the slow oscillation modifying adiabatically the parameters of the fast oscillator.

We would like to stress that this phenomenon can only be clearly observed because the experimental noise has been reduced so that the small fast overmodulation takes over. As a consequence, the spectral comb that characterizes the modulation of one oscillator by another is only fully revealed by the DyMD approach. To allow a global comparison are presented on Fig. 5 the different spectrum of τ 2-3 depending on the data processing. This confirms that the single mode DyMD clearly is not able to reproduce correctly the signal because it misses the fundamental tone of the fast oscillation. Compared to the raw data, which show only one, the 2-Mode DyMD exhibits up to six harmonics. The DyMD technique also permits in-depth understanding of the molecule vibration through analysis of the b k coefficients. In literature, vibrations of SMs are usually classified depending on how the optical phase between the solitons evolves [START_REF] Krupa | Real-time observation of internal motion within ultrafast dissipative optical soliton molecules[END_REF], and a single oscillation pattern is usually assumed. Here the SM experiences a periodic evolution (71 RTs), set by the largest and strongest oscillator (b 1 ) that bounds the whole molecule. Still there exists a minor part of this oscillation that is caused by another oscillator, characterized by the coefficient b 2 . Consequently the SM is under the influence of at least two limit cycles of radically different nature. The fast oscillation is of much weaker amplitude and thus it is not strong enough to take over the dynamics. The co-existence of several limit cycle attractors, and their range of attraction, is a fundamental question for a better understanding of the creation and the dissolution of SMs [START_REF] Grelu | Dissipative solitons for mode-locked lasers[END_REF][START_REF] Schreiber | On the study of pulse evolution in ultra-short pulse mode-locked fiber lasers by numerical simulations[END_REF][START_REF] Zavyalov | Dissipative soliton molecules with independently evolving or flipping phases in mode-locked fiber lasers[END_REF][START_REF] Zavyalov | Discrete family of dissipative soliton pairs in mode-locked fiber lasers[END_REF]. There exists mostly scarce information regarding the stability of the molecules'motion. Assessing the latter experimentally is usually tricky as it might involve ac-tually the destruction of the SM as soon as one tries to alter forcefully its properties. Here we see that a finer analysis of the SM motion allows to get a better estimation of its stability by simply looking at its weak fluctuations. It provides also clear indication regarding how the destabilization of the SM would occur. Considering here that the optical phase relationship between the leading and trailing solitons is not favorable for the SM's stability, one hypothesis we could formulate is that a larger fast trembling could eventually result into the SM achieving a more stable conformation (metastability). The SM can thus switch between limit cycle attractors. To conclude, we demonstrated that Dynamic Mode Decomposition is a suitable method for the analysis of DFT data. By reducing the noise, it allows the observation of minute phenomena that would have otherwise remained hidden. Moreover, the DyMD decomposition can be used to compress the data efficiently, without loss of information. Depending on the denoising which is desired, the initial data set can be sequentially reconstructed using a different number of modes. For instance, the single mode projection clearly lacks details. When it comes to the quantitative analysis of the experimental data, the DyMD is able to reveal how a complex oscillation pattern of the SM is shared between its elementary constitutive components; and separate the temporal evolution of the individual vibration modes from their spatial distribution. We are then able to describe complex vibration patterns that involve more than two pulses, and this technique could be extended to more complex solitonic systems [START_REF] Wu | Intelligent breathing soliton generation in ultrafast fiber lasers[END_REF]. As a practical example, we investigated the dynamics of a 3-Soliton molecule in an ultrafast fiber ring laser cavity. We were able to demonstrate that the soliton belonging to the same molecule may not experience the same vibration, and that at least two limit cycles of different kind could co-exist inside the same laser cavity. The optical phase difference of ∆φ between the leading and the trailing soliton is known to create repulsion. This poses the question regarding the meta-stability of some soliton molecules configurations. And it reinforces the interest in experiments (and data analysis) of acute precision as most transition phenomena start from weak instabilities. For this first proof-of-principle demonstration about the opportunities that are offered by the DyMD, we implemented the DyMD on the raw DFT spectral data, without performing any subsequent data treatment. The technique also has the denoising and compression capability. Regarding the analysis of the dynamics based on the analysis of the mode decomposition, the DyMD representation can be seen as a change of basis (or a projector, similar to a principal component analysis -PCA). Consequently, some DyMD decompositions could be more straightforward to interpret, depending on the system under study. For example, without changing the main conclusions, the DyMD could have been performed on the Fourier transformed data (Fig. 1-(d)) instead of the raw DFT data, or even on the resulting SM motion (Fig. 2). We believe that this letter paves the way for more detailed analysis of the SM dynamics. In particular, we demonstrated that the oscillatory pattern of SMs results from the interplay of individual vibration modes and we were able to extract the round-trip evolution of each mode. It is then possible to investigate further how the modes interact by constructing a simpler nonlinear model that would reproduce the interplay that is observed between the b k coefficients.

Figure 1 :

 1 Figure 1: (a) Experimental setup; PBS: polarization beam splitter; HDF: 545 m of Highly Dispersive Fiber; Pump: 980-nm laser diode; WDM: pump-signal multiplexer. (b) Single-shot spectra. (c) DFT Spectra after 2-Mode reduction by Dynamic Mode Decomposition. (d) (logarithmic scale) Fourier Transform of (b) showing three characteristic inter-Soliton seperations of 4.1 ps 4.6 ps and 8.7 ps (pink arrows). (e) Error of the DyMD in (b). -3 dB corresponds to 1 Bit of precision (hence -24 dB is 8-Bit precision). Subpanels (b-e) are represented in logarithmic scale.

Figure 2 :

 2 Figure 2: (a-b-c). Evolution of the inter-soliton separation for diffreent soliton pairs: {1 -2}, {2 -3}, and {1 -3}, respectively. (d-e-f): Same as above, but for the optical phase difference between the solitons. Black points stand for data processed using a Stavitzky-Golay filter. Orange: 4-Mode DyMD. Yellow: 2-Mode DyMD. Purple: 1-Mode DyMD.

Figure 3 :

 3 Figure 3: (a-b) Representation of the 1 st and 2 nd modes of the 2-Mode DyMD (c-d) Evolution of the coefficients b k , k = {1, 2} used for the reconstruction. (e) Logarithmic Scale. Spectra of evolving vibration mode's amplitude b k .

Figure 4 :

 4 Figure 4: Schematic representation of the two vibration modes, indicating the relative displacement of the dissipative solitons (arrows, with amplitude of the displacement indicated), and the concomitant changes of optical phase. These representations can be obtained numerically by zeroing either the b 1 or b 2 coefficients during the DyMD reconstruction. For clarity, the numbers have been rounded up.

Figure 5 :

 5 Figure 5: Spectrum of the round-trip evolution of the inter-soliton separation τ 2-3 . Blue: raw data. Red: Data processed by a 4 th order Savitzky-Golay filter. Dark and Light Grey: Results of 2-and single-Mode DyMD, respectively. Note the apparition of spurious harmonic tone, along with the disappearance of the fast oscillation's tone around 0.2 RT -1 .

Funding

This work was supported by the French ANR program, project OPTIMAL (contract ANR-20-CE30-0004)

Data Availability Statement

Data underlying the results presented in this paper may be obtained from the authors upon reasonable request.

Disclosures

The authors declare no conflicts of interest.


Loujain Liekah
email: loujain.liekah5@gmail.com

George Papadakis
email: gpapadis@di.uoa.gr

Deduplication Over Heterogeneous Attribute Types (D-HAT)

Keywords: Clustering, Entity matching, Data quality

Deduplication is the task of recognizing multiple representations of the same real-world object. The majority of existing solutions focuses on textual data, this means that data sets containing boolean and numerical attribute types are rarely considered in the literature, while the problem of missing values is inadequately covered. Supervised solutions cannot be applied without an adequate number of labelled examples, but training data for deduplication can only be obtained through time-costly processes. In high dimensional data sets, feature engineering is also required to avoid the risk of overfitting. To address these challenges, we go beyond existing works through D-HAT, a clustering-based pipeline that is inherently capable of handling high dimensional, sparse and heterogeneous attribute types. At its core lies: (i) a novel matching function that effectively summarizes multiple matching signals, and (ii) MutMax, a greedy clustering algorithm that designates as duplicates the pairs with a mutually maximum matching score. We evaluate D-HAT on five established, real-world benchmark data sets, demonstrating that our approach outperforms the state-of-the-art supervised and unsupervised deduplication algorithms to a significant extent.

Introduction

Integrating overlapping and complementary data sets is a common process that creates new and valuable knowledge [START_REF] Chen | Big data: a survey[END_REF]. The main task of integration is to identify duplicate records, which represent the same real-world entity, such as products, institutes, or patients. This task is called deduplication [START_REF] Dong | Big data integration[END_REF], entity matching [START_REF] Konda | Magellan: toward building entity matching management systems[END_REF], entity resolution [START_REF] Papadakis | Blocking and filtering techniques for entity resolution: a survey[END_REF] or record linkage [START_REF] Fellegi | A theory for record linkage[END_REF]. It constitutes a crucial task that improves the data quality by repairing and curating data sources [START_REF] Fan | Interaction between record matching and data repairing[END_REF], reducing the storage size, and preparing data for downstream applications [START_REF] Dong | Big data integration[END_REF].

Existing solutions for deduplication are based on calculating pairwise similarity scores from one or more attributes [START_REF] Christophides | An overview of end-to-end entity resolution for big data[END_REF]. The unsupervised methods create This project has received funding from the European Union's Horizon 2020 research and innovation program under grant agreement No 875171.

a similarity graph, where the nodes correspond to records and the edges are weighted by the matching scores of the adjacent nodes [START_REF] Hassanzadeh | Framework for evaluating clustering algorithms in duplicate detection[END_REF]. The graph is then partitioned into clusters such that all nodes within each cluster correspond to duplicate records. These approaches typically calculate matching scores by treating all attributes as textual data [START_REF] Christophides | An overview of end-to-end entity resolution for big data[END_REF]. However, real-world data sets involve heterogeneous attribute types, i.e., numerical, categorical and boolean attributes. Casting these types as strings disregards important information and possibly leads to inaccurate matching scores. For example, the prices "14" and "14.00" are identical as numbers, but partially similar when compared as sequences of characters and totally dissimilar when treated as tokens. Hence, unsupervised techniques need to correctly model and support heterogeneous attribute types.

On the other hand, supervised methods typically model deduplication as a binary classification task [START_REF] Konda | Magellan: toward building entity matching management systems[END_REF]. They convert each pair of records into a feature vector by applying similarity metrics on different attributes. The vectors are then labelled to train a classifier that predicts the matching status for unlabelled pairs. However, these approaches face multiple challenges: (i) The curse of dimensionality, i.e., tasks become exceedingly difficult with a higher number of dimensions. (ii) Labeled data is scarce, but obtaining it through crowd-sourcing is costly and time-consuming [START_REF] Wang | CrowdER: crowdsourcing entity resolution[END_REF]. Moreover, its size and quality affects the end result to a significant extent [START_REF] Mudgal | Deep learning for entity matching: a design space exploration[END_REF], but are hard to ensure, due to the heavy class imbalance. (iii) Supervised methods require long training times [START_REF] Mudgal | Deep learning for entity matching: a design space exploration[END_REF].

To address these shortcomings, we introduce D-HAT (Deduplication with Heterogeneous Attribute Types), a novel clustering-based pipeline for end-to-end deduplication. D-HAT goes beyond existing works in three ways: (i) It inherently supports data sets with heterogeneous types of attributes and a large portion of missing values (i.e., high sparsity). (ii) It inherently supports and leverages complex schemata of high dimensionality.

Related Work

The growing research on deduplication reflects its increasing importance, with numerous methods tackling various aspects [START_REF] Christen | The data matching process[END_REF][START_REF] Christophides | An overview of end-to-end entity resolution for big data[END_REF][START_REF] Dong | Big data integration[END_REF].

One of deduplication's main challenges is its quadratic complexity: in the worst case, it examines all possible pairs of records. Blocking is typically used to alleviate this complexity and to scale deduplication to voluminous data sets [5,[START_REF] Papadakis | Blocking and filtering techniques for entity resolution: a survey[END_REF]. Blocking puts together similar records in groups called blocks by applying blocking schemes or functions. A blocking function extracts signatures from every record, dividing the input data set into a set of overlapping blocks -comparisons are reduced to candidates, i.e., pairs of records sharing at least one block, reducing the computational cost to a significant extent. Yet, the higher time efficiency comes with the risk of missing potential matches [START_REF] Papadakis | Comparative analysis of approximate blocking techniques for entity resolution[END_REF].

After blocking, matching is performed to determine the degree of similarity between the candidate pairs of records. In essence, it applies similarity functions to the values of selected attributes of the candidate records, obtaining numerical matching scores. Next, it determines whether the resulting degree of similarity is sufficient for designating two records as duplicates. We distinguish the matching algorithms into unsupervised and supervised ones.

The former category includes a collection of methods that are provided by JedAI [START_REF] Papadakis | Three-dimensional entity resolution with JedAI[END_REF][START_REF] Papadakis | The return of JedAI: end-to-end entity resolution for structured and semi-structured data[END_REF] and Stringer [START_REF] Hassanzadeh | Framework for evaluating clustering algorithms in duplicate detection[END_REF], with ZeroER [START_REF] Wu | ZeroER: entity resolution using zero labeled examples[END_REF] constituting the state-of-theart unsupervised approach; it represents every candidate pair as a feature vector. Unlike supervised methods, it does not require a training set. Instead, at its core lies the observation that the distribution of the feature vectors for duplicate records differs from that of the non-matching records. Based on this idea, it learns the parameters of the Gaussian distribution of matching vectors by iteratively applying expectation maximization to compute the posterior probability of a matching label given the feature vector. A posterior probability higher than 0.5 is considered as an indication of duplicate records.

Among the supervised methods, the most popular one is Magellan [START_REF] Konda | Magellan: toward building entity matching management systems[END_REF], a system that combines a variety of features with the main machine learning classifiers, such as decision trees, logistic regression and support vector machines. After providing an annotated sample of candidate pairs T , matching is performed by training a classifier over T . Magellan also offers a set of blocking methods.

DeepMatcher [START_REF] Mudgal | Deep learning for entity matching: a design space exploration[END_REF] is a space of matching solutions based on neural networks with three modules: i) attribute embedding, ii) attribute similarity representation, and iii) a classification module. In most cases, the first module relies on pre-trained fastText embeddings [START_REF] Bojanowski | Enriching word vectors with subword information[END_REF] to convert every token to a vector. EMTransformer [START_REF] Brunner | Entity matching with transformer architectures -a step forward in data integration[END_REF] and DITTO [START_REF] Li | Deep entity matching: challenges and opportunities[END_REF] go beyond DeepMatcher by leveraging attentionbased transformers like BERT [START_REF] Devlin | BERT: pre-training of deep bidirectional transformers for language understanding[END_REF], and RoBERTa [START_REF] Liu | RoBERTa: a robustly optimized BERT pretraining approach[END_REF]. These solutions perform well on textual data, outperforming Magellan in terms of accuracy [START_REF] Brunner | Entity matching with transformer architectures -a step forward in data integration[END_REF][START_REF] Li | Deep entity matching: challenges and opportunities[END_REF][START_REF] Mudgal | Deep learning for entity matching: a design space exploration[END_REF]. We disregard them, as they require large training sets and many hours of training [START_REF] Mudgal | Deep learning for entity matching: a design space exploration[END_REF] in order to fine-tune hundreds of thousands of parameters [START_REF] Wang | CorDEL: a contrastive deep learning approach for entity linkage[END_REF].

Preliminaries

A data set T is a collection of records. A record is an object description denoted by r i , where i is a unique identifier. Records are defined by their attributes. The set of attributes in T is denoted by T.A, while the value of a specific attribute a in record r i is symbolized as r i .a; r i .a = N/A indicates that r i lacks a value for a, i.e., there is a missing or a null value. Two records, r i and r j , that describe the same real-world object are matching, i.e., duplicates, a situation denoted by r i ≡ r j . A data set is called clean if it does not contain any duplicates. Deduplication is the task of identifying and linking duplicate records. A characteristic of this task is that the number of duplicate records scales linearly with the size of the input, unlike its computational cost, which increases quadratically [START_REF] Getoor | Entity resolution: theory, practice & open challenges[END_REF]. As a result, Deduplication constitutes a heavily imbalanced task and its effectiveness is measured with respect to the following measures:

1. Recall, the portion of existing duplicates that are detected, i.e., Re = T P T P +F N . 2. Precision, the portion of record pairs characterized as duplicates that are indeed matching, i.e., P r = T P T P +F P . 3. F-Measure, the harmonic mean of Recall and Precision, F 1 = 2 × P r×Re P r+Re , where TP stands for the true positive pairs, FP for the false positive ones, and FN for the false negative ones.

In this context, Deduplication can be formally defined as follows:

Problem 1 (Deduplication). Given a data set T , detect the set of duplicate pairs of records, D = {r i , r j ∈ T : i = j ∧ r i ≡ r j }, such that Recall, Precision and F-Measure are maximized.

Our Approach

We now delve into our framework, whose pipeline is illustrated in Fig. 1.

Step 1: Data Cleaning. The first step prepares the input by determining the core characteristics of the attributes describing the given data set(s)1 , i.e., it calculates the number of unique values and the data type per attribute. Attributes that have two unique values are converted to boolean to obtain a more precise degree of similarity. Attributes with very few unique values (<10) are treated as categorical variables. Numerical attributes are identified through regular expressions that detect quantities, possibly accompanied by an optional unit of measurement. E.g., an attribute value width = ''42.8 in'' is transformed into width = 42.8 and is marked as a numeric data type. Min-max normalization is then performed on the values of numeric attributes:

Step 2: Attribute Selection. Attributes with a majority of missing values lack valuable information for deduplication and, thus, can be disregarded. The coverage of an attribute a expresses the portion of non-empty values in a across all input records; the fewer missing values there are, the higher is the coverage. We formally define the coverage c of each attribute as: c(a) = 1-|ri.a=N/A:ri∈T | |T | . This step discards the attributes with a coverage below a specific threshold. Preliminary experiments demonstrated that 0.1 constitutes an effective value.

Step 3: Blocking. This step is critical because it determines two things: 1. Time efficiency, because the processing time of the following steps is determined by the number of candidates in the resulting blocks. 2. Effectiveness, because the recall of D-HAT is bounded by the recall of blocking; the false negative pairs of records, which have no block in common, cannot be detected by the subsequent steps, and are excluded from the final output.

Therefore, it is crucial that blocking balances these two competing goals: the reduced search space and the high effectiveness. D-HAT is generic enough to accommodate any blocking method that meets this requirement. Preliminary experiments indicated that Magellan's [START_REF] Konda | Magellan: toward building entity matching management systems[END_REF] overlap blocker is a robust approach for creating blocks of high performance (see Sect. 5 for more details). It defines as candidate pairs those sharing at least one token in the values of a specific attribute. D-HAT applies the overlap blocker to all textual attributes in the given data sets and opts for the one minimizing the number of candidates, while maximizing coverage -high coverage implicitly signals high recall after blocking.

Step 4: Feature Matrix. Similar to supervised approaches, D-HAT represents each pair of records as a feature vector by applying type-specific normalized similarity functions to selected attributes. Unlike supervised approaches, these vectors are unlabelled. In more detail, after detecting the type of every attribute in Step 1, D-HAT creates a feature vector V i,j for each candidate pair of records (r i , r j ) ∈ B, where B is the set of blocks produced by the previous step and the k th feature/dimension in V i,j , V k i,j , stems from a similarity function that is compatible with the type of the k th attribute, a k . If the value of either record for a k is empty or incorrect (i.e., incompatible with the type of a k ), V k i,j ='N/A', which stands for a missing feature. Note that this step does not require any domain knowledge from the user. D-HAT automatically detects the attribute type and applies the appropriate similarity functions in order to create the features.

In particular, the following functions are used by D-HAT:

• For boolean and categorical attributes, the equality operator.

• For numerical attributes, four similarity functions are used:

1. The equality operator, 2. The Euclidean similarity, -Levenshtein similarity, the minimum number of edit operations (insert, delete or substitute) required to transform one string to another. -Hamming, similar to Levenshtein except that it allows only substitution. (ii) Semantic similarity measures. D-HAT exploits pre-trained embedding representations of textual data. Two types of representations are actually used: a) Word-based models like word2vec and GlobalVectors (GloVe). They substitute each token (word) by a meaningful numeric vector that is learnt from training a shallow feedforward neural network on large, external, un-annotated textual corpora, such as Google News and Wikipedia. In these models, words with contextual similarity have linearly related vector representations. However, they cannot produce vector representations for words that are out-of-vocabulary. b) To address this limitation, skipgram models like fastText [START_REF] Bojanowski | Enriching word vectors with subword information[END_REF] represent each word by the sum of the vector representations of its bag of characters. Thus, they are capable of learning a recurrent neural network that yields vector representations for words, independently of their occurrence in the training data. To extract numeric features/dimensions from the three pre-trained embeddings (i.e., word2vec, GloVe and fastText), D-HAT applies three similarity functions to the vectors of two records: the cosine, the Euclidean and the word mover's similarity [START_REF] Kusner | From word embeddings to document distances[END_REF]. For the last two functions, the homonymous distance function d is transformed into a similarity value sim as follows: sim = 1 1+d . (iii) Hybrid similarity measures. This configuration combines the aforementioned syntactic similarity measures with the semantic ones, given that they capture complementary matching evidence.

V k i,j = 1 -EucDist(r i .a k , r j .a k ). 3. The relative similarity, V k i,j = 1 -
Overall, D-HAT creates one feature per boolean and categorical attributes, four per numeric ones as well as nine semantic features and up to seven syntactic ones per textual attribute.

Step 5: Matching Scores. The goal of this step is to estimate the matching likelihood for each pair of candidates based on the feature matrix of the previous step. This is carried out in two steps:

(i) Binarizing the feature vectors. In essence, D-HAT treats each feature as a vote for a "match" (1) or a "non-match" (0) decision. The dimensions of boolean and categorical attributes are already binary. The dimensions of numerical and textual attributes are defined in [0, 1], with higher values indicating a higher matching likelihood. To binarize them, D-HAT employs a similarity threshold θ ∈ [0, 1], common to all dimensions, such that all numeric scores above θ are converted into "match" votes (1), while the rest become "non-match" votes (0). All dimensions with a "N/A" value are ignored. (ii) Score estimation. To calculate the matching score m i,j for two candidate records, r i and r j , we aggregate the dimensions of their binary feature vector V i,j into a single value through their mean, i.e., m i,j = N k=1

V k i,j /(Nn), where N is the total number of features, n is the number of missing ones and V k i,j ∈ {0, 1}. At the end of these two steps, the matching scores of all pairs are calculated and stored in a matrix M . The records and the matrix define a weighted graph G(V, M ), where the set of nodes V represent the input records, and M is the adjacency matrix of weights. G(V, M ) is referred to as the similarity graph.

Step 6: MutMax Clustering. The final step receives as input the similarity graph G(V, M ) and partitions it into a set of disjoint clusters, such that every cluster corresponds to a unique entity, containing all duplicate records describing it. The partitioning is performed by MutMax, a greedy approach that defines as duplicates the pairs of records with mutually maximum scores. More specifically, MutMax operates as follows: For each record r i , all candidates are sorted in decreasing matching scores and the top one r i max = r j is selected as the potential match. If r i was set as the potential match for r j , the records r i and r j are designated as matches. The rest of the candidate pairs are ignored.

Overall approach. D-HAT algorithm is outlined in Fig. 2.

Step 1 (Data cleaning) is applied first (Line 1). Step 2 (Attribute selection) is performed given threshold c min (Lines 2-7). The overlap blocker is applied to each attribute (Lines 8-10). A performance score is computed per attribute by multiplying the coverage of attribute a with the reduction ratio [5]: getScore(B a , a) = c(a) • RR(B a , T ), where |B a | denotes the total number of candidate pairs in the blocks B a . The attribute with the highest score is selected (Lines 11-14), and is applied to retrieve the final set of blocks (Line 16).

The next loop simultaneously applies Steps 4 and 5. It builds a twodimensional array M with a score for each pair of compared records. In more detail, F ∩ a is the set of functions applicable for attribute a. For each feature higher than θ, the overall similarity is incremented by one matching vote (Lines [START_REF] Wang | CorDEL: a contrastive deep learning approach for entity linkage[END_REF][START_REF] Wu | ZeroER: entity resolution using zero labeled examples[END_REF][START_REF] Christen | A survey of indexing techniques for scalable record linkage and deduplication[END_REF]. The average score is finally estimated for the current pair of candidates (Line 29).

Finally, MutMax is applied to M (Lines 31-36). For each record, the most similar candidate is specified and stored in array O (Line 31). Using O, D-HAT identifies the record pairs that are mutually most similar (Lines 32-33), adding them to the output (Line 34). Note that D is a set and that each output pair is formed with the lowest id in the left part (i.e., i < j in (i, j) in Line 34); as a result, no duplicate pairs are returned as output.

In terms of time complexity, the cost of Steps 1, 2 and 3 is linear with the number of attributes in the given data set T , i.e., O(|T.A|). For Steps 4 and 5, the cost is O(|B|). For Step 6 no sorting is required. Instead, D-HAT merely iterates once over all cells in the two-dimensional array M . A hash table can be used to store the estimated similarities in practice. As a result, both the time and space complexity of Step 6 (and the entire algorithm) are linear with the number of candidate pairs after blocking, i.e., O(|B|).

Experimental Evaluation

Setup. D-HAT is implemented in Python 3.8.5. All experiments were run on an Ubuntu 18.04.5 server with a 12-core Intel Xeon D-2166NT @2GHz, 64 GB of RAM and 300 GB HDD. A single core was employed in all time measurements.

Benchmark Data Sets. We employ five established data sets that come from multiple domains: products, bibliography, restaurants, and healthcare. Immucare is a healthcare dataset matching two hospital visits of the same patient. The technical details of these data sets [START_REF] Konda | Magellan: toward building entity matching management systems[END_REF][START_REF] Wu | ZeroER: entity resolution using zero labeled examples[END_REF] are summarized in Table 1.

Baseline Systems. We compare the performance of D-HAT with Magellan [START_REF] Konda | Magellan: toward building entity matching management systems[END_REF] and ZeroER [START_REF] Wu | ZeroER: entity resolution using zero labeled examples[END_REF]. For the former, we use decision tree as the classification algorithm, while for the latter, no configuration is needed.

Evaluation Measures. We use the standard measures of recall, precision, and F1-score, which are defined in Sect. 3. We also report the overall run-time, i.e., the time that intervenes between receiving the data set(s) as input and producing the duplicate pairs as output. We repeat every measurement three times and report the average.

Step 3: Blocking

D-HAT applies Magellan's overlap blocker to all attributes and selects as optimal the one minimizing the number of candidates, while maximizing coverage. The resulting performance appears in Table 2. In all cases, the number of candidate pairs is reduced by whole order of magnitude (i.e., 90%) in comparison to the brute-force approach (i.e., |S| × |T |). The only exception is Abt-Buy, where the candidates drop by 86%, which is a dramatic reduction of the search space, too. Nevertheless, the recall in all cases remains rather high, above 90%. This means that the vast majority of duplicate pairs co-occur in at least one block.

Note that precision after blocking remains very low for most data sets. To raise it to acceptable levels, matching is required. Note also that compared to the overall run-time of D-HAT and the rest of the methods (in Fig. 3), the overhead of blocking is negligible (< 10% in all cases). The only exception is Immucare, where the overhead of blocking is high, due to the very large number of attributes retained after Step 2 (75).

Steps 4-6: Matching

To ensure fairness, we apply the same blocker to the same key attribute for both baseline systems, (e.g., we use the 'phone' attribute instead of 'name' in Fodors-Zagats). Note that for Amazon-Google, ZeroER could not create its feature matrix within a time limit of 6 h. To complete the assessment, we combined it with the feature vectors created by Magellan instead. As a result, the performance of ZeroER could be slightly different from that reported in [START_REF] Wu | ZeroER: entity resolution using zero labeled examples[END_REF].

The resulting performance of all algorithms with respect to precision (Pr), recall (Re) and f-measure (F1) appears in Table 3, while the corresponding runtimes are reported in Fig. 3. Note that after preliminary experiments, we set c min = 0.1 and θ = 0.7 for D-HAT in all cases. Note also that D-HAT is combined with three different groups of features: (i) The syntactic ones, which include only the syntactic similarity functions for textual attributes along with the specialized functions of boolean, categorical and numeric attributes. (ii) The semantic features, which differ from the previous group in that they replace the syntactic similarity functions with the semantic ones. (iii) The hybrid features, which employ all similarity functions for all types of attributes defined in Sect. [START_REF] Christen | The data matching process[END_REF]. In this way, we are able to examine the contribution of the two types of textual similarity functions, which account for the majority of features used by D-HAT.

Compared to blocking, precision has actually increased by whole orders of magnitude. This emphasis on precision should be attributed to MutMax clustering, which associates every record only with its most similar candidate.

Comparing the various groups of features between them, we observe that the syntactic ones consistently outperform the semantic ones. The reason is that most data sets contain domain-specific terminology. As a result, especially word2vec and GloVe suffer from a large portion of out-of-vocabulary terms. The only exception is DBLP-ACM, which involves long textual attributes like venue names and publication titles; in these settings, the evidence provided by semantic similarities outperforms the syntactic ones, albeit by just ∼2%.

In terms of time-efficiency, the advantage of syntactic similarity functions is clear in all cases, as shown in Fig. 3. The run-time of D-HAT increases by a whole order of magnitude in almost all cases, when replacing the syntactic similarity features with the semantic ones. This is caused by the large number of lookups and computations that are required for converting every attribute value into a high-dimensional embedding and a similarity score.

It is interesting to examine whether the combination of syntactic and semantic similarities justifies the lower time efficiency by an increase in effectiveness. This is only true in Amazon-Google, where hybrid features' F1 is higher than the syntactic ones by ∼10%. In all other cases, the hybrid features lie between the two other groups of features, usually closer to the top performing one. Hence, D-HAT should be exclusively combined with the syntactic group of features.

Compared to ZeroER, Table 3 shows that D-HAT with syntactic features achieves significantly better effectiveness in most cases. Its f-measure is actually higher by 50%, on average, across the five data sets. At the same time, Fig. 3 demonstrates D-HAT is consistently faster than ZeroER by whole orders of magnitude (e.g., 1 min vs 6 hrs over Amazon-Google) -the sole exception is DBLP-ACM, where D-HAT is slower, due to the computation of 10 syntactic similarity functions over textual values. D-HAT takes into account attributes with high level of noises (missing values, heterogeneity of existing values, errors), which inevitably corrupt some matching signals.

Compared to Magellan, in the first two data sets, D-HAT achieves a higher f-measure than Magellan by more than 13%, while in the next three data sets both methods exhibit practically identical performance (i.e., their f-measures differ by less than 1%). The competitive performance of Magellan stems from its supervised functionality: in each dataset, 70% of the candidate pairs are used for training its classification model, leaving only 30% of the pairs as a testing set. In contrast, D-HAT processes all candidate pairs and its performance is bounded by blocking. In terms of time-efficiency, we observe in Fig. 3 that D-HAT takes a clear lead in all cases, as its run-time is lower than Magellan even by a whole order of magnitude (e.g., 35 vs 400 s over Abt-Buy).

Overall, D-HAT typically outperforms the state-of-the-art unsupervised deduplication method to a significant extent in all respects. Compared to the state-of-the-art supervised approach, it exhibits similar effectiveness, if not higher, at a much lower run-time, despite the lack of labelled instances.

Sensitivity Analysis

The only configuration parameter that is crucial for the performance of D-HAT is the similarity threshold θ, whose value depends on the level of noise and heterogeneity in the data. To assess its impact on the overall performance of D-HAT, we consider all values in the range [0.5, 1] with a step of 0.1. The results appear in Fig. 4. Due to lack of space, we report three of the five datasets. We observe that this parameter has no effect on any evaluation measure over DBLP-ACM. The reason is that the pairs identified as matches in these datasets exhibit very high similarity (practically 1.0) for most of the features employed by D-HAT. As a result, the matching decisions of MutMax clustering are not altered by the value of θ. For Abt-Buy and Amazon-Google, we observe that up to 0.7, the performance of D-HAT improves (Abt-Buy) or remains the same (Amazon-Google). For θ > 0.7, a small increase in the similarity threshold yields slightly lower performance with respect to all measures. The reason is that both data sets are challenging tasks, because they contain many corner cases, i.e., records that are close to the decision boundary.

Overall, we can conclude that D-HAT is robust with respect to its similarity threshold θ, with θ = 0.7 constituting a reliable default value.

Conclusions

We presented D-HAT, an efficient, fully automated clustering-based end-to-end deduplication system. D-HAT can process high dimensional data sets with heterogeneous attribute types and missing values without requiring user intervention or any labelled data. The thorough experimental study on benchmark data sets demonstrates that our system achieves high accuracy across different benchmark tasks, and outperforms supervised and unsupervised baselines. The main benefit of D-HAT over unsupervised methods is the high accuracy on all standard tasks, whereas compared to supervised methods, D-HAT eliminates the extra time and effort needed from domain experts to annotate a training set. It also saves the time required to find and train an efficient classification model. In the future, we plan to parallelize D-HAT on top of Apache Spark in order to scale it to huge data sets with millions of records.

  (iii) It achieves state-of-the-art results without requiring any labelled data. Our contributions are the following: -We propose D-HAT, an automated end-to-end, clustering-based framework for deduplicating high-dimensional data sets with heterogeneous attribute types and missing values. Its matching algorithm uses as features a comprehensive set of signals, coupling them with a novel greedy clustering method that defines as matches the records with mutually maximum matching scores. -We conduct experiments on established real benchmark data sets, showing that: (i) In terms of effectiveness, D-HAT outperforms the state-of-the-art supervised and unsupervised baseline methods. (ii) In terms of time efficiency, D-HAT has an undeniable advantage over the baseline methods. -We have publicly released all data and code used in our experiments through https://github.com/Loujainl/D-HAT.

Fig. 1 .

 1 Fig. 1. The end-to-end pipeline of D-HAT.

  |ri.a k -rj .a k | max(ri.a k ,rj .a k ) . 4. The normalized Manhattan similarity, V k i,j = |ri.a k -rj .a k | max(ri.a k ,rj .a k ) . • For textual attributes, the following functions are used: (i) Syntactic similarity measures. D-HAT distinguishes textual attributes into short strings, if their average value entails less than five words, and long strings otherwise. For both types, it employs the following functions: 1. Jaccard similarity: V k i,j = |token set(ri.a k )∩token set(rj .a k )| |token set(ri.a k )∪token set(rj .a k )| . 2. Generalized Jaccard, which extends the previous measure to consider the bags of tokens: V k i,j = |bag(ri.a k )∩bag(rj .a k )| |bag(ri.a k )∪bag(rj .a k )| . 3. Overlap Coefficient: V k i,j = |token set(ri.a k )∩token set(rj .a k )| min(|token set(ri.a k )|,|token set(rj .a k )|) . 4. Bag: V k i,j = 1 -max(|bag(ri.a k )-bag(rj .a k )|,|bag(rj .a k )-bag(ri.a k )|) max(|(rj .a k )|,|(ri.a k )|)|) 5. Dice Similarity: V k i,j = 2 × |token set(ri.a k )∩token set(rj .a k )| |token set(ri.a k )|+|token set(rj .a k )| . Additionally, D-HAT uses two similarity functions for short strings:

Fig. 2 .

 2 Fig. 2. The end-to-end algorithm of D-HAT.

Fig. 3 .

 3 Fig. 3. Run-time in seconds.

Fig. 4 .

 4 Fig. 4. Performance of D-HAT with syntactic features when varying the threshold θ.

Table 1 .

 1 Technical characteristics of the benchmark data sets. |S|, |T | and |D| stand for the number of source records, target records and duplicate pairs, respectively.

	Data set Amazon-Google 1,363 3,226 1,298 |S| |T | |D|	#Attributes #Numerical #Bool. & Cat. #Textual #Selected 4 1 0 2 3
	Abt-Buy	1,081 1,092 1,095	3	1	0	2	3
	DBLP-ACM	2,614 2,294 2,223	4	1	1	2	3
	Fodors-Zagats	533	331	112	5	0	0	5	5
	Immucare	305	310	305 213	32	6	37	75

Table 2 .

 2 Blocking performance. Time in Seconds.

	Data set	Key Attribute #Candidates Recall Prec Time
	Amazon-Google Name	131,214	0.995 0.010 7.3
	Abt-Buy	Name	164,072	0.994 0.007 2.6
	DBLP-ACM	Authors	318,404	0.993 0.007 19.4
	Fodors-Zagat	Phone	111	0.929 0.936 0.7
	Immucare	Date of Birth	311	1.000 0.981 26.5

Table 3 .

 3 Matching effectiveness of D-HAT, Magellan and ZeroER across all data sets. The best F1 per data set is underlined.

	Data set D-HAT								Magellan		ZeroER
		Syntactic Features Semantic Features Hybrid Features
		Pr	Re	F1	Pr	Re	F1	Pr	Re	F1	Pr	Re	F1	Pr	Re	F1
	A-G	0.904 0.479 0.626 0.828 0.349 0.534 0.925 0.532 0.675 0.513 0.573 0.542 0.663 0.385 0.487
	A-B	0.818 0.402 0.539 0.635 0.174 0.274 0.824 0.346 0.487 0.440 0.443 0.442 0.220 0.601 0.322
	D-A	0.992 0.956 0.974 0.995 0.980 0.987 0.997 0.974 0.985 0.980 0.983 0.981 0.936 0.945 0.940
	F-Z	0.981 0.929 0.954 0.971 0.911 0.940 0.981 0.929 0.954 0.939 0.969 0.954 1.000 0.312 0.476
	CA	0.993 0.987 0.990 0.990 0.987 0.988 0.993 0.987 0.990 0.968 1.000 0.984 1.000 0.487 0.655

Table 4 .

 4 The number of features per group.

	Data set Non-textual Syntactic Semantic Hybrid
	A-G	4	14	22	32
	A-B	4	14	22	32
	D-A	4	14	22	32
	F-Z	0	35	45	80
	CA	78	400	411	733

In the case of Record Linkage, we assume aligned schemata.