# Generalized Sketches for Streaming Sets
## 6 Evaluation
### Baselines  
We compared our framework with the following state-of-the-art methods on all four tasks: user cardinality estimation, common-interest count estimation, Jaccard similarity estimation, and nearest neighbor search.  
* **MinHash and HLL.** For common-interest count estimation, the baseline is the method [15], which estimates common-interest counts by generating both MinHash [16] and HyperLogLog [5] (short for HLL in the following paper) sketches for each user's interest set. Clearly, one can use generated HLL sketches to estimate user cardinalities, and  
\begin{table}
\begin{tabular}{l c c c} \hline \hline  & **\# Users** & **\# Interests** & **Size** \\ \hline Movie & 6040 & 9746 & 1,000,209 \\ \hline Reuters & 21,557 & 60,234 & 1,464,182 \\ \hline Tropes & 152,093 & 64,415 & 3,232,134 \\ \hline Wikipedia & 2780 & 276,739 & 7,846,807 \\ \hline Flickr & 499,610 & 395,979 & 8,545,307 \\ \hline TREC & 556,077 & 1,729,302 & 151,632,178 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Real-world datasets used in our experiments, where “size” refers to the number of elements in the stream.  
use generated Minhash sketches to estimate Jaccard similarities and build LSH tables for a nearest neighbor search.
* **OPH+HLL.** One can also solve all four tasks by combining OPH [17] and HLL, where OPH [17] is much faster than MinHash and exhibits comparable accuracy for applications such as Jaccard similarity estimation and nearest neighbor search [20; 21; 22]. In detail, HLL sketches were used to estimate user cardinalities, and optimal densified OPH sketches were used to estimate Jaccard similarity and build LSH tables for a rapid nearest neighbor search. To estimate the common-interest count of any two users \(u\) and \(v\), we first easily obtained (1) estimations \(\hat{d}_{u}\), \(\hat{d}_{v}\), and \(\hat{d}_{u,v\cup}\) of \(d_{u}\), \(d_{v}\), and \(d_{u\cup v}=|N_{u}\cup N_{v}|\) from HLL sketches and our OH sketches; (2) estimation \(\hat{J}_{u,v}\) of Jaccard similarity \(J_{u,v}\) from optimal densified OPH sketches and DOH sketches. As shown in [15], the common-interest count \(d_{u\cap v}\) can be estimated by each of the following schemes: (**scheme 1**) \(\hat{d}_{u\cap v}=\hat{d}_{u}+\hat{d}_{v}-\hat{d}_{u\cup v}\); (**scheme 2**) \(\hat{d}_{u\cap v}=\hat{J}_{u,v}\hat{d}_{u\cup v}\); (**scheme 3**) \(\hat{d}_{u\cap v}=\frac{\hat{J}_{u,v}}{\hat{J}_{u,v}+1}(\hat{d}_{u}+\hat{d}_{ v})\). Similar to MinHash and HLL method [15], we initialize the parameter \(\overline{\lambda}^{(0)}=(\lambda_{u}^{(0)},\lambda_{v}^{(0)},\lambda_{u,v}^{( 0)})^{\mathsf{T}}=(\hat{d}_{u},\hat{d}_{v\cap v})^{\mathsf{T}}\) for our common-interest count estimation method in Section 5.3 and then run only a single Newton-Raphson iteration to obtain a more accurate estimation of \(d_{u\cap v}\). In our experiments, common-interest count estimations given by OPH and HLL are computed by the above schemes 1, 2, and 3 in a direct manner.  
In our experiments, by default, we let MinHash, OPH, and our sketch method OH use the same \(k\), i.e., the number of registers used to generate one MinHash/OPH/OH sketch. We let \(k_{1}\) denote the number of registers used for an HLL sketch. Therefore, our method, SimCar, uses \(k_{1}\) fewer registers than baselines MinHash and HLL and OPH and HLL. Compared with MinHash, OPH, and OH using 32-bit registers, HLL uses 5-bit registers [5]; thus, our method, SimCar, reduces the memory usage by 13.5% and 23.8% when \(k_{1}=k\) and \(k_{1}=2k\), respectively.