## 3 Approximate Record Matching in Similarity Space
### Proposed Model of Fuzzy Record Similarity Metric (FRSM)  
The proposed model is based on maximum weight matching in a bipartite graph [40; 42; 44] that satisfies an axiom (S1) for the symmetry mentioned above. The exact optimal solution to the combinatorial assignment problem can be found using the Kuhn-Munkres algorithm [46; 47; 48]. A graph, \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), consists of a set, \(\mathcal{V}=\mathcal{R}_{1}\cup\mathcal{R}_{2}\), of vertices (the tokens of both records) and a set, \(\mathcal{E}\), of pairs of vertices, called edges. For an edge, \(e=(X_{i},Y_{j})\), we say that the endpoints of \(e\) are \(X_{i}\) and \(Y_{j}\); we say that \(e\) is incident to \(X_{i}\) and \(Y_{j}\). A graph, \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), is bipartite if the vertex set, \(V\), can be partitioned into two sets, \(\mathcal{R}_{1}\) and \(\mathcal{R}_{2}\) (the bipartition), such that \(\mathcal{R}_{1}\cap\mathcal{R}_{2}=\emptyset\) and no edge in \(\mathcal{E}\) has both endpoints in the same set of the bipartition. A matching \(\mathcal{M}\subseteq\mathcal{E}\) is a collection of edges such that every vertex is incident to at most one edge in \(\mathcal{M}\). If a vertex has no incident edge, it is referred to as exposed (or unmatched). A matching is perfect if no vertex is exposed; in other words, a matching is perfect if its cardinality is equal to \(|\mathcal{R}_{1}|=|\mathcal{R}_{2}|\). Theorem 4.1 (Konig): _For any bipartite graph, the largest possible matching is equal to the smallest possible vertex cover._  
This theorem is an expression of the equality of the primary and dual problem in linear programming. The Kuhn-Munkres algorithm is based on such dual tasks. Definition 4.1 (Maximum Weight Matching Problem): Given a weight, \(c_{i,j}\) for all \((i,j),\in\mathcal{E}\). Given a matching, let its incidence vector be \(\mathbf{x}\), where \(x_{i,j}=1\) if \((i,j)\in\mathcal{M}\), and \(0\) otherwise. One can formulate the maximum weight matching problem as follows: its objective function is  
\[\mathbf{x}^{\star}=\arg\max\sum_{i=1}^{|\mathcal{R}_{1}|}\sum_{j=1}^{|\mathcal{R}_ {2}|}c_{i,j}x_{i,j}=\arg\max c^{T}\mathbf{x}, \tag{9}\]  
subject to  
\[\sum_{i=1}^{|\mathcal{R}_{1}|}x_{i,j}=1, \tag{10}\]  
\[\sum_{j=1}^{|\mathcal{R}_{2}|}x_{i,j}=1. \tag{11}\]  
In general graphs, the minimum vertex cover problem is \(NP\)-complete; meanwhile, in bipartite graphs, this problem belongs to the class \(N\). The maximum weight matching problem has a polynomial time complexity of \(\mathcal{O}(|\mathcal{V}|^{4})\), but it has been shown that it can be modified to achieve a running time of \(\mathcal{O}(|\mathcal{V}|^{3})\). Note that the best-known time complexity for the maximum weighted matching is \(\mathcal{O}(|\mathcal{V}||\mathcal{E}|+|\mathcal{V}|^{2}\log|\mathcal{V}|)\)[49; 50]. For the calculation of textual similarity, we use the normalized edit similarity metric in the range \([0,1]\), as defined in Theorem (5):  
\[c_{i,j}=s_{n}(X_{i},Y_{j}). \tag{12}\]  
Let us mention that several normalization factors have been developed [23; 24; 25], and most of them violate the triangle inequality as a condition of being a similarity metric. However, in [24], there is a normalized similarity metric, and this has been further generalized into a similarity space [43]. On the other hand, it also has been found that such normalization factors do not affect accuracy, with fluctuations in the test results of \(\approx 1\%\). This accuracy could be considered to be a statistically acceptable error.