## 5 Results
### Experiment Setup and Evaluation Q-Gram Filter Efficiency  
In this section, we present the results of an extensive set of experiments conducted to demonstrate the efficiency of the proposed mathematical models for Q-gram filtering and approximate record-weighted matching in a bipartite graph. The quality of the measurement data can be checked by finding matches in a database created from other sources. We used a test suite that has been reported in various papers and is widely used to analyze these metrics [4; 15]. In the dataset, we compared pairs of inputs that belonged to the same domain, and if their IDs matched, then we marked them as identical. Our test involved comparing datasets taken from [15], shown in Table 2. In the test, each dataset was divided into two parts. Between these two parts, we calculated the scores between all pairs of records. We sorted all the pairs according to the calculated similarity scores. Ideally, all matches should have a higher similarity score and, as a result, should appear in the sorted list before all mismatches. We computed the _non-interpolated average precision_ of this ranking. According to the papers [4; 15], we calculate the precision and recall as:  
\[\text{Precision} =\frac{c(i)}{i}\, \tag{66}\] \[\text{Recall} =\frac{c(i)}{\mathcal{P}}\, \tag{67}\]  
where \(c(i)\) is the number of correct matching pairs ranked before position \(i\), and \(\mathcal{P}\) is total number of correct matches. Consequently, _interpolated precision_ at recall, \(r\), is the \(\max_{i}\frac{c(i)}{i}\), where the \(\max\) is taken over all ranks, \(i\), such that \(\frac{c(i)}{\mathcal{P}}\geq r\). The graphs in Figures 7-9 are plotted from the interpolated precision in the recall sequence \(r=0.0\), \(0.05\),..., \(0.95\), and \(1.0\) (\(21\) equidistant recall levels), with a step length of \(0.05\). The curves go through the points and are smoothed for better clarity. The overall relative performance of the compared similarity functions is calculated using the maximum F1-score as follows:  
\[\text{F1-score}=2\frac{(\text{Precision}\times\text{Recall})}{\text{Precision}+ \text{Recall}}, \tag{68}\]  
This is shown in Tables 3 and 4. The table shows that the best results of \(85.09\%\) were achieved using the FRMS method and its combination with the Q-gram filter at \(85.01\%\) \begin{table}
\begin{tabular}{l r l r} \hline \hline
**Name** & **Number of Strings** & **Name** & **Number of Strings** \\ \hline Animal & 5709 & Game & 911 \\ Bird Kunkel & 336 & Park & 654 \\ Bird Nybird & 982 & Restaurant & 863 \\ Bird Scott1 & 38 & Ucd-people & 90 \\ Bird Scott2 & 719 & Census & 841 \\ Business & 2139 & & \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Datasets used in experiments from original sources [15]. Figure 6: Block diagram of the processing of records from the source in real-time by a two-stage system of Q-gram filter and FRMS. Based on these results, we can say that such results confirm the high accuracy of the approximated optimal Q-gram filter and verify the correctness of our mathematical derivation of its approximate form. However, it should be noted that, although it is still an approximation, there are several records for which we found, upon detailed analysis, that they did not pass through the filter. We performed a complete ablation study for combinations of our derived Q-gram filters with padding (Theorem 10 and Corollary 11) and naive Q-gram filter with padding (Corollary 10) along with FRMS. See Table 4. Padding \(|p|=2\) indicates that a single prefix and postfix character was used, \(|p|=1\) indicates that only a prefix character was used, and \(|p|=0\) indicates that no padding was applied. The experiments evaluated whether each compared pair of matches passes the filter at a fixed threshold, \(\alpha\), corresponding to the final similarity score of the FRMS method, i.e., a filter threshold of \(\alpha=s_{n}(\mathcal{R}_{1},\mathcal{R}_{2})\). The thresholding parameter \(\alpha\) was only reduced by 0.01 as an error tolerance.