Real-Time Fuzzy Record-Matching Similarity Metric and Optimal Q-Gram Filter

The large group of phonetic algorithms includes Soundex [5], Metaphone [6], Double Methaphone [7], Phonex [8], Phonix [9], NYSIIS [10], and Fuzzy Soundex [11]. These algorithms are characterized by a strong linguistic/phonetic dependence (usually English), which leads to poor F measures [12], poor robustness against misspelling and typographical errors, and a lack of assumptions of tokens. Due to their language specificity, they cannot be used well on multiple-language data sources. However, they are still implemented in many databases and software applications used by leading software companies. In our experience with IT companies, we have frequently encountered a misunderstanding of the use of such algorithms in datasets comprising various languages for which they are not intended.

The basic ideas of heuristics are based on linear programming, local searching, and transformations to a linear sum assignment problem with error correction. The choice of the edit distance metric varies depending on the particular heuristic applied. Jaro distance [13] and its modification, Jaro–Winkler distance [14], are well-known representatives that are very often used in the commercial sector for their simple implementation and high F measures [2,12,15]. They are appropriate only for short strings, e.g., names, and do not make assumptions with respect to tokens, as they are sensitive to any disorder in the sequence of tokens.

The edit distance between two strings represents the minimum cost required to perform a series of edit operations to convert one string into the other. Each operation has an associated cost, often 1. Well-known algorithms based on dynamic programming include the Hamming–Levenshtein [16] and Damerau–Levenshtein [17,18] algorithms for DNA or protein sequence comparison; these follow the methods proposed by Needleman and Wunsch [19], Smith and Waterman [20], Gotoh [21], and others. The learning cost associated with distance in supervised machine learning for specific transitions is also worth mentioning [22]. Unfortunately, these standard similarity metrics are not practically usable for a bag-of-words model, where permutations of words should also be involved. The other issue is normalization, e.g., the Levenshtein distance is a measure of the absolute edit distance between terms and is not practically usable due to the bias of such metrics against words with different lengths. Normalization factors that normalize the Levenshtein distance to lie within a range of $[0,1]$ have been proposed [23,24,25] . However, some factors violate the axioms of the similarity metric, especially triangle inequality.

Q-grams (also called ‘n-grams’; see [26]) are short character sub-strings (of length q) of the record strings [27]. These methods have been applied in various forms, such as through the application of different approaches to spelling correction or the use of inverted indexes [28,29,30]. The Q-gram method is a favorite indexing method in enterprise and web search engines; it is used by tech companies with the largest market shares and capitalization. A comparison with other similarities yields quite good results; however, token-based algorithms outperform this method [12]. We explain this by the fact that Q-grams do not treat natural language encoding based on words; rather, they split the tokens into ‘artificial’ sub-strings, ignoring the information about which token generated the Q-gram. This concept achieves good results, with robustness to any disorder in the token sequence, but it comes at the cost of its overall accuracy. For this reason, such methods serve as a preprocessing step for more accurate approximate string-matching algorithms.

An example of a string-matching approach is demonstrated by [31], who introduce a software library for fuzzy string matching and candidate ranking. Their method incorporates support for various deep neural network architectures, enabling both the training of new classifiers and the fine-tuning of existing models. This paper presents their approach to building the library and tuning the training dataset. They also compare the results with existing systems such as [32], which, however, relies on lookup tables. They compare their results with [33], who bring an approach called toponym matching, which is used, for example, in matching paired texts that represent the same real locations and are therefore often used in the geosciences. The authors of [33] use the approach of gated recurrent units [34], a recurrent neural network used in modeling sequence data. An example is a representation of a sequence of bytes corresponding to texts with which they have something in common. Their approach uses the deep neural network architecture proposed by [35], where the parameters are learned from the training data. The whole model can then be trained end-to-end using a back-propagation algorithm following an optimization method proposed by [36], which is called Adam. The paper then shows results on a large dataset collected by the GeoNames gazetter from www.geonames.org.

Another perspective is presented by [37], who explore ontology matching using deep neural networks. They emphasize that some methods overlook higher-level correlations between different descriptions of the entities being evaluated. To address this, ref. [37] propose learning-based methods that account for such correlations. Ontology matching, as described in their study, involves measuring the similarity between two entities from distinct ontologies, where a pair of entities with high similarities is referred to as a mapping. Establishing such mappings is crucial for ensuring correct data exchange between ontology-based applications; yet, it is a challenging task due to the complexity of modern ontologies. By employing a deep learning model, their approach generates high-level abstract representations of the original data. This methodology is used to address the semantic heterogeneity problem, focusing on identifying semantically similar entities across different ontologies.

