# Generalized Sketches for Streaming Sets
## 5 Our Framework SimCar
### User Cardinality Estimation
The authors of [5; 68; 69] reveal that statistical properties of \(\mathbb{E}_{d_{u}}(\phi(\vec{x}_{u}))\) and \(\text{Var}_{d_{u}}(\phi(\vec{x}_{u}))\) are well approximated by \(\mathbb{E}_{\text{Poisson}(\lambda_{u})}(\phi(\vec{x}_{u}))\) and \(\text{Var}_{\text{Poisson}(\lambda_{u})}(\phi(\vec{x}_{u}))\) when setting \(\lambda_{u}=d_{u}\), which is the _depoissonization step_. **Estimator of \(\lambda_{u}\). ** Next, we elaborate our method to derive the MLE of \(\lambda_{u}\) under the Poisson approximation model. For any \(0<x<1\), the following equation holds  
\[ \begin{split}& f(x_{u,i}=x|\lambda_{u})\\ =&\sum_{d_{u,i}=0}^{+\infty}f(x_{u,i}=x|d_{u,i}) \frac{e^{-\frac{\lambda_{u}}{k}}\lambda_{u}^{d_{u,i}}}{d_{u,i}!k^{d_{u,i}}}\\ =& e^{-\frac{\lambda_{u}}{k}}+\sum_{d_{u,i}=1}^{ \infty}d_{u,i}(1-x)^{d_{u,i}-1}\frac{e^{-\frac{\lambda_{u}}{k}}\lambda_{u}^{d_ {u,i}}}{d_{u,i}!k^{d_{u,i}}}\\ =&\frac{\lambda_{u}}{k}e^{-\frac{\lambda_{u}}{k}}, \end{split}  \tag{3}\]  
where the last equation holds because of the Taylor series of \(\frac{\lambda_{u}}{k}e^{-\frac{\lambda_{u}x}{k}}\) at \(x_{0}=1\). Then, we compute the PDF of \(x_{u,i}\) at \(x\) given \(\lambda_{u}\) as  
\[f(x_{u,i}=x|\lambda_{u})=\left\{ \begin{array}{ll}\frac{\lambda_{u}}{k}e^{- \frac{\lambda_{u}x}{k}},&0<x<1\\ e^{-\frac{\lambda_{u}}{k}},&x=1.\end{array} \right. \tag{4}\]The last equation holds because we have \(d_{u,i}=0\) when \(x=1\), which occurs with probability \(P(d_{u,i}=0|\lambda_{u})=e^{-\frac{\lambda u}{k}}\). Let \(\Phi_{u}\) denote the set of elements in vector \(\vec{x}_{u}\) that are smaller than \(1\), i.e.,  
\[\Phi_{u}=\{i:x_{u,i}<1,1\leq i\leq k\}.\]  
Denoted by \(k_{u}\) is the number of elements in vector \(\vec{x}_{u}\) that equal \(1\). Then, the likelihood function of \(\lambda_{u}\) given by \(k\) independent observed variables \(x_{u,1},\ldots,x_{u,k}\) is computed as  
\[\mathcal{L}(\vec{x}_{u}|\lambda_{u}) =\prod_{i=1}^{k}f(x_{u,i}|\lambda_{u})\] \[=e^{-\frac{\lambda u_{u}}{k}}\prod_{i\in\Phi_{u}}\frac{\lambda_{ u}}{k}e^{-\frac{\lambda u_{u}u_{i}}{k}}\] \[=\left(\frac{\lambda_{u}}{k}\right)^{k-k_{u}}e^{-\frac{\lambda u (k_{u}+\Sigma_{\text{loc}}\Phi_{u}\,x_{u,i})}{k}}\] \[=\left(\frac{\lambda_{u}}{k}\right)^{k-k_{u}}e^{-\frac{\lambda u \frac{\Sigma_{\text{loc}}\,x_{u,i}}{k}}{k}}.\]  
Let \(\hat{\lambda}_{u}=\arg\max_{\lambda_{u}}\log\mathcal{L}(\vec{x}_{u}|\lambda_{ u})\) denote the MLE of \(\lambda_{u}\). We compute the derivative of \(\log\mathcal{L}(\vec{x}_{u}|\lambda_{u})\) as  
\[\frac{\partial\log\mathcal{L}(\vec{x}_{u}|\lambda_{u})}{\partial\lambda_{u}}= \frac{k-k_{u}}{\lambda_{u}}-\frac{\sum_{i=1}^{k}x_{u,i}}{k}.\]  
Let \(\frac{\partial\log\mathcal{L}(\vec{x}_{u}|\lambda_{u})}{\partial\lambda_{u}}=0\). Then, we obtain the MLE of \(\lambda_{u}\) as  
\[\hat{\lambda}_{u}=\frac{k(k-k_{u})}{\sum_{i=1}^{k}x_{u,i}}. \tag{5}\]  
To analyze the estimation error of \(\hat{\lambda}_{u}\), we first compute the Fisher information of \(\lambda_{u}\) as  
\[\mathcal{I}(\lambda_{u}) =-\mathbb{E}\bigg{(}\frac{\partial^{2}\log\mathcal{L}(\vec{x}_{u} |\lambda_{u})}{\partial\lambda_{u}^{2}}\bigg{)}\] \[=\mathbb{E}\bigg{(}\frac{k-k_{u}}{\lambda_{u}^{2}}\mid\lambda_{u} \bigg{)}\] \[=\frac{k(1-e^{-\frac{\lambda_{u}}{k}})}{\lambda_{u}^{2}}.\]  
The last equation is obtained because \(\mathbb{E}(k_{u}|\lambda_{u})=ke^{-\frac{\lambda u}{k}}\), which is easily derived from Equation (4). From [70], we find that the MLE \(\hat{\lambda}_{u}\) is an asymptotically efficient unbiased estimator of \(\lambda_{u}\), and its mean square error (MSE) asymptotically approaches the Cramer-Rao lower bound (CRLB) of \(\lambda_{u}\), which is defined as \(\frac{1}{L(\lambda_{u})}\). Formally, we have \(\lim_{k\rightarrow+\infty}\hat{\lambda}_{u}\rightarrow\lambda_{u}\) and \(\lim_{k\rightarrow+\infty}\text{MSE}(\hat{\lambda}_{u})\rightarrow\frac{1}{L( \hat{\lambda}_{u})}\). Lastly, at the depoissonization step, we use \(\hat{\lambda}_{u}\) to approximate \(d_{u}\).