# Generalized Sketches for Streaming Sets
## 5 Our Framework SimCar
### Common-Interest Count Estimation
\begin{split}& f(x_{u,i}=x,x_{v,i}=x)\\ &=f(x_{u\cap p,i}=x)f(x_{u\setminus p,i}>x)f(x_{v\setminus u,i} >x)\\ &=\frac{\lambda_{u,v}}{k}e^{-\frac{(\lambda_{u}+\lambda_{v}- \lambda_{u,v})x}{k}},\quad 0<x<1.\end{split}  \tag{9}\]  
**Case 5: \(0<x_{u,i}<x_{v,i}<1\). ** This case indicates that \(x_{u\setminus p,i}=x_{u,i}\) and \(\min(x_{u\cap v,i},x_{v\setminus u,i})=x_{v,i}\). We find that \(d_{v,i}=d_{u\cap v,i}+d_{v\setminus u,i}\sim\text{Poisson}\Big{(}\frac{ \lambda_{u}}{k}\Big{)}\), and \(f(\min(x_{u\cap v,i},x_{v\setminus u,i})=x^{\prime})=\frac{\lambda_{v}}{k}e^{ -\frac{\lambda_{u,v}x^{\prime}}{k}}\). Therefore, we have  
\[ \begin{split}& f(x_{u,i}=x,x_{v,i}=x^{\prime})\\ &=f(x_{u\setminus v,i}=x)f(\min(x_{u\cap v,i},x_{v\setminus u, i})=x^{\prime})\\ &=\frac{(\lambda_{u}-\lambda_{u,v})\lambda_{v}}{k^{2}}e^{-\frac{( \lambda_{u}-\lambda_{u,v})x+\lambda_{u,v}x^{\prime}}{k}},0<x<x^{\prime}<1.\end{split}  \tag{10}\]  
**Case 6: \(0<x_{v,i}<x_{u,i}<1\). ** Similar to Case 5, we have  
\[ \begin{split}& f(x_{u,i}=x,x_{v,i}=x^{\prime})\\ &=f(\min(x_{u\cap v,i},x_{u\setminus v,i})=x)f(x_{v\setminus u,i}=x^{\prime})\\ &=\frac{(\lambda_{v}-\lambda_{u,v})\lambda_{u}}{k^{2}}e^{-\frac{( \lambda_{v}-\lambda_{u,v})x^{\prime}+\lambda_{u,v}x}{k}},0<x^{\prime}<x<1. \end{split}  \tag{11}\]  
Let \(\Phi^{(j)}_{u,v}\) denote the set of integers \(i\in\{1,\dots,k\}\), such that the relation between \(x_{u,j}\) and \(x_{v,i}\) is Case \(j\), \(1\leq j\leq 6\). Define \(k^{(j)}_{u,v}=|\[PERSON]^{(j)}_{u,v}|\). Then, we have \(k_{u}=k^{(1)}_{u,v}+k^{(2)}_{u,v}\), \(k_{v}=k^{(1)}_{u,v}+k^{(3)}_{u,v}\), \(\Phi_{u}=\Phi^{(3)}_{u,v}\cup\Phi^{(4)}_{u,v}\cup\Phi^{(5)}_{u,v}\cup\Phi^{(6)}_ {u,v}\), and \(\Phi_{v}=\Phi^{(2)}_{u,v}\cup\Phi^{(4)}_{u,v}\cup\Phi^{(5)}_{u,v}\cup\Phi^{(6)} _{u,v}\). Now, we obtain the likelihood function of \(\widetilde{\lambda}=(\lambda_{u},\lambda_{v},\lambda_{u,v})\) given by \(k\) independent observed variable pairs \((x_{u,1},x_{v,1}),\dots,(x_{u,k},x_{v,k})\) as  
\[\begin{split}&\mathcal{L}(\vec{x}_{u},\vec{x}_{v})=\Pi_{i=1}^{k}f(x_{u,i},x_{v,i})=e^{-\frac{(\lambda_{u}+\lambda_{v}-\lambda_{u,v})\lambda_{v}}{k}} \\ &\times\bigg{(}\frac{\lambda_{v}-\lambda_{u,v}}{k}\bigg{)}^{k^{(2 )}_{u,v}}e^{-\frac{\lambda_{u}\Phi^{(2)}_{u,v}+(\lambda_{v}-\lambda_{u,v}) \lambda_{v}\lambda_{v}\lambda_{v}}{k}}\\ &\times\bigg{(}\frac{\lambda_{u}-\lambda_{u,v}}{k}\bigg{)}^{k^{(3 )}_{u,v}}e^{-\frac{\lambda_{u}\Phi^{(3)}_{u,v}+(\lambda_{u}-\lambda_{u,v}) \lambda_{v}\lambda_{v}\lambda_{v}}{k}}\\ &\times\bigg{(}\frac{\lambda_{u,v}}{k}\bigg{)}^{k^{(4)}_{u,v}} e^{-\frac{(\lambda_{u}+\lambda_{v}-\lambda_{u,v})\lambda_{v}\lambda_{v}\lambda_{v} \lambda_{v}}{k}}\\ &\times\bigg{(}\frac{(\lambda_{u}-\lambda_{u,v})\lambda_{v}}{k^{  
**Complexities of user cardinality estimation. ** No extra memory space is required for user cardinality estimation. The time complexity of estimating a user's cardinality is \(O(k)\). **Complexities of common-interest count estimation. ** No extra memory space is required for common-interest count estimation. We find that our method only requires several Newton-Raphson iterations to converge, where each iteration has a negligible computational cost. Therefore, the time complexity of estimating two users' common-interest counts is \(O(k)\). **Complexities of Jaccard similarity estimation. ** No extra memory space is required for common-interest count estimation. Based on two users' DOH sketches, time \(O(k)\) is required when estimating two users' Jaccard similarity. **Complexities of nearest neighbor search. ** Given DOH sketches of users in \(U\), space \(O(|U|b)\) and time \(O(|U|b)\) are required for building LSH tables, and searching a query user's nearest neighbors requires time \(O(k\log|U|)\).