# Generalized Sketches for Streaming Sets
## 2 Related Work  
**LSH for similarity estimation. ** LSH maps similar objects (e.g., sets and vectors) to the same hash value with higher probability than dissimilar ones [23], and has been widely used for applications such as similarity estimation and nearest neighbor search. _MintHash_[16] is a popular LSH technique for estimating the Jaccard similarity coefficient of sets. Recently, considerable attention has been paid to improving the performance of MinHash. For example, _b-bit minwise hashing_[18], _odd sketch_[19], and MaxLogHash [27] use probabilistic techniques such as sampling and sketching to further reduce the amount of memory used by MinHash. However, all these methods update each element with a high complexity of \(O(k)\). To solve this problem, _OPH_[17] and its variants [20; 21; 22; 28] were developed to accelerate the speed of processing each element in sets by orders of magnitude. Very recently, [PERSON] et al. [29] used HyperLogLog [5] and OPH [17] sketches to estimate the Jaccard similarity, as well as the containment. In addition to sets (i.e., binary vectors), a variety of sketch methods have also been developed to estimate similarity between real-value weighted vectors. For example, [PERSON] [25] developed a method, _SimHash_, for approximating angle similarity (i.e., cosine similarity) between weighted vectors. [PERSON] et al. [26] used _p_-stable distributions to estimate \(l_{p}\) distance between weighted vectors, where \(0<p\leq 2\). Refs. [30; 31; 32; 33; 34; 35; 36; 37; 38] were developed to approximate the weighted Jaccard similarity of weighted vectors. [PERSON] et al. [39] proposed a Gumbel-Max-Trick-based sketching method, \(\mathcal{P}\)-MinHash, to estimate another novel Jaccard similarity metric, _probability Jaccard similarity_. They also demonstrated that the probability Jaccard similarity is scale invariant and more sensitive to changes in vectors. [PERSON] et al. [40] proposed FastGM to further reduce the time complexity of \(\mathcal{P}\)-MinHash by generating the hash values in order. **LSH for nearest neighbor search. ** To perform a nearest neighbor search, refs. [23; 26] first, objects are hashed into a hash table. To perform a similarity search, a query object is hashed into a bucket of the hash table, and then the objects in the bucket are used as candidate objects, which need to be further verified. However, nearest neighbors may not appear as candidate objects because close objects may be hashed into different buckets. To solve this problem, refs. [41; 42; 43] proposed methods that look up more than one bucket of the hash table for a query, which significantly reduces the amount of storage. To further  
Figure 1: Framework of our framework SimCar. improve the performance, many techniques, such as _C2 LSH_[44], _SK-LSH_[45] and _LSB-Frest_[46], were developed to reduce memory usage and query cost. After gathering the candidate objects, but before verifying them, [PERSON] et al. [47] developed a method _BayesLSH_ that performs similarity estimation and candidate pruning using LSH sketches to accelerate the procedure of verifying candidate objects. Real-world datasets are usually not distributed uniformly over the space, which results in unbalanced LSH buckets and degrades the performance of LSH for nearest neighbor search. To solve this problem, [PERSON] et al. [48] developed a method _DSH_ leveraging data distributions to hash nearest neighbors together with a larger probability. [PERSON] et al. [49] developed a system, FLASH, using OPH and reservoir sampling to overcome the computational and parallelization hurdles. Recently, several LSH-based methods [50; 51; 52] and transformation-based methods [53; 54; 55] were developed to solve the maximum inner product search (MIPS) problem, i.e., search vectors having maximum inner products with a given query vector. **Cardinality estimation. ** To estimate a large data set's cardinality, [PERSON] et al. [3] developed the first fast sketch method LPC. Additionally, refs.