# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 2 Preliminaries
### Sequential Pattern Mining
#### 2.1.1 Frequent Sequential Pattern Mining  
Given a dataset \(\mathcal{D}\) and a _minimum frequency threshold_\(\theta\in(0,1]\), _frequent sequential pattern_ (FSP) mining is the task of reporting the set \(FSP(\mathcal{D},\theta)\) of all the sequences whose frequency in \(\mathcal{D}\) is at least \(\theta\), and their frequencies:  
\[FSP(\mathcal{D},\theta)=\{(p,f_{\mathcal{D}}(p)):p\in\mathbb{U},f_{\mathcal{D }}(p)\geq\theta\}. \tag{3}\]  
In the first part of this work, we are interested in finding the set \(FSP(\mathcal{D},\theta)\) by only mining a sample of the dataset \(\mathcal{D}\). Note that given a sample of the dataset \(\mathcal{D}\), one cannot guarantee to find the exact set \(FSP(\mathcal{D},\theta)\) and has to resort to approximations of \(FSP(\mathcal{D},\theta)\). Thus, we are interested in finding rigorous approximations of \(FSP(\mathcal{D},\theta)\). In particular, we consider the approximation of \(FSP(\mathcal{D},\theta)\) defined in Reference [8].  
**Definition 1**.: _Given \(\varepsilon\in(0,1)\), an \(\varepsilon\)-approximation \(\mathcal{C}\) of \(FSP(\mathcal{D},\theta)\) is defined as a set of pairs \((p,f_{p})\):_  
\[\mathcal{C}=\{(p,f_{p}):p\in\mathbb{U},f_{p}\in[0,1]\} \tag{4}\]  
_that has the following properties:_  
* \(\mathcal{C}\) _contains a pair_ \((p,f_{p})\) _for every_ \((p,f_{\mathcal{D}}(p))\in FSP(\mathcal{D},\theta)\)_;_
* \(\mathcal{C}\) _contains no pair_ \((p,f_{p})\) _such that_ \(f_{\mathcal{D}}(p)<\theta-\varepsilon\)_;_
* _for every_ \((p,f_{p})\in\mathcal{C}\)_, it holds_ \(|f_{\mathcal{D}}(p)-f_{p}|\leq\varepsilon/2\)_._  
(Note that while Reference [8] introduced the definition of \(\varepsilon\)-approximation of \(FSP(\mathcal{D},\theta)\), it did not provide a sampling algorithm to find such approximation for a given \(\varepsilon\in(0,1)\).)  
Intuitively, the approximation \(\mathcal{C}\) contains all the frequent sequential patterns that are in \(FSP(\mathcal{D},\theta)\) (i.e., there are no _false negatives_) and no sequential pattern that has frequency in \(\mathcal{D}\) much below \(\theta\). In addition, \(\mathcal{C}\) provides a good approximation of the actual frequency of the sequential pattern in \(\mathcal{D}\), within an error \(\varepsilon/2\), arbitrarily small.  
Depending on the application, one may be interested in a different approximation of \(FSP(\mathcal{D},\theta)\), where all the sequential patterns in the approximation are frequent sequential patterns in the whole dataset.  
**Definition 2**.: _Given \(\varepsilon\in(0,1)\), a false positives free (FPF) \(\varepsilon\)-approximation \(\mathcal{F}\) of \(FSP(\mathcal{D},\theta)\) is defined as a set of pairs \((p,f_{p})\):_  
\[\mathcal{F}=\{(p,f_{p}):p\in\mathbb{U},f_{p}\in[0,1]\} \tag{5}\]  
_that has the following properties:_  
* \(\mathcal{F}\) _contains no pair_ \((p,f_{p})\) _such that_ \(f_{\mathcal{D}}(p)<\theta\)_;_
* \(\mathcal{F}\) _contains all the pairs_ \((p,f_{p})\) _such that_ \(f_{\mathcal{D}}(p)\geq\theta+\varepsilon\)_;_
* _for every_ \((p,f_{p})\in\mathcal{F}\)_, it holds_ \(|f_{\mathcal{D}}(p)-f_{p}|\leq\varepsilon/2\)_._  
The approximation \(\mathcal{F}\) does not contain _false positives_, that is, sequences with \(f_{\mathcal{D}}(p)<\theta\). In addition, it does not miss sequences with \(f_{\mathcal{D}}(p)\geq\theta+\varepsilon\) and, similarly to the \(\varepsilon\)-approximation, we have that, for every pair in \(\mathcal{F}\), it gives a good approximation of the actual frequency of the sequential patterns in \(\mathcal{D}\), within an error \(\varepsilon/2\), arbitrarily small.