## 4 Optimal Q-Gram Filter
### Count Filtering  
The intuition behind count filtering is that strings with greater edit similarity than a threshold of \(s_{n}\geq\alpha\) have a large number of Q-grams in common, based on Theorem 4.1 and Corollaries 3 and 4.2. At the beginning of this chapter, we introduce the concept of Q-gram similarity lying in similarity space. Definition 7 (Q-gram Similarity): Let \(\Sigma\) be a finite alphabet, and let \(\Sigma^{*}\) denote the set of all strings over \(\Sigma\). The function \(s_{q}\colon\Sigma^{*}\times\Sigma^{*}\to\mathbb{N}_{0}\) is the Q-gram similarity function for the strings \(X\) and \(Y\):  
\[s_{q}(X,Y)=|Q_{X}\cap Q_{Y}|, \tag{23}\]  
where \(Q_{X}\) and \(Q_{Y}\) are the corresponding \(Q\)-gram sets. Corollary 2: \(Q\)_-gram similarity, \(s_{q}(X,Y)\), is a similarity metric._  
Proof: It has been already shown in [43] that a set intersection is a elementary similarity metric satisfying (S1), (S2), (S3), and (S4) from Definition 1. 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 \(|X|\) and a text string, \(Y\), with length \(|Y|\). Then, the following theorem is given in [53]:  
Theorem 4.2 (Q-gram Count Filtering): _Let consider two strings, \(X\) and \(Y\), and the edit distance \(d(X,Y)\). Then, the Q-gram similarity, \(s_{q}(X,Y)\), between \(X\) and \(Y\) is bounded below by_  
\[t=\max\{|X|,|Y|\}-q+1-qd(X,Y), \tag{24}\]  
_where \(t\) is a Q-gram similarity threshold with respect to \(d(X,Y)\)._Proof. : [52]. 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. **Corollary 3** (Infimum of Q-gram for Edit Distance). : _Let \(d\in[0,d_{max}]\) be an edit distance. Then, there exists a lower bound_  
\[\inf_{d}\{|Q_{X}\cap Q_{Y}|\}=\max\{|X|,|Y|\}-q+1-q\min\{d_{sing},d_{max}\}. \tag{25}\]  
Proof. : \(\inf_{d}\{|Q_{X}\cap Q_{Y}|\}=\inf_{d=d_{max}}\{|Q_{X}\cap Q_{Y}|\}\); the term \(\min\{d_{sing},d_{max}\}\) treats the filter underflow below 0. **Corollary 4** (Supremum of Q-gram for Edit Distance). : _Suppose we are given an edit distance, \(d\in[0,d_{max}]\). Then, there exists an upper bound_  
\[\sup_{d}\{|Q_{X}\cap Q_{Y}|\}=\max\{|X|,|Y|\}-q+1. \tag{26}\]  
Proof. : Similarly, we obtain an upper bound by maximizing \(|Q_{X}\cap Q_{Y}|\) and use \(d=0\); hence, \(\sup_{d}\{|Q_{X}\cap Q_{Y}|\}=\sup_{d=0}\{|Q_{X}\cap Q_{Y}|\}\). 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}\{|Q_{X}\cap Q_{Y}|\}\). **Definition 8** (Q-gram Singularity). : _We say there is a Q-gram singularity if no common Q-gram is guaranteed; so, Q-gram filtering has no effect and_  
\[t=\inf_{d}\{|Q_{X}\cap Q_{Y}|\}\leq 0. \tag{27}\]  
**Corollary 5** (Length Singularity of Q-gram Filter). : _Let \(|X|_{sing}\) be the string length where \(t=0\) for an edit distance, \(d(X,Y)>0\).