## 3 Approximate Record Matching in Similarity Space
### Survey of Current Token-Based Methods  
In our survey, we have identified the most-cited algorithms based on fuzzy set relatedness [44]. Hence, we refer to them as the current state of the art. We refer readers to the commonly used similarity functions, fuzzy dice similarity, fuzzy cosine similarity, and fuzzy Jaccard similarity [41; 42; 44]. Our record-matching method will be based on this class of algorithms.  
**Definition 3** (Fuzzy Token Similarity [41; 42]).: _Let us consider two sets of tokens, \(\mathcal{R}_{1}\) and \(\mathcal{R}_{2}\). Write \(\mathcal{R}_{1}\,\widetilde{\cap}_{\delta}\,\mathcal{R}_{2}\) for the fuzzy overlap of \(\mathcal{R}_{1}\) and \(\mathcal{R}_{2}\). The value \(\delta\) is the token level threshold in the internal similarity function, \(\mathrm{sim}^{\prime}(X_{i},Y_{j})\). The incident edge for the token pair is considered only if \(\mathrm{sim}^{\prime}(X_{i},Y_{j})\geq\delta\). We will define the following similarity functions: Fuzzy dice similarity, \(\mathrm{sim}_{D}(\mathcal{R}_{1},\mathcal{R}_{2})\),_  
\[\mathrm{sim}_{D}(\mathcal{R}_{1},\mathcal{R}_{2})=\frac{2|\mathcal{R}_{1}\, \widetilde{\cap}_{\delta}\,\mathcal{R}_{2}|}{|\mathcal{R}_{1}|+|\mathcal{R}_{ 2}|}.\] (5) Fuzzy cosine similarity, \(\mathrm{sim}_{C}(\mathcal{R}_{1},\mathcal{R}_{2})\),_  
\[\mathrm{sim}_{C}(\mathcal{R}_{1},\mathcal{R}_{2})=\frac{|\mathcal{R}_{1}\, \widetilde{\cap}_{\delta}\,\mathcal{R}_{2}|}{\sqrt{|\mathcal{R}_{1}|}\sqrt{| \mathcal{R}_{2}|}}.\] (6) Fuzzy Jaccard similarity, \(\mathrm{sim}_{J}(\mathcal{R}_{1},\mathcal{R}_{2})\),_  
\[\mathrm{sim}_{J}(\mathcal{R}_{1},\mathcal{R}_{2})=\frac{|\mathcal{R}_{1}\, \widetilde{\cap}_{\delta}\,\mathcal{R}_{2}|}{|\mathcal{R}_{2}|+|\mathcal{R}_{ 1}|-|\mathcal{R}_{1}\,\widetilde{\cap}_{\delta}\,\mathcal{R}_{2}|}.\] (7) Fuzzy overlap similarity, \(\mathrm{sim}_{O}(\mathcal{R}_{1},\mathcal{R}_{2})\),_  
\[\mathrm{sim}_{O}(\mathcal{R}_{1},\mathcal{R}_{2})=\frac{|\mathcal{R}_{1}\, \widetilde{\cap}_{\delta}\,\mathcal{R}_{2}|}{\mathrm{min}\{|\mathcal{R}_{1}|,|\mathcal{R}_{2}|\}}. \tag{8}\]  
_The relaxed term'similarity function' is used instead of 'normalized similarity metric' because, e.g., dice similarity is not a normalized similarity metric, as can be simply deduced from [45]._  
In the definition of fuzzy token similarity, we also add a fuzzy overlap compared to the original articles because we will continue to work with it. However, the previously introduced models have some disadvantages from our perspective:  
* _Second Threshold:_ The disadvantage is that we actually have two threshold parameters--the threshold \(\delta\) in the internal similarity function, \(\mathrm{sim}^{\prime}(X_{i},Y_{j})\), and the overall threshold, \(\alpha\), on \(\mathrm{sim}(\mathcal{R}_{1},\mathcal{R}_{2})\), with which we classify whether the records \(\mathcal{R}_{1}\) and \(\mathcal{R}_{2}\) are a match or not. The global threshold, \(\alpha\), can be quite different from the local threshold, \(\delta\). In addition, the threshold of the internal function, \(\delta\), requires optimization and can lead to reduced accuracy if selected incorrectly--see an example in Appendix A.2.  
* _Not Entirely Fuzzy:_ By applying a binary classifier, \(\text{sim}^{\prime}(X_{i},Y_{j})\geq\delta\), we can determine whether a token pair \((X_{i},Y_{j})\) is classified as a match. Such a strict classification on the token level leads to declining matches on tokens lower than the threshold \(\delta\) and does not respect human-natural continuous perception of the overall similarity, because the information about any similarity lower than \(\delta\) is replaced by a substitution value of zero.
* _Not a Similarity Metric:_ For the triangle inequalities given by (N2), respectively, (S2) is violated. This statement is supported by using the normalized Levenshtein similarity, which violates the triangle inequality, as further mentioned in the next sub-chapter. For details, see Appendix A.3.