# Generalized Sketches for Streaming Sets  
[PERSON]  
1  
[PERSON]  
2  
[PERSON]  
3 MOE Key Laboratory for Intelligent Networks and Network Security, Xi'an Jiaotong University, Xi'an 710049, China; [EMAIL_ADDRESS] (P.J. ); [EMAIL_ADDRESS] (P.W.) [PERSON]  
3 Correspondence: [EMAIL_ADDRESS] (K.Y. ); [EMAIL_ADDRESS] (Y.Q. ); Tel. : +486-1590871901 (K.Y)  
[PERSON] Wang  
LogLog [4], HyperLogLog [5], MinCount [6], RoughEstimator [7], and their variants [2; 8; 9; 10; 11; 12; 13] to generate a compact data summary (or sketch) for each user's interest set, and then infer user cardinalities from the generated sketches. * **Common-interest count. ** Two users' common-interest count is defined as the number of interests that they both link to, i.e., the cardinality of the intersection of two users' interest sets. It is popularly used for applications such as friend recommendation [14] and network anomaly detection [15]. One can use sketch and sampling methods in [13; 14; 15] to estimate users' common-interest counts. * **User Jaccard similarity. ** The Jaccard similarity is a popular similarity measure. Two users' similarity can be evaluated as the Jaccard similarity of their interest sets, which is defined as their common-interest count divided by the number of distinct interests at least one of them links to. One can use sketch methods such as _MinHash_[16], _OPH_[17], and their variants [18; 19; 20; 21; 22] to estimate users' Jaccard similarities. Some of these sketch methods, such as Minhash, can be used for _locality-sensitive hashing_ (LSH) indexing [16; 23; 24; 25], which is capable of searching a query user's similar users with sub-linear time. The above three _duplicate-irrelevant_ statistics may all be desired for applications such as network anomaly detection. For example, given a detected abnormal user (e.g., the IP address of an attacker captured by Honeynet systems), network administers may want to quickly search for similar users among all network users, which may also be abnormal users, and then estimate their cardinalities, Jaccard similarities, and common-interest counts for further inspection. Although many cardinality estimation methods can be easily extended to estimate the above three statistics because they generate _mergeable_ sketches (mergeable cardinality estimation sketches of two sets \(S_{1}\) and \(S_{2}\) can be used to generate a sketch of \(S_{1}\cup S_{2}\), which is used to estimate the cardinality of \(S_{1}\cup S_{2}\). ), [PERSON] et al. [15] observed that their extensions exhibit large errors for estimating common-interest counts and Jaccard similarities. Even worse, the sketches generated by these cardinality methods cannot be used for LSH indexing, which results in a high computational cost for searching users with similar interests. One can combine multiple existing methods to generate different sketches for estimating user cardinalities, common-interest counts, and Jaccard similarities, respectively. This straightforward method increases the required memory and computational resources, which limits its usage for high-speed data streams. To address the above challenges, we develop a novel framework, _SimCar_, which is shown in Figure 1. The framework consists of two modules: (1) the _online processing module_, which uses [PERSON]'s algorithm [6] to build an _order-hashing_ (OH) sketch of the interest set of each user occurring in the stream; (2) the _online query module_, which provides functions for estimating the cardinalities, intersection cardinalities, and Jaccard similarities of users' interest sets at any time of interest. Specially, using OH sketches, we develop maximum likelihood estimation (MLE) methods for estimating cardinalities and intersection cardinalities of users' interest sets.