In structured documents, there is implicit information from the context, given by columns as a semantic topic. Each attribute is modeled using a bag-of-words model, where the context is very often not relevant in traditional databases and NoSQL storage. The previously mentioned methods are based on the comparison of characters in the complete string. A hybrid similarity method converts the string into a set of tokens, the so-called bag-of-words model. A string can be transformed into sets by splitting using a delimiter. This allows us to take the semantic meaning of the words into account and process large texts. The comparison has two levels: a character-level comparison for each pair of tokens and a token-level comparison of all possible pairs of tokens. The similarity calculation is usually based on the Jaccard index or the Sorensen–Dice formulae. For the token set, comparisons such as Monge–Elkan [38,39] or SofTFIDF [15] are used. Unfortunately, these methods perform an approximate combinatorial assignment, and hence yield an asymmetric matching, see Appendix A.1. Maximum matching on bipartite graph [40,41,42] is more suitable for practical use and achieves the best F-measures due to its solving the optimal assignment problem and the symmetricity of their measurements. The significant advantage of these methods is that they preserve the encoding of natural language, particularly in terms of token resolution, treating words as distinct units of meaning. We find that this group of models deserves the most attention in research for its promising results.

Unfortunately, those algorithms often have a quadratic time complexity, $\mathcal{O}\left(n^2\right)$, or even a cubic time complexity, $\mathcal{O}\left(n^3\right)$, or worse, $\mathcal{O}\left(n^4\right)$; this is especially the case for those providing the best recall/precision results on research datasets.

We assume the given normalized similarity metric, $s_n({\mathcal{R}}_1,{\mathcal{R}}_2)$, which measures the similarity between two records, ${\mathcal{R}}_1$ and ${\mathcal{R}}_2$, as a real number in the interval $[0,1]$, with 1 representing complete similarity and 0 representing complete dissimilarity. Consider a fixed $\alpha$, $0<\alpha <1$. The applications distinguish relevant records by a binary classifier into two classes: the set of matches ($\mathcal{M}$) and the set of non-matches ($\mathcal{N}$), consisting of ordered pairs of records $({\mathcal{R}}_1,{\mathcal{R}}_2)$. More formally,

The decision of where to set the match/non-match threshold, $\alpha$, is a balancing act. The threshold should be chosen based on an acceptable sensitivity (or recall, which is the proportion of truly matching records that are correctly linked by the algorithm) and positive predictive value (or precision, which is the proportion of records linked by the algorithm that are indeed true matches). The task is to find an algorithm that classifies the sets of matches and non-matches as accurately as possible, corresponding to reality as judged by human observation. In the scientific literature, we also encounter the terms record linkage, data matching, fuzzy matching, entity resolution, etc.

In information retrieval theory and search engines, we can analogically meet with the phrase ‘retrieving relevant documents’. A record can be transformed into tokens of words. That is, each record is split into a set of tokens, $\{X_1$, …, $X_j$, …, $X_n\}\in {\mathcal{R}}_1$. We denote the size of a record, ${\mathcal{R}}_1$, by $|{\mathcal{R}}_1|$, which is the number of tokens in ${\mathcal{R}}_1$.

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.

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:

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=\varnothing$ 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|$.

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.

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}\left(\right|\mathcal{V}{|}^4)$, but it has been shown that it can be modified to achieve a running time of $\mathcal{O}\left(\right|\mathcal{V}{|}^3)$. Note that the best-known time complexity for the maximum weighted matching is $\mathcal{O}\left(\right|\mathcal{V}\left|\right|\mathcal{E}|+|\mathcal{V}{|}^{2}log\left|\mathcal{V}\right|)$ [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):

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.

We now introduce a normalization of $d(X_i,Y_j)$ differences (generally called the edit distance) for Levenshtein similarity in the interval $[0,1]$, which is one of the most used in [4,12,30,42]:

It can be easily shown, for example, Appendix A.3, that this normalization also violates the triangle inequality; therefore, all the distances or similarity functions introduced in the articles based on this normalization are not metrics and cannot be used well in applications like cluster analysis.

