## 3 Approximate Record Matching in Similarity Space
### Proposed Model of Fuzzy Record Similarity Metric (FRSM)
: _Let the worst-case expected edit distance be \(d(\alpha,|X|,|Y|)\colon\mathbb{R}\times\mathbb{N}^{+}\times\mathbb{N}^{+} \rightarrow\mathbb{N}_{0}\), representing the maximal possible edit distance, \(d(X,Y)\colon\Sigma^{*}\times\Sigma^{*}\rightarrow\mathbb{N}_{0}\), for string lengths \(|X|\) and \(|Y|\), with a similarity determined by a fixed \(\alpha\in[0,1]\)._  
**Theorem 6** (Threshold of Normalized Edit Similarity Metric). : _Let us consider an edit distance of \(d(X,Y)\). The worst case of the expected distance function is \(d(\alpha,|X|,|Y|)\). Then,_  
\[\sum_{i=1}^{|\mathcal{R}_{1}|}x_{i,j}=1, \tag{10}\]0  
_where \(\alpha\in[0,1]\subset\mathbb{R}\) is a threshold of the normalized similarity metric given by inequality \(s_{n}(X,Y)\geq\alpha\). We use symbol \(\lfloor\cdot\rfloor\) for the floor function._  
Proof. : According to Theorem 3 and by substituting the self-similarities, which are equal to the corresponding cardinalities of the sets, \(s(X,X)=|X|\) and \(s(Y,Y)=|Y|\), the expected distance \(d(\alpha,|X|,|Y|)\) reaches its maximum when the similarity is at its minimum, corresponding to the lowest similarity given by the threshold \(\alpha\). This occurs if--and only if--we substitute \(s_{n}(X,Y)=\alpha\)  
\[ \begin{split} d(X,Y)&=\left\lfloor d_{R}\right\rfloor =\left\lfloor\frac{1-s_{n}(X,Y)}{1+s_{n}(X,Y)}(s(X,X)+s(Y,Y))\right\rfloor\\ &\leq\sup_{\alpha}d(X,Y)=\left\lfloor\frac{1-\alpha}{1+\alpha}(| X|+|Y|)\right\rfloor=d(\alpha,|X|,|Y|).\end{split}  \tag{19}\]  
The edit distance is an integer, so we apply the floor function to eliminate any undefined fractional part. **Definition 6** (Fuzzy Record Similarity Metric--FRMS). : _Let \(\mathcal{M}\) be a matching collection of edges connecting pairs of tokens, and the cardinality be \(|\mathcal{M}|=\min\{|\mathcal{R}_{1}|,|\mathcal{R}_{2}|\}\); this is especially true for cases of imperfect matching, \(|\mathcal{R}_{1}|\
eq|\mathcal{R}_{2}|\). We define an expected value of the similarity metric as an average of the normalized edit similarity metrics between \(\mathcal{R}_{1}\) and \(\mathcal{R}_{2}\), as follows:_  
\[\mathbb{E}[s_{n}(\mathcal{R}_{1},\mathcal{R}_{2})]=s_{n}(\mathcal{R}_{1}, \mathcal{R}_{2})=\frac{\sum_{(i,j)\in M}s_{n}(X_{i},Y_{j})}{|\mathcal{M}|}. \tag{20}\]  
**Theorem 7**. : _The Fuzzy Record Similarity Metric (FRMS) is a normalized similarity metric._  
Proof. : FRMS satisfies (N1) because the maximum weight matching in a bipartite graph is a symmetric measure. We continue from Definition 6, applying Theorem 5 and convex combinations in Theorem 1; then, the remaining axioms are easily proven. **Corollary 1** (Identity FRMS and Fuzzy Overlap Similarity). : _The Fuzzy Record Similarity Metric equals the fuzzy overlap similarity if--and only if--\(\delta=0\):_  
\[s_{n}(\mathcal{R}_{1},\mathcal{R}_{2})=sim_{O}(\mathcal{R}_{1},\mathcal{R}_{ 2}). \tag{21}\]  
Proof. : We can express directly  
\[s_{n}(\mathcal{R}_{1},\mathcal{R}_{2}) =\frac{\sum_{(i,j)\in M}s_{n}(X_{i},Y_{j})}{|\mathcal{M}|}=\frac{ \sum_{(j,i)\in M}s_{n}(X_{i},Y_{j})}{\min\{|\mathcal{R}_{1}|/|\mathcal{R}_{2} |\}}=\frac{|\mathcal{R}_{1}\cap_{i=0}\mathcal{R}_{2}|}{\min\{|\mathcal{R}_{1}| /|\mathcal{R}_{2}|\}}=\text{sim}_{O}(\mathcal{R}_{1},\mathcal{R}_{2}). \tag{22}\]  
whenever we remove a second threshold by setting \(\delta=0\). Then, we obtain a complete bipartite graph; therefore, \(\sum_{(i,j)\in M}s_{n}(X_{i},Y_{j})=|\mathcal{R}_{1}\cap_{j=0}\mathcal{R}_{2}|\). In contrast with the fuzzy Jaccard similarity from Definition 3, we offer a well-designed generalized similarity metric that is suitable for text mining and cluster analysis as the first introduced advanced fuzzy record similarity technique. Graphically, the whole procedure is shown in Figures 1 and 2 and the enumerated example is shown in Appendix A.2. For the time complexity, note that, in most cases in large databases, each attribute stores short strings with few tokens; hence, the computation is feasible and fast in many real-world scenarios.