# Generalized Sketches for Streaming Sets
## 5 Our Framework SimCar
### Common-Interest Count Estimation  
Similarly, we use the MLE and Poisson approximation techniques to estimate the common-interest count \(d_{u\cap\mathcal{U}}\) of any two users \(u,v\in U\). Specifically, we assume  
\[d_{u\cap\mathcal{U}}\sim\text{Poisson}(\lambda_{u,v}).\]Define \(N_{u\setminus v}=N_{u}\setminus N_{v}\) and \(N_{v\setminus u}=N_{v}\setminus N_{u}\). Let \(d_{u\setminus v}=|N_{u\setminus v}|\) and \(d_{v\setminus u}=|N_{v\setminus u}|\). We also assume  
\[d_{u\setminus v}\sim\text{Poisson}(\lambda_{u}-\lambda_{u,v}),\]  
\[d_{v\setminus u}\sim\text{Poisson}(\lambda_{v}-\lambda_{u,v}),\]  
where \(\lambda_{u}\geq\lambda_{u,v}\) and \(\lambda_{v}\geq\lambda_{u,v}\). Similar to \(N_{u,i},1\leq i\leq k\), we define  
\[N_{u\cap v,i}=\{w:i_{w}=i,w\in N_{u\cap v}\},\]  
\[N_{u\setminus v,i}=\{w:i_{w}=i,w\in N_{u\setminus v}\},\]  
\[N_{v\setminus u,i}=\{w:i_{w}=i,w\in N_{v\setminus u}\}.\]  
Let \(d_{u\cap v,i}=|N_{u\cap v,i}|\), \(d_{u\setminus v,i}=|N_{u\setminus v,i}|\), and \(d_{v\setminus u,i}=|N_{v\setminus u,i}|\). Similar to Equation (2), we find that \(d_{u\cap v,1},\ldots,d_{u\cap v,k},d_{u\setminus v,1},\ldots,d_{u\setminus v,k}\), \(d_{v\setminus u,1},\ldots,d_{v\setminus u,k}\) are independent, and they are distributed according to the following Poisson distributions  
\[d_{u\cap v,i}\sim\text{Poisson}\bigg{(}\frac{\lambda_{u,v}}{k}\bigg{)},\]  
\[d_{u\setminus v,i}\sim\text{Poisson}\bigg{(}\frac{\lambda_{u}-\lambda_{u,v}}{ k}\bigg{)},\]  
\[d_{v\setminus v,i}\sim\text{Poisson}\bigg{(}\frac{\lambda_{v}-\lambda_{u,v}}{ k}\bigg{)}.\]  
Define \(x_{u\cap v,i}=\min_{w\in N_{u\cap v,i}}r_{w}\), \(x_{u\setminus v,i}=\min_{w\in N_{u\setminus v,i}}r_{w}\), and \(x_{v\setminus u,i}=\min_{w\in N_{v\setminus u,i}}r_{w}\). Then, we find that  
\[x_{u,i}=\min(x_{u\cap v,i},x_{u\setminus v,i}),\]  
\[d_{u\setminus v}\sim\text{Poisson}(\lambda_{u}-\lambda_{u,v}),\]0  
Let \(f(x_{u,i}=x,x_{v,i}=x^{\prime}|\lambda_{u},\lambda_{v},\lambda_{u,v})\) denote the PDF of the random variable pair \((x_{u,i},x_{v,i})\) at \((x,x^{\prime})\), given \(\lambda_{u}\), \(\lambda_{v}\), and \(\lambda_{u,v}\). In what follows, we omit the conditions \(\lambda_{u}\), \(\lambda_{v}\), and \(\lambda_{u,v}\) for simplicity when no confusion is raised. We derive \(f(x_{u,i}=x,x_{v,i}=x^{\prime})\) for all possible relations between \(x_{u,i}\) and \(x_{v,i}\) as follows:  
**Case 1:**\(x_{u,i}=x_{v,i}=1\). This case indicates \(d_{u\cap v,i}=d_{u\setminus v,i}=d_{v\setminus u,i}=0\). Therefore, we have  
\[d_{u\setminus v}\sim\text{Poisson}(\lambda_{u}-\lambda_{u,v}),\]1 \[d_{u\setminus v}\sim\text{Poisson}(\lambda_{u}-\lambda_{u,v}),\]2 \[d_{u\setminus v}\sim\text{Poisson}(\lambda_{u}-\lambda_{u,v}),\]3 \[d_{u\setminus v}\sim\text{Poisson}(\lambda_{u}-\lambda_{u,v}),\]4  
**Case 2:**\(x_{u,i}=1\wedge 0<x_{v,i}<1\).This case indicates \(d_{u\cap v,i}=d_{u\setminus v,i}=0\) and \(0<x_{v\setminus u,i}=x_{v,i}<1\). Similar to Equation (4), we have \(f(x_{v\setminus u,i}=x)=\frac{\lambda_{v}-\lambda_{u,v}}{k}e^{-\frac{((x_{v}- \lambda_{u,v}))x}{k}}\). Then, we have  
\[d_{u\setminus v}\sim\text{Poisson}(\lambda_{u}-\lambda_{u,v}),\]5 \[d_{u\setminus v}\sim\text{Poisson}(\lambda_{u}-\lambda_{u,v}),\]6 \[d_{u\setminus v}\sim\text{Poisson}(\lambda_{u}-\lambda_{u,v}),\]7  
**Case 3: \(0<x_{u,i}<1\wedge x_{v,i}=1\). ** Similar to Case 2, we have  
\[ \begin{split}& f(x_{u,i}=x,x_{v,i}=1)\\ &=f(x_{u\setminus p,i}=x)P(d_{u\cap p,i}=0)P(d_{v\setminus u,i}= 0)\\ &=\frac{\lambda_{u}-\lambda_{u,v}}{k}e^{-\frac{(\lambda_{u}- \lambda_{u,v})x}{k}},\quad 0<x<1.\end{split}  \tag{8}\]  
**Case 4: \(0<x_{u,i}=x_{v,i}<1\). ** This case indicates that \(x_{u\cap p,i}<x_{u\setminus p,i}\) and \(x_{u\cap p,i}<x_{v\setminus u,i}\). Similar to Equation (4), we obtain \(f(x_{u\cap p,i}=x)=\frac{\lambda_{u,v}}{k}e^{-\frac{\lambda_{u,v}x}{k}},f(x_{ u\setminus v,i}>x)=e^{-\frac{(\lambda_{u}-\lambda_{u,v})x}{k}}\), and \(f(x_{v\setminus u,i}>x)=e^{-\frac{(\lambda_{v}-\lambda_{u,v})x}{k}}\). Therefore, we have  
\[