Now, consider a scenario in which we want to predict the edit distance based on knowing only the lengths of the strings X and Y. The calculation of the edit distance, $d(X,Y)$, itself is computationally expensive, in quadratic time it is $\mathcal{O}\left(\right|X\left|\right|Y\left|\right)$, so we would like to obtain at least a rough estimate of the worst case of the expected edit distance for the minimum edit normalized similarity, given by the threshold $s_n(X,Y)\ge \alpha$. We introduce an expected edit distance, ${sup}_{\alpha }d(X,Y)=d(\alpha ,|X|,|Y\left|\right)$, depending on already-known parameters—the threshold $\alpha$ and the lengths of the strings $\left|X\right|$ and $\left|Y\right|$. Finally, we obtain a prediction which is computationally feasible in constant time, $\mathcal{O}\left(1\right)$, and will help in developing an optimal filter in further chapters.

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 Figure 1 and Figure 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. However, in large storage situations with millions of records, such time complexity in the algorithm is not usable for real-time approximate string matching and search. A filter, also called a blocking technique, could be developed using a method with much lower time complexity; this could thus filter many records and significantly reduce the large comparison space [28,29,30]. Practically all used methods are sub-optimal filters which, during filtering, lose true-positive candidates. The reason that we observe for this is that these methods are not explicitly mathematically united. The intention of this article is to show, in general, that it is possible to derive an optimal filter that is less time-consuming and serves as the lower bound of the threshold related to a more time-consuming algorithm of approximate string matching. In our case, we propose a two-stage method, where a less time-consuming filter, such as a Q-gram filter, could be used for our proposed token-based model, FRMS, with polynomial time complexity. The Q-gram filter is also one of the most-used indexing methods for search engines in real-world applications. Thresholding by least-shared Q-grams is known as T-overlap similarity join [30]. In the next chapters, we will describe a new optimal Q-gram filter for FRMS, the purpose of which is to solve the T-overlap similarity join problem.

The intuition behind count filtering is that strings with greater edit similarity than a threshold of $s_n\ge \alpha$ have a large number of Q-grams in common, based on Theorem 8 and Corollaries 3 and 9.

At the beginning of this chapter, we introduce the concept of Q-gram similarity lying in similarity space.

By dividing by $|Q_X\cup Q_Y|$, we obtain a normalized similarity metric called the Jaccard metric [43]. For further derivation, we consider only a simple intersection as a measurement of the Q-grams common to X and Y.

In [52], a relation is proposed between the edit distance and the Q-gram method. Suppose we are given a pattern string, X, with length $\left|X\right|$ and a text string, Y, with length $\left|Y\right|$. Then, the following theorem is given in [53]:

This observation is critical for a class of algorithms that target string similarity search and similarity joins based on edit distance constraints, with numerous practical applications in data cleaning, search engines, and integration. These algorithms extend traditional exact search-and-join operations in databases by allowing for errors and inconsistencies in the data—see [30].

One of the common problems is to find the threshold of the least-sharing Q-grams for an allowed edit distance with a fixed maximum distance, $d_{max}$, which can be set as a parameter by the user. Denote by $d\in [0,d_{max}]$ an interval range of allowed edit distance. A singularity of a Q-gram filter, $d_{sing}$, occurs whenever this lower bound is less than or equal to zero, as will be explained further on.

In our definition, for the first time, we introduced an expression using infimum and supremum on the Q-gram set in relation to the edit distance, d. A similar kind of equation is also introduced in [52,53]. For simplicity, from now on, we write the threshold as $t={inf}_d\left\{\right|Q_X\cap Q_Y\left|\right\}$.

There is an example in Figure 3. The underlined letter indicates the position that is the worst in the calculation, as there is no trigram without that letter.

The normalization of the edit distance has received less attention in many scientific articles, but we find it to have great importance for many real-world applications that need to measure normalized similarity independently of the length of the string. The edit distance, $d=1$, on a string with a length of $\left|X\right|=24$ is very often totally different from that of a string, Y, with a length of, e.g., $\left|Y\right|=6$. The normalization factor that this brings is related well to the human perception of the similarity of different objects. From similarity space theory, the strings could often have different self-similarities. Self-similarity could be a measure of the number of extracted Q-grams or string lengths. For instance, having German words $X=$ ‘Einkommensteuererklärung’ (income tax return) and $Y=$ ‘Steuer’ (tax), we have $s(X,X)\ge s(Y,Y)$ when counting string lengths, common characters, or Q-grams. Whenever we compare two objects with different feature sizes, we ask the following question: Are these objects also of different importance? In our model, we say no; hence, we obtain the following argument for normalization among strings.

Similar to the previous (3), we reformulate our normalized least-sharing Q-gram pairs as a threshold similarity, as follows: where we substitute for the edit distance the worst case scenario with $d(X,Y)=d(\alpha ,|X|,|Y\left|\right))$, and we use this case later in this paper.

The occurrence of a singularity of the Q-gram filter, $t_{\alpha }$, depends on the string lengths $\left|X\right|$ and $\left|Y\right|$ and the user-chosen threshold parameter, $\alpha \in [0,1]$.

Simply explained, a Q-gram filter can work efficiently if $d(X,Y)\le d_{sing}(\alpha ,|X|,|Y\left|\right)$. If equality holds, then all Q-grams could be destroyed, as the worst case scenario.

