# Generalized Sketches for Streaming Sets
## 6 Evaluation
### Accuracy  
**Results of cardinality estimation. ** We compared our method, SimCar, with HyperLogLog used by MinHash and HLL and OPH and HLL, as well as the CORE algorithm [59], which is introduced in Algorithm 3 in Section 5. In this experiment, all three sketch methods--HLL, CORE, and SimCar--use the same number of registers, i.e., \(k_{1}=k\). As shown in Figure 3, our method, SimCar, is significantly more accurate than HLL and CORE on these real-world datasets. To be more specific, SimCar gives a gain of 18%\(\sim\)40% (resp. 10%\(\sim\)23%) improvement to CORE (resp. HLL). For example, on Wikipedia, the average NRMSE of SimCar is 0.0285, while those of HLL and CORE are 0.0337 and 0.0475, respectively. Figure 4 further shows the average NRMSEs for different \(k\). We can see that the average NRMSEs of all methods decrease as \(k\) increases, and our method is consistently more accurate than HLL and CORE. In addition, we compute the fine-grained NRMSEs with respect to the user cardinality ranging from 1 to \(10,000\) with \(k=2^{8}\) and \(k=2^{9}\). As shown in Figure 5, both HLL and CORE exhibit large estimation errors when user cardinality is small because they both use two different estimators for cardinalities within two different ranges, respectively. However, our method, SimCar, just uses one estimator, and we find that SimCar decreases the NRMSEs of HLL and CORE by \(10\%-42\%\) for different user cardinalities. **Results of common-interest count estimation. ** As shown in Figure 5(a)-c, where we set \(k_{1}=k\), we can see that our method, SimCar, is more accurate than the other two methods for all three schemes introduced in Section 6.2, and scheme 1 performs the worst among the three schemes, whose average NRMSEs are up to 8.7\(\times\) those of the other two schemes. We raised \(k_{1}\) to 2\(k\), and the results are shown in Figure 5(d)-f. We can see that SimCar still outperforms MinHash and HLL and OPH and HLL for most of the datasets. Figure 7 show the average NRMSEs for different \(k\) on datasets Reuters, Tropes, and TREC, where we set \(k_{1}=k\). We can see that the average NRMSEs of all methods decrease as \(k\) increases. For scheme 1, our method, SimCar, is up to four and three times more accurate than MinHash and HLL and OPH and HLL, respectively. For schemes 2 and 3, we find that OPH and HLL gives results comparable to SimCar when \(k\) is medium. However, our method, SimCar, still outperforms OPH and HLL when \(k\geq 2^{10}\). **Results of Jaccard similarity estimation and nearest neighbor search. ** We compared our method to the MinHash sketch and densified OPH sketch for Jaccard similarity estimation and nearest neighbor search. We used the technique discussed in Section 5.1 to build LSH for all three methods. The experimental results in Table 3 demonstrate that our method, SimCar, is comparable to MinHash and densified OPH on all the datasets. Figure 2: Online sketching time of our framework, SimCar, in comparison with MinHash and HLL and OPH and HLL. (**a**) Sketching time on different datasets with \(k_{1}=k=2^{9}\). (**b**) Sketching time on dataset Reuters with different \(k\). Figure 4: User cardinality estimation errors of our framework, SimCar, compared with HLL and CORE, \(k_{1}=k=2^{9}\) by default. Figure 3: User cardinality estimation errors of our framework, SimCar, compared with HLL and CORE, \(k_{1}=k=2^{9}\) by default.