# Generalized Sketches for Streaming Sets
## 5 Our Framework SimCar
### User Cardinality Estimation  
In this section, we estimate the cardinality of any queried user. Specially, we first build a probabilistic model according to the state of the OH sketch, and then solve it using MLE methods. **Exact probabilistic model. ** For any user \(u\in U\), let \(N_{u,i}\) denote the set of its interests whose hash values equal \(i\) with respect to hash function \(f\); that is,  
\[N_{u,i}=\{w:i_{w}=i,w\in N_{u}\},\quad 1\leq i\leq k.\]  
At any time of stream \(\Gamma\), from Equation (1), we have  
\[x_{u,i}=\min_{w\in N_{u,i}}r_{w}k-\lfloor r_{w}k\rfloor.\]  
Define \(d_{u,i}=|N_{u,i}|\). Let \(f(x_{u,i}=x|d_{u,i}=d)\) denote the probability density function (PDF) of random variable \(x_{u,i}\) at \(x\) given \(d_{u,i}=d\). Then, we have  
\[f(x_{u,i}=x|d_{u,i}=d)=\left\{ \begin{array}{ll}d(1-x)^{d-1},&d>0\wedge 0<x<1 \\ 1,&d=0\wedge x=1\\ 0,&\text{otherwise}.\end{array} \right.\]  
Our algorithm randomly splits users in set \(N_{u}\) into \(k\) subsets \(N_{u,1}\), \(\ldots\), \(N_{u,k}\). Using the classical balls-in-urns model, we derive the probability distribution of vector \((d_{u,1},\ldots,d_{u,k})\) as  
\[P(d_{u,1},\ldots,d_{u,k}|d_{u})=\frac{\binom{d_{u}}{d_{u,1},\ldots,d_{u,k}}}{ k^{d_{u}}},\]  
where \(\binom{d_{u}}{d_{u,1},\ldots,d_{u,k}}=\frac{d_{u,1}! }{d_{u,1}!\cdots d_{u,k}!}\). Therefore, the PDF of \(\vec{x}_{u}\) given \(d_{u}\) is computed as  
\[f(\vec{x}_{u}|d_{u})=\sum_{d_{u,1},\ldots,d_{u,k}=d_{u}}\frac{\binom{d_{u}}{d _{u,1},\ldots,d_{u,k}}}{k^{d_{u}}}\prod_{i=1}^{k}f(x_{u,i}|d_{u,i}).\]  
**Poisson approximation model. ** Clearly, \(d_{u,1},\ldots,d_{u,k}\) are not independent, which hinders us when it comes to obtaining the MLE of \(d_{u}\). Similar to [5], we use the Poisson approximation technique to remove the dependence of \(d_{u,1},\ldots,d_{u,k}\). Specifically, we assume that the value of \(d_{u}\) is distributed according to a Poisson distribution with parameter \(\lambda_{u}\), i.e., \(d_{u}\sim\text{Poisson}(\lambda_{u})\). Then, the PDF of \(\vec{x}_{u}\) given \(\lambda_{u}\) is  
\[ \begin{split}& f(\vec{x}_{u}|\lambda_{u})=\sum_{d=0}^{+\infty} \mathcal{L}(\vec{x}_{u}|d_{u})\frac{e^{-\lambda_{u}}\lambda_{u}^{d_{u}}}{d_{u}! }\\ &=\sum_{d_{u}=0}^{+\infty}\sum_{d_{u}=0}^{+\infty}\frac{(d_{u,1} \cdots d_{u,k})^{d_{u}}}{k^{d_{u}}}\prod_{i=1}^{k}f(x_{u,i}|d_{u,i})\frac{e^{ -\lambda_{u}}\lambda_{u}^{d_{u}}}{d_{u}!}\\ &=\sum_{d_{u,1}=0}^{+\infty}\ldots\sum_{d_{u,k}=0}^{+\infty}\prod _{i=1}^{k}f(x_{u,i}|d_{u,i})\frac{e^{-\frac{\lambda_{u}}{k}}\lambda_{u}^{d_{ u}}}{d_{u,i}!k^{d_{u,i}}}\\ &=\prod_{i=1}^{k}\sum_{d_{u,i}=0}^{+\infty}f(x_{u,i}|d_{u,i}) \frac{e^{-\frac{\lambda_{u}}{k}}\lambda_{u}^{d_{u,i}}}{d_{u,i}!k^{d_{u,i}}}\\ &=\prod_{i=1}^{k}f(x_{u,i}|\lambda_{u}).\end{split} \]  
Given \(d_{u}\sim\text{Poisson}(\lambda_{u})\), the above equation indicates that the values of \(x_{u,1},\ldots,x_{u,k}\) are independent and identically distributed. In addition, the values of \(d_{u,1},\ldots,d_{u,k}\) are independent and identically distributed according to a Poisson distribution \(\text{Poisson}(\frac{\lambda_{u}}{k})\). Formally, we have  
\[d_{u,i}\sim\text{Poisson}\bigg{(}\frac{\lambda_{u}}{k}\bigg{)},\quad i=1, \ldots,k. \tag{2}\]  
For an estimator \(\phi(\vec{x}_{u})\) of \(d_{u}\) (e.g., Equation (5), derived later), we let \(\mathbb{E}_{d_{u}}(\phi(\vec{x}_{u}))\) and \(\text{Var}_{d_{u}}(\phi(\vec{x}_{u}))\) denote the expectation and the variance of \(\phi(\vec{x}_{u})\) under the exact probabilistic model (i.e., \(f(\vec{x}_{u}|d_{u})\)), and let \(\mathbb{E}_{\text{Poisson}(\lambda_{u})}(\phi(\vec{x}_{u}))\) and \(\text{Var}_{\text{Poisson}(\lambda_{u})}(\phi(\vec{x}_{u}))\) denote the expectation and the variance of \(\phi(\vec{x}_{u})\) under the Poisson approximation model (i.e., \(f(\vec{x}_{u}|d_{u})\)).