In other words, we should always select a threshold, $\alpha \ge {\alpha }_{sing}$, for the corresponding token lengths, to have a working and efficient Q-gram filter that is capable of filtering any dissimilar records.

Indeed, for $d=1$ and $\alpha =0.8$, we obtain $\left|X\right|=5$. Shorter strings must always have $s_n(X,Y)<\alpha$ for $d>0$.

A singularity of a Q-gram filter could cause performance problems on certain string lengths, ${\left|X\right|}_{sing}$, due to generating a large candidate set. This property is demonstrated in Figure 4. To resolve this kind of problem, we should extend our model with at least 1 padding Q-gram, denoted by $p\in {\Sigma }^{\ast }$. From nature, empirical observation, and some blocking techniques [28,29,30], increasing the importance of initial letters seems reasonable. For an initial solution, we could define a prefix or postfix ‘$p=\#$’, or both of them for each token, and extend the Q-gram sets by about $|Q_X|+|p|$ Q-grams.

The behavior of the Q-gram filters near the singularity points plays a fundamental role in their theoretical and practical performance. While empirical studies across diverse datasets have demonstrated that padding Q-grams consistently improves F-measure statistics [55,56], prior work has lacked a rigorous theoretical framework explaining this phenomenon. We propose that the singularity behavior of Q-gram filters provides the theoretical foundation for these empirical observations. Specifically, we show that padding characters serve two complementary functions: First, they ensure non-zero Q-gram similarity at singularity points by introducing guaranteed common sub-strings at token boundaries. Second, they expand the feature space dimensionality through additional Q-grams generated from the padding–token boundary regions. This dual effect creates what we term a “smooth Q-gram set”—one where similarity measures transition continuously across token boundaries rather than exhibiting sharp discontinuities. The additional discriminative power provided by the extended feature space enables more robust classification, particularly in boundary cases where the base Q-gram filter approaches singularity.

Another solution could be to combine feature extraction with multiple sizes of the Q-grams, e.g., unigrams, bigrams, and trigrams. The singularities of those Q-gram filters would be mutually resolved. A generalization of such a combination could be expressed as a sum of shared Q-grams over different Q-gram sizes, $t_1$, $t_2$, and $t_3$, and their constants, $q_1=1$, $q_2=2$, and $q_3=3$. and evaluating

In this generalization, we consider the records ${\mathcal{R}}_1,{\mathcal{R}}_2$, consisting of token sets that are matched in a bipartite graph. As mentioned previously, $\left|\mathcal{M}\right|$ is the resulting maximum edge-connected pair token for the optimal combinatorial assignment problem. We assume that the only known factors are the matching token pairs given by $\mathcal{M}$, with unknown edit distances, but we can predict them in accordance with the expected edit distances. It can be very confusing that the edit distances are unknown while this model assumes a known matching $\mathcal{M}$, which is calculated on the adjacency matrix. Building such a model has a quite tricky reason, which we may express as a model depending on threshold $\alpha$ and token lengths of $X_i\in {\mathcal{R}}_1$ and $Y_j\in {\mathcal{R}}_2$. We formulate this generalization in the following.

For the sake of exposition, we explain two terms of the optimal Q-gram filter equation. The term maximum shared Q-grams counts the maximum possible number of shared Q-grams, $|Q_{{\mathcal{R}}_1}\cap Q_{{\mathcal{R}}_2}|$, that could be achieved with tokens with corresponding lengths, $|X_i|,|Y_j|$, given by the resulting matching set of $\mathcal{M}$ on the complete bipartite graph. In fact, this term is simple because it counts only the Q-grams across matching token pairs $|X_i|$ and $|Y_j|$. The most crucial term is the loss function, which must be maximized for an unknown expected distance distribution of the tokens employing a user-defined global threshold, $\alpha$. Table 1 (bottom) contains a complete list of the constraints previously imposed on the integer linear programming problem as well as the fuzzy token similarity functions that have been introduced. Note that, in previous publications, this task was simplified: there was no consideration of the dependence of $t_{\mathcal{M}}$ on variables such as the length of the Q-gram q and the lengths of the tokens $|X_i|$$|Y_j|$. The derived model solves it for optimality and cannot be further improved.

A naive approximation would be to assume the constancy of ${\alpha }_{i,j}=\alpha$, which actually performs an average distance allocation among the tokens. This is the approximation of the optimal lower bound Q-gram pairs for maximum weight matching in a bipartite graph. We note the fact that $X_i$ and $Y_i$ are connected by a resulting edge. However, we can not predict which tokens will be matched on the bipartite graph, and so cannot predict their lengths.