Generalized Sketches for Streaming Sets

Abstract

Many real-world datasets are given as a stream of user–interest pairs, where a user–interest pair represents a link from a user (e.g., a network host) to an interest (e.g., a website), and may appear more than once in the stream. Monitoring and mining statistics, including cardinality, intersection cardinality, and Jaccard similarity of users’ interest sets on high-speed streams, are widely employed by applications such as network anomaly detection. Although estimating set cardinality, set intersection cardinality, and set Jaccard similarity, respectively, is well studied, there is no effective method that provides a one-shot solution for estimating all these three statistics. To solve the above challenge, we develop a novel framework, SimCar. SimCar online builds an order-hashing (OH) sketch for each user occurring in the data stream of interest. At any time of interest, one can query the cardinalities, intersection cardinalities, and Jaccard similarities of users’ interest sets. Specially, using OH sketches, we develop maximum likelihood estimation (MLE) methods to estimate cardinalities and intersection cardinalities of users’ interest sets. In addition, we use OH sketches to estimate Jaccard similarities of users’ interest sets and build locality-sensitive hashing tables to search for users with similar interests with sub-linear time. We evaluate the performance of our methods on real-world datasets. The experimental results demonstrate the superiority of our methods.

1. Introduction

Many real-world networks (e.g., computer networks, phone networks, and financial networks) generate data (e.g., packets, calling records, and transactions) in a stream fashion, where an element (e.g., a packet) records a link from a user (e.g., a source IP address) to an interest (e.g., a destination IP address). The data can be modeled as a data stream of user–interest pairs, including duplicates, because multiple data records (e.g., packets from a source IP address to a destination IP address) may relate to the same user–interest pair. Due to the large size and high-speed nature of these data streams, it is prohibitive to collect all the data, especially when the computation and memory resources of data-collection devices (e.g., network routers) are limited. To solve this challenge, considerable attention has been paid to designing fast and memory-efficient data streaming algorithms for monitoring and mining user behaviors. For example, Count-Min sketch [1] and its variants have been successfully used to detect heavy hitters (e.g., user–interest pairs frequently occurred).

In addition to statistics using the frequency of duplicates, significant effort has also been made to mine users’ interest sets, such as:

• User cardinality. A user’s cardinality is defined to be the number of distinct interests that the user links to, i.e., the cardinality of the user’s interest set. Monitoring user cardinalities in computer networks is fundamental for applications such as network anomaly detection [2]. One can use a variety of sketch methods, such as LPC [3], 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,26], 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$.), Cohen 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 Giroire’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. In addition, we use the technique optimal densification [22] to generate densification OH (DOH) sketches and then use DOH sketches to estimate Jaccard similarities of users’ interest sets and build locality-sensitive hashing tables to search for users with similar interests with sub-linear time. Our main contributions are summarized as follows:

• For sets given in a stream fashion, our method, SimCar, builds only one type of sketches (i.e., OH sketch) to effectively mine a variety of their statistics, including cardinality, intersection cardinality, and Jaccard similarity, as well as fast search similar sets. It outperforms the straightforward method of combining existing sketch-based cardinality estimation methods and Jaccard similarity estimation methods.
• We develop maximum likelihood estimation (MLE) methods to estimate set cardinalities and intersection cardinalities, which are more accurate than the original OH-sketch-based cardinality estimation method [6].
• Compared with state-of-the-art methods, experimental results on real-world datasets demonstrate that our method, SimCar, is up to 1000 times faster for online data streams processing, and reduces the memory usage by 13.5–23.8% to achieve the same performance accuracy.

The rest of this paper is organized as follows. The problem formulation is presented in Section 3. Section 4 introduces the preliminaries. Section 5 presents our framework, SimCar. The performance evaluation is presented in Section 6. Section 2 summarizes related work. Concluding remarks then follow.

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. MinHash [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\left(k\right)$. 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, Raul 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, Charikar [25] developed a method, SimHash, for approximating angle similarity (i.e., cosine similarity) between weighted vectors. Datar et al. [26] used p-stable distributions to estimate $l_p$ distance between weighted vectors, where $0<p\le 2$. Refs. [30,31,32,33,34,35,36,37,38] were developed to approximate the weighted Jaccard similarity of weighted vectors. Ryan et al. [39] proposed a Gumbel-Max-Trick-based sketching method, $Ƥ$-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. Qi et al. [40] proposed FastGM to further reduce the time complexity of $Ƥ$-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 improve the performance, many techniques, such as C2LSH [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, Satuluri 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, Gao et al. [48] developed a method DSH leveraging data distributions to hash nearest neighbors together with a larger probability. Wang 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, Whang et al. [3] developed the first fast sketch method LPC. Additionally, refs. [2,12] used different sampling methods to enlarge the estimation range of LPC. Flajolet and Martin [56] developed a sketch method, FM, which uses a register initialized to zero for cardinality estimation. To further improve the performance of FM, sketch methods LogLog [4], HyperLogLog [5], RoughEstimator [7], and HLL-TailCut+ [57] were developed to use a list of m registers and compress the register size from 32 bits to 5 or 4 bits. Giroire [6] developed a sketch method, MinCount, (also known as bottom-k sketch [58]) which stores the k minimum hash values of elements in the stream to estimate the stream cardinality. Lumbroso [59] developed another order-statistics-based cardinality estimation method which hashes the data stream’s elements into k registers at random, and each register stores the minimum hash value of elements hashed into it. Ting [53] developed a martingale-based estimator to further improve the accuracy of the above sketch methods, such as LPC, HyperLogLog, and MinCount. Chen et al. [60] extended HyperLogLog to sliding windows. In addition to sketch methods, two sampling methods [61,62] were also developed for cardinality estimation. Recently, considerable attention [8,9,10,11] has been given to developing fast sketch methods to monitor the cardinalities of network hosts over high-speed links. Ting [13] developed methods to estimate the cardinality of set unions and intersections from MinCount sketches. Cohen et al. [15] developed a method combining MinHash and HyperLogLog to estimate set intersection cardinalities. These two methods fail to solve the problem studied in this paper, because MinCount does not belong to the LSH family, and cannot be used for sub-linear time similarity search, and MinHash fails to deal with high-speed data streams due to its high time complexity.

LSH for clustering and feature tracking. LSH can also support other analytical tasks, such as clustering and feature tracking. Mao et al. [63] proposed the MR-PGDLSH algorithm to reduce the overhead of frequent communication between nodes through LSH, so as to solve the problem of excessive communication overhead faced by the partition-based K-means clustering algorithm in the big data environment. Corizzo et al. [64,65] proposed the DENCAST algorithm to process large-scale high-dimensional data using LSH, which is more efficient than the most advanced distributed clustering algorithm. Cao et al. [66] used LSH-based k-nearest neighbor matching to generate feature correspondence, and then used a ratio test method to remove outliers from the previous matching set, and finally achieved better results. Ding et al. [67] proposed a perceptual hash algorithm based on deep learning and LSH to generate edge feature samples to improve the robustness of HRRS image authentication.

3. Problem Formulation

Let $\mathrm{\Gamma }=e^{\left(1\right)},\dots ,e^{\left(t\right)},\dots$ denote the stream of interest, where $e^{\left(t\right)}=(u^{\left(t\right)},w^{\left(t\right)})$ is the $t^{\mathrm{th}}$ element of stream $\mathrm{\Gamma }$, which represents a link from a user $u^{\left(t\right)}$ to an interest $w^{\left(t\right)}$. Note that a pair $(u,w)$ may appear more than once in stream $\mathrm{\Gamma }$. Denote by U the set of occurring users, and W the set of occurring interests. Let $N_u$ be the interest set of user u, i.e., the set of interests that user u links to. User u’s cardinality is defined as the number of its distinct interests, i.e., $d_u=\left|N_u\right|$. For two users u and v, we define their common-interest count as $d_{u\cap v}=|N_u\cap N_v|$, and their Jaccard similarity as $J_{u,v}=\frac{|N_u\cap N_v|}{|N_u\cup N_v|}$. In this paper, we aim to design a fast method to build a compact data summary (or, sketch) for each user in a single-pass stream $\mathrm{\Gamma }$. For any specific query user u, generated sketches are effective for rapidly searching for nearest neighbors of user u (i.e., users $v\in U$ with large Jaccard similarity $J_{u,v}$) without enumerating each user in U. More importantly, they are also accurate for estimating the cardinality $d_v$ of any user v, Jaccard similarity $J_{u,v}$, as well as the common-interest count $d_{u\cap v}$ of any two users u and v. For ease of reference, we list the notation used throughout the paper in Table 1.

Table 1. Table of notation.

$\mathrm{\Gamma }$	The stream of interest
$U,W$	The sets of users and interests,
$r_w$	The random rank value of interest $w\in W$
$i_w$	$i_w =\lfloor r_{w}k\rfloor +1$
k	The number of registers used for a MinHash, OPH, or OH sketch
$k_1$	The number of registers used for an HLL sketch
$N_u$	The set of interests of user $u\in U$
$N_{u\cap v}$	The set of common interests of users u and v in U, i.e., $N_{u\cap v} = N_u\cap N_v$
$N_{u\setminus v}$	The set of interests affiliated with user u but not user v, i.e., $N_{u\setminus v} = N_u\setminus N_v$
$N_{u,i}$	The set of interests w in $N_u$ with $i_w = i$
$N_{u\cap v,i}$	The set of interests w in $N_{u\cap v}$ with $i_w = i$
$N_{u\setminus v,i}$	The set of interests w in $N_{u\setminus v}$ with $i_w = i$
$d_u$	The cardinality of user $u\in U$, i.e., $d_u = \left|N_u\right|$
$d_{u\cap v}$	The common-interest count of users u and v, i.e., $d_{u\cap v} = |N_u\cap N_v|$
$d_{u\setminus v}$	The number of elements in set $N_{u\setminus v}$ i.e., $d_{u\setminus v}=|N_u\setminus N_v|$
$d_{u,i}$	The number of interests w in $N_u$ with $i_w=i$
$d_{u\cap v,i}$	The number of interests w in $N_{u\cap v}$ with $i_w=i$
$d_{u\setminus v,i}$	The number of interests w in $N_{u\setminus v}$ with $i_w=i$
$J_{u,v}$	The Jaccard similarity of sets $N_u$ and $N_v$
${\overrightarrow{x}}_u$	OH sketch of $N_u$, $u\in U$
${\overrightarrow{x}}_u^{*}$	DOH sketch of $N_u$, $u\in U$
$x_{u,i}$, $x_{u,i}^{*}$	the $i^{\mathrm{th}}$ element of vectors ${\overrightarrow{x}}_u$ and ${\overrightarrow{x}}_u^{*}$, respectively
$\pi (·)$	Random permutation from W to W
$\rho (·)$	Random variable selected from $(0,1)$ uniformly
b, c	Two parameters of LSH tables
$f\left(x\right|y)$	PDF of random variable x given condition y
${\mathsf{\Phi }}_u$	The set of elements in ${\overrightarrow{x}}_u$ that are smaller than 1
$k_u$	The number of elements in ${\overrightarrow{x}}_u$ that equal 1
${\lambda }_u,{\lambda }_{u,v}$	Parameters of Poisson approximations
${\Phi }_{u,v}^{\left(j\right)}$	The set of elements in ${\overrightarrow{x}}_u$ and ${\overrightarrow{x}}_v$ whose relations are Case j defined in Section 5.3, $1\le j\le 6$
$k_{u,v}^{\left(j\right)}$	The cardinality of set ${\mathrm{\Phi }}_{u,v}^{\left(j\right)}$, $1\le j\le 6$
$g\left(\overrightarrow{\lambda }\right)$, $H\left(\overrightarrow{\lambda }\right)$	Gradient and Hessian matrix of likelihood function $log\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)$ at $\overrightarrow{\lambda }=({\lambda }_u,{\lambda }_v,{\lambda }_{u,v})$

Table 1. Table of notation.

$\mathrm{\Gamma }$	The stream of interest
$U,W$	The sets of users and interests,
$r_w$	The random rank value of interest $w\in W$
$i_w$	$i_w =\lfloor r_{w}k\rfloor +1$
k	The number of registers used for a MinHash, OPH, or OH sketch
$k_1$	The number of registers used for an HLL sketch
$N_u$	The set of interests of user $u\in U$
$N_{u\cap v}$	The set of common interests of users u and v in U, i.e., $N_{u\cap v} = N_u\cap N_v$
$N_{u\setminus v}$	The set of interests affiliated with user u but not user v, i.e., $N_{u\setminus v} = N_u\setminus N_v$
$N_{u,i}$	The set of interests w in $N_u$ with $i_w = i$
$N_{u\cap v,i}$	The set of interests w in $N_{u\cap v}$ with $i_w = i$
$N_{u\setminus v,i}$	The set of interests w in $N_{u\setminus v}$ with $i_w = i$
$d_u$	The cardinality of user $u\in U$, i.e., $d_u = \left|N_u\right|$
$d_{u\cap v}$	The common-interest count of users u and v, i.e., $d_{u\cap v} = |N_u\cap N_v|$
$d_{u\setminus v}$	The number of elements in set $N_{u\setminus v}$ i.e., $d_{u\setminus v}=|N_u\setminus N_v|$
$d_{u,i}$	The number of interests w in $N_u$ with $i_w=i$
$d_{u\cap v,i}$	The number of interests w in $N_{u\cap v}$ with $i_w=i$
$d_{u\setminus v,i}$	The number of interests w in $N_{u\setminus v}$ with $i_w=i$
$J_{u,v}$	The Jaccard similarity of sets $N_u$ and $N_v$
${\overrightarrow{x}}_u$	OH sketch of $N_u$, $u\in U$
${\overrightarrow{x}}_u^{*}$	DOH sketch of $N_u$, $u\in U$
$x_{u,i}$, $x_{u,i}^{*}$	the $i^{\mathrm{th}}$ element of vectors ${\overrightarrow{x}}_u$ and ${\overrightarrow{x}}_u^{*}$, respectively
$\pi (·)$	Random permutation from W to W
$\rho (·)$	Random variable selected from $(0,1)$ uniformly
b, c	Two parameters of LSH tables
$f\left(x\right|y)$	PDF of random variable x given condition y
${\mathsf{\Phi }}_u$	The set of elements in ${\overrightarrow{x}}_u$ that are smaller than 1
$k_u$	The number of elements in ${\overrightarrow{x}}_u$ that equal 1
${\lambda }_u,{\lambda }_{u,v}$	Parameters of Poisson approximations
${\Phi }_{u,v}^{\left(j\right)}$	The set of elements in ${\overrightarrow{x}}_u$ and ${\overrightarrow{x}}_v$ whose relations are Case j defined in Section 5.3, $1\le j\le 6$
$k_{u,v}^{\left(j\right)}$	The cardinality of set ${\mathrm{\Phi }}_{u,v}^{\left(j\right)}$, $1\le j\le 6$
$g\left(\overrightarrow{\lambda }\right)$, $H\left(\overrightarrow{\lambda }\right)$	Gradient and Hessian matrix of likelihood function $log\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)$ at $\overrightarrow{\lambda }=({\lambda }_u,{\lambda }_v,{\lambda }_{u,v})$

4. Preliminaries

In this section, we present Giroire’s algorithm [6] for cardinality estimation, and the OPH method [17] as well as the optimal densification [22] for Jaccard similarity estimation, which are closely related with our framework, SimCar.

4.1. Giroire’s Algorithm

Giroire [6] developed a fast method, CORE, for estimating a stream’s cardinality, i.e., the number of distinct elements occurring in the stream. The basic idea behind CORE is that one can assign each element in the stream a rank that is randomly and uniformly selected from the range (0,1), and to some extent, the minimum of occurring elements’ ranks reflects the number of distinct occurring elements (i.e., the stream’s cardinality). To accelerate the performance, CORE splits elements in the stream into k subsets, and keeps track of the minimum rank for each subset, which is finally used to infer the stream’s cardinality. In detail, CORE uses k registers $x_1$, …, $x_k$ to generate a sketch of the stream, where $x_1$, …, $x_k$ are initialized to 1. Let $r_e$ be the rank of an element e that is uniformly selected from range (0, 1) at random; that is, $r_e\sim \mathrm{Uniform}(0,1)$. For an element e arriving on the stream, CORE computes $i_e=\lfloor r_{e}k\rfloor +1$ and then updates the $i_e^{\mathrm{th}}$ register $x_{i_e}$ as

$$x_{i_e}\leftarrow min(x_{i_e},r_{e}k-i_e-1).$$

(1)

At the end of the stream, the stream’s cardinality is estimated as $d^{*}=\frac{k(k-1)}{{\sum }_{i=1}^k{x}_i}$. Since $d^{*}$ is severely biased for small cardinalities, CORE treats the list of registers $x_1,\dots ,x_k$ as an LPC sketch (i.e., a bitmap of k bits) [3]. Let $n_1$ be the number of registers among $x_1,\dots ,x_k$ that equal 1 at the end of the stream. When $\frac{n_1}{k}\le 86\%$, CORE estimates the stream’s cardinality as $-klog\frac{n_1}{k}$.

4.2. OPH

OPH [17] can be viewed as a sampling method, which samples (at most) k distinct elements from each set of interest without replacement and then estimates the Jaccard similarity of two sets based on their sampled elements. Compared with the well-known sketch method MinHash [16], which is used to estimate set Jaccard similarity, OPH reduces the time complexity of processing each element in set $N_u$ from $O\left(k\right)$ to $O\left(1\right)$. In detail, to build a sketch of set $N_u\subseteq W$, OPH [17] uses a single permutation function $\pi (·):W\to W$ to process each element in a set $N_u$. Specifically, it evenly divides $W=\{1,\dots ,p\}$ into k bins: $W_j=\left\{⌊\frac{p(j-1)}{k}+1⌋,\dots ,⌊\frac{pj}{k}⌋\right\}$, $1\le j\le k$. The OPH sketch of set $N_u$ is a vector ${\overrightarrow{x}}_u={(x_{u,1},\dots ,x_{u,k})}^{\mathsf{T}}$, where each element $x_{u,j}$, $1\le j\le k$, is computed as

$$x_{u,j}=\left\{\begin{array}{cc}\underset{w\in N_u\wedge \pi \left(w\right)\in W_j}{min}\pi \left(w\right),\hfill & \exists w\in N_u,\pi \left(w\right)\in W_j\hfill \\ \varnothing ,\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

Given that at least one of $x_{u,j}$ and $x_{v,j}$ does not equal ∅ Li et al. [17] observed that $x_{u,j}=x_{v,j}$ occurs with probability $J_{u,v}$, and proposed estimating $J_{u,v}$ based on this observation. Let $\mathbf{1}\left(\mathbb{P}\right)$ be the indicator function that equals one when the predicate $\mathbb{P}$ is true, and zero otherwise. Formally, OPH estimates the Jaccard similarity $J_{u,v}$ of two sets $N_u$ and $N_v$ based on their OPH sketches ${\overrightarrow{x}}_u$ and ${\overrightarrow{x}}_v$ as

$${\widehat{J}}_{u,v}=\frac{{\sum }_{i=1}^k\mathbf{1}(x_{u,i}=x_{v,i}\wedge x_{u,i}\ne \varnothing \wedge x_{v,i}\ne \varnothing )}{{\sum }_{i=1}^k\mathbf{1}(x_{u,i}\ne \varnothing \vee x_{v,i}\ne \varnothing )}.$$

As shown in Algorithm 1, one can apply the above OPH algorithm online to stream $\mathrm{\Gamma }$ and compute the OPH sketch of each user’s interest set $N_u$, $u\in U$.

Algorithm 1: Online update procedure of OPH [17].

4.3. Optimal Densification

Clearly, the OPH method generates sketches (i.e., vectors) that may have empty elements (i.e., elements equal ∅), which hinders its application for LSH-based similarity search with sub-linear time, and also results in a large error in the Jaccard similarity estimation. To solve this problem, refs. [20,21,22] proposed several densification techniques, which reassign empty elements using the values of non-empty elements. The state-of-the-art densification technique, optimal densification [22], is shown in Algorithm 2. Specifically, when the $i^{\mathrm{th}}$ element of OPH sketch ${\overrightarrow{x}}_u$ is empty (i.e., $x_{u,i}=\varnothing$), optimal densification iteratively uses a hash function $j=h(i,l):\{1,\dots ,k\}\times \{1,2,\dots ,\}\to \{1,\dots ,k\}$, to find a non-empty element $x_{u,j}$ (i.e., $x_{u,j}\ne \varnothing$). Function $h(i,l)$ takes two arguments: (1) i, the current empty element that needs to be reassigned; (2) l, the number of failed attempts made so far to reach a non-empty element, which is initialized to 1. Let ${\overrightarrow{x}}_u^{*}$ denote the optimal densification of OPH sketch ${\overrightarrow{x}}_u$. For any sets $N_u$ and $N_v$, their Jaccard similarity $J_{u,v}$ is estimated as

$${\widehat{J}}_{u,v}^{*}=\frac{{\sum }_{i=1}^k\mathbf{1}(x_{u,i}^{*}=x_{v,i}^{*})}{k}.$$

Shrivastava [22] proves that ${\widehat{J}}_{u,v}^{*}$ is an unbiased estimator of $J_{u,v}$ and is more accurate than the original OPH method, as well as other densificiation techniques in [20,21].

Algorithm 2: Optimal densification [22].

5. Our Framework SimCar

In this section, we use Giroire’s algorithm [6] (Algorithm 3) to build an OH sketch for each occurring user. Based on generated OH sketches, we first present our methods for estimating the Jaccard similarity of users’ interest sets and quickly searching users with similar interests. Then, we propose methods for estimating the cardinalities and common-interest counts of users’ interest sets.

Algorithm 3: The CORE algorithm [59].

5.1. Jaccard Similarity Estimation and Nearest Neighbor Search

Jaccard Similarity Estimation. Let ${\overrightarrow{x}}_u^{(*)}$ be the DOH sketch of OH sketch ${\overrightarrow{x}}_u$, $u\in U$, which is computed using the optimal densification technique introduced in Section 4. Similar to optimal densification [22], we find that $P(x_{u,i}^{*}=x_{v,i}^{*})=J_{u,v}$ for any $1\le i\le k$. Then, we estimate the Jaccard similarity of $J_{u,v}$ as

$${\widehat{J}}_{u,v}^{*}=\frac{{\sum }_{i=1}^k\mathbf{1}(x_{u,i}^{*}=x_{v,i}^{*})}{k}.$$

Following the error analysis in [22], we find that ${\widehat{J}}_{u,v}^{*}$ is an unbiased estimate of $J_{u,v}$ and has the same accurate performance as the optimal densification of OPH.

Nearest Neighbor Search. A variety of LSH methods [16,23,24,25,26] have been developed to solve the task of nearest neighbor search with sub-linear time. The basic idea behind these LSH methods is to place similar users into the same bucket of a hash table with high probability. Following the principle of LSH, our nearest neighbor search method consists of two basic phases:

• Pre-processing phase. We first construct b hash tables ${\mathbb{H}}_1,\dots ,{\mathbb{H}}_b$ for all users in U. Let $k=bc$, where c is an integer parameter used to determine the performance of LSH. Let ${\overrightarrow{x}}_u^{(*,i,c)}$, $1\le i\le b$, denote the vector consisting of the ${((i-1)c+1)}^{\mathrm{th}}$ to ${\left(ic\right)}^{\mathrm{th}}$ elements of DOH sketch ${\overrightarrow{x}}_u^{*}$, i.e., ${\overrightarrow{x}}_u^{(*,i,c)}={(x_{u,(i-1)c+1}^{*},\dots ,x_{u,ic}^{*})}^{\mathsf{T}}$. Then, we insert each user u and its densification sketch ${\overrightarrow{x}}_u^{*}$ into hash tables ${\mathbb{H}}_1,\dots ,{\mathbb{H}}_b$ as

  $${\mathbb{H}}_i\left[{\overrightarrow{x}}_u^{(*,i,c)}\right]\leftarrow {\mathbb{H}}_i\left[{\overrightarrow{x}}_u^{(*,i,c)}\right]\cup \left\{u\right\},1\le i\le b.$$
• Retrieving phase. Given a specific user u, we search for its similar users. Instead of scanning all users in set U, we only probe b different buckets ${\mathbb{H}}_1\left[{\overrightarrow{x}}_u^{(*,i,c)}\right],\dots ,{\mathbb{H}}_b\left[{\overrightarrow{x}}_u^{(*,i,c)}\right]$ from b hash tables, respectively, and report the users in any of these buckets as the potential candidates. Last, nearest neighbors of user u are detected by enumerating all users in set ${\mathbb{H}}_1\left[{\overrightarrow{x}}_u^{(*,i,c)}\right]\cup \dots \cup {\mathbb{H}}_b\left[{\overrightarrow{x}}_u^{(*,i,c)}\right]$, and computing and sorting their Jaccard similarity estimations.

5.2. User Cardinality Estimation

In this section, we estimate the cardinality of any queried user. Specially, we first build a probabilistic model according to the state of the OH sketch, and then solve it using MLE methods.

Exact probabilistic model. For any user $u\in U$, let $N_{u,i}$ denote the set of its interests whose hash values equal i with respect to hash function f; that is,

$$N_{u,i}=\{w:i_w=i,w\in N_u\},1\le i\le k.$$

At any time of stream $\mathrm{\Gamma }$, from Equation (1), we have

$$x_{u,i}=\underset{w\in N_{u,i}}{min}{r}_{w}k-\lfloor r_{w}k\rfloor .$$

Define $d_{u,i}=\left|N_{u,i}\right|$. Let $f(x_{u,i}=x|d_{u,i}=d)$ denote the probability density function (PDF) of random variable $x_{u,i}$ at x given $d_{u,i}=d$. Then, we have

$$f(x_{u,i}=x|d_{u,i}=d)=\left\{\begin{array}{cc}d{(1-x)}^{d-1},\hfill & d>0\wedge 0<x<1\hfill \\ 1,\hfill & d=0\wedge x=1\hfill \\ 0,\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

Our algorithm randomly splits users in set $N_u$ into k subsets $N_{u,1}$, …, $N_{u,k}$. Using the classical balls-in-urns model, we derive the probability distribution of vector $(d_{u,1},\dots ,d_{u,k})$ as

$$P(d_{u,1},\dots ,d_{u,k}|d_u)=\frac{\left(\genfrac{}{}{0pt}{}{d_u}{d_{u,1},\dots ,d_{u,k}}\right)}{k^{d_u}},$$

where $\left(\genfrac{}{}{0pt}{}{d_u}{d_{u,1},\dots ,d_{u,k}}\right)=\frac{d_u!}{d_{u,1}!\cdots d_{u,k}!}$. Therefore, the PDF of ${\overrightarrow{x}}_u$ given $d_u$ is computed as

$$f\left({\overrightarrow{x}}_u\right|d_u)=\sum _{d_{u,1}+\dots +d_{u,k}=d_u}\frac{\left(\genfrac{}{}{0pt}{}{d_u}{d_{u,1},\dots ,d_{u,k}}\right)}{k^{d_u}}\prod _{i=1}^{k}f\left(x_{u,i}\right|d_{u,i}).$$

Poisson approximation model. Clearly, $d_{u,1},\dots ,d_{u,k}$ are not independent, which hinders us when it comes to obtaining the MLE of $d_u$. Similar to [5], we use the Poisson approximation technique to remove the dependence of $d_{u,1},\dots ,d_{u,k}$. Specifically, we assume that the value of $d_u$ is distributed according to a Poisson distribution with parameter ${\lambda }_u$, i.e., $d_u\sim \mathrm{Poisson}\left({\lambda }_u\right)$. Then, the PDF of ${\overrightarrow{x}}_u$ given ${\lambda }_u$ is

$$\begin{array}{cc}\hfill & f\left({\overrightarrow{x}}_u\right|{\lambda }_u)=\sum _{d=0}^{+\infty }ℒ\left({\overrightarrow{x}}_u\right|d_u)\frac{e^{-{\lambda }_u}{\lambda }_u^{d_u}}{d_u!}\hfill \\ \hfill & =\sum _{d_u=0}^{+\infty }\sum _{d_{u,1}+\dots +d_{u,k}=d_u}\frac{\left(\genfrac{}{}{0pt}{}{d_u}{d_{u,1},\dots ,d_{u,k}}\right)}{k^{d_u}}\prod _{i=1}^{k}f\left(x_{u,i}\right|d_{u,i})\frac{e^{-{\lambda }_u}{\lambda }_u^{d_u}}{d_u!}\hfill \\ \hfill & =\sum _{d_{u,1}=0}^{+\infty }\dots \sum _{d_{u,k}=0}^{+\infty }\prod _{i=1}^{k}f\left(x_{u,i}\right|d_{u,i})\frac{e^{-\frac{{\lambda }_u}{k}}{\lambda }_u^{d_{u,i}}}{d_{u,i}!k^{d_{u,i}}}\hfill \\ \hfill & =\prod _{i=1}^k\sum _{d_{u,i}=0}^{+\infty }f\left(x_{u,i}\right|d_{u,i})\frac{e^{-\frac{{\lambda }_u}{k}}{\lambda }_u^{d_{u,i}}}{d_{u,i}!k^{d_{u,i}}}\hfill \\ \hfill & =\prod _{i=1}^{k}f\left(x_{u,i}\right|{\lambda }_u).\hfill \end{array}$$

Given $d_u\sim \mathrm{Poisson}\left({\lambda }_u\right)$, the above equation indicates that the values of $x_{u,1},\dots ,x_{u,k}$ are independent and identically distributed. In addition, the values of $d_{u,1},\dots ,d_{u,k}$ are independent and identically distributed according to a Poisson distribution $\mathrm{Poisson}\left(\frac{{\lambda }_u}{k}\right)$. Formally, we have

$$d_{u,i}\sim \mathrm{Poisson}\left(\frac{{\lambda }_u}{k}\right),i=1,\dots ,k.$$

(2)

For an estimator $\varphi \left({\overrightarrow{x}}_u\right)$ of $d_u$ (e.g., Equation (5), derived later), we let ${\mathbb{E}}_{d_u}\left(\varphi \left({\overrightarrow{x}}_u\right)\right)$ and ${\mathrm{Var}}_{d_u}\left(\varphi \left({\overrightarrow{x}}_u\right)\right)$ denote the expectation and the variance of $\varphi \left({\overrightarrow{x}}_u\right)$ under the exact probabilistic model (i.e., $f\left({\overrightarrow{x}}_u\right|d_u)$), and let ${\mathbb{E}}_{\mathrm{Poisson}\left({\lambda }_u\right)}\left(\varphi \left({\overrightarrow{x}}_u\right)\right)$ and ${\mathrm{Var}}_{\mathrm{Poisson}\left({\lambda }_u\right)}\left(\varphi \left({\overrightarrow{x}}_u\right)\right)$ denote the expectation and the variance of $\varphi \left({\overrightarrow{x}}_u\right)$ under the Poisson approximation model (i.e., $f\left({\overrightarrow{x}}_u\right|d_u)$). The authors of [5,68,69] reveal that statistical properties of ${\mathbb{E}}_{d_u}\left(\varphi \left({\overrightarrow{x}}_u\right)\right)$ and ${\mathrm{Var}}_{d_u}\left(\varphi \left({\overrightarrow{x}}_u\right)\right)$ are well approximated by ${\mathbb{E}}_{\mathrm{Poisson}\left({\lambda }_u\right)}\left(\varphi \left({\overrightarrow{x}}_u\right)\right)$ and ${\mathrm{Var}}_{\mathrm{Poisson}\left({\lambda }_u\right)}\left(\varphi \left({\overrightarrow{x}}_u\right)\right)$ when setting ${\lambda }_u=d_u$, which is the depoissonization step.

Estimator of ${\lambda }_u$. Next, we elaborate our method to derive the MLE of ${\lambda }_u$ under the Poisson approximation model. For any $0<x<1$, the following equation holds

$$\begin{array}{cc}\hfill & f(x_{u,i}=x|{\lambda }_u)\hfill \\ \hfill =& \sum _{d_{u,i}=0}^{+\infty }f(x_{u,i}=x|d_{u,i})\frac{e^{-\frac{{\lambda }_u}{k}}{\lambda }_u^{d_{u,i}}}{d_{u,i}!k^{d_{u,i}}}\hfill \\ \hfill =& e^{-\frac{{\lambda }_u}{k}}+\sum _{d_{u,i}=1}^{\infty }{d}_{u,i}{(1-x)}^{d_{u,i}-1}\frac{e^{-\frac{{\lambda }_u}{k}}{\lambda }_u^{d_{u,i}}}{d_{u,i}!k^{d_{u,i}}}\hfill \\ \hfill =& \frac{{\lambda }_u}{k}{e}^{-\frac{{\lambda }_{u}x}{k}},\hfill \end{array}$$

(3)

where the last equation holds because of the Taylor series of $\frac{{\lambda }_u}{k}{e}^{-\frac{{\lambda }_{u}x}{k}}$ at $x_0=1$. Then, we compute the PDF of $x_{u,i}$ at x given ${\lambda }_u$ as

$$f(x_{u,i}=x|{\lambda }_u)=\left\{\begin{array}{cc}\frac{{\lambda }_u}{k}{e}^{-\frac{{\lambda }_{u}x}{k}},\hfill & 0<x<1\hfill \\ e^{-\frac{{\lambda }_u}{k}},\hfill & x=1.\hfill \end{array}\right.$$

(4)

The last equation holds because we have $d_{u,i}=0$ when $x=1$, which occurs with probability $P(d_{u,i}=0|{\lambda }_u)=e^{-\frac{{\lambda }_u}{k}}$. Let ${\mathsf{\Phi }}_u$ denote the set of elements in vector ${\overrightarrow{x}}_u$ that are smaller than 1, i.e.,

$${\Phi }_u=\{i:x_{u,i}<1,1\le i\le k\}.$$

Denoted by $k_u$ is the number of elements in vector ${\overrightarrow{x}}_u$ that equal 1. Then, the likelihood function of ${\lambda }_u$ given by k independent observed variables $x_{u,1},\dots ,x_{u,k}$ is computed as

$$\begin{array}{cc}\hfill ℒ\left({\overrightarrow{x}}_u\right|{\lambda }_u)& =\prod _{i=1}^{k}f\left(x_{u,i}\right|{\lambda }_u)\hfill \\ \hfill & =e^{-\frac{{\lambda }_u{k}_u}{k}}\prod _{i\in {\mathrm{\Phi }}_u}\frac{{\lambda }_u}{k}{e}^{-\frac{{\lambda }_u{x}_{u,i}}{k}}\hfill \\ \hfill & ={\left(\frac{{\lambda }_u}{k}\right)}^{k-k_u}{e}^{-\frac{{\lambda }_u(k_u+{\sum }_{i\in {\mathrm{\Phi }}_u}{x}_{u,i})}{k}}\hfill \\ \hfill & ={\left(\frac{{\lambda }_u}{k}\right)}^{k-k_u}{e}^{-\frac{{\lambda }_u{\sum }_{i=1}^k{x}_{u,i}}{k}}.\hfill \end{array}$$

Let ${\widehat{\lambda }}_u=arg{max}_{{\lambda }_u}log\mathcal{L}\left({\overrightarrow{x}}_u\right|{\lambda }_u)$ denote the MLE of ${\lambda }_u$. We compute the derivative of $log\mathcal{L}\left({\overrightarrow{x}}_u\right|{\lambda }_u)$ as

$$\frac{\partial log\mathcal{L}\left({\overrightarrow{x}}_u\right|{\lambda }_u)}{\partial {\lambda }_u}=\frac{k-k_u}{{\lambda }_u}-\frac{{\sum }_{i=1}^k{x}_{u,i}}{k}.$$

Let $\frac{\partial log\mathcal{L}\left({\overrightarrow{x}}_u\right|{\lambda }_u)}{\partial {\lambda }_u}=0$. Then, we obtain the MLE of ${\lambda }_u$ as

$${\widehat{\lambda }}_u=\frac{k(k-k_u)}{{\sum }_{i=1}^k{x}_{u,i}}.$$

(5)

To analyze the estimation error of ${\widehat{\lambda }}_u$, we first compute the Fisher information of ${\lambda }_u$ as

$$\begin{array}{cc}\hfill \mathcal{I}\left({\lambda }_u\right)& =-\mathbb{E}\left(\frac{{\partial }^{2}log\mathcal{L}\left({\overrightarrow{x}}_u\right|{\lambda }_u)}{\partial {\lambda }_u^2}\right)\hfill \\ \hfill & =\mathbb{E}\left(\frac{k-k_u}{{\lambda }_u^2}\mid {\lambda }_u\right)\hfill \\ \hfill & =\frac{k(1-e^{-\frac{{\lambda }_u}{k}})}{{\lambda }_u^2}.\hfill \end{array}$$

The last equation is obtained because $\mathbb{E}\left(k_u\right|{\lambda }_u)=k{e}^{-\frac{{\lambda }_u}{k}}$, which is easily derived from Equation (4). From [70], we find that the MLE ${\widehat{\lambda }}_u$ is an asymptotically efficient unbiased estimator of ${\lambda }_u$, and its mean square error (MSE) asymptotically approaches the Cramér–Rao lower bound (CRLB) of ${\lambda }_u$, which is defined as $\frac{1}{\mathcal{I}\left({\lambda }_u\right)}$. Formally, we have ${lim}_{k\to +\infty }{\widehat{\lambda }}_u\to {\lambda }_u$ and ${lim}_{k\to +\infty }\mathrm{MSE}\left({\widehat{\lambda }}_u\right)\to \frac{1}{\mathcal{I}\left({\lambda }_u\right)}$. Lastly, at the depoissonization step, we use ${\widehat{\lambda }}_u$ to approximate $d_u$. In our experiments, we will show that the above MLE estimator is more accurate than the Giroire’s algorithm (Section 4.1), especially for small cardinalities.

5.3. Common-Interest Count Estimation

Similarly, we use the MLE and Poisson approximation techniques to estimate the common-interest count $d_{u\cap v}$ of any two users $u,v\in U$. Specifically, we assume

$$d_{u\cap v}\sim \mathrm{Poisson}\left({\lambda }_{u,v}\right).$$

Define $N_{u\setminus v}=N_u\setminus N_v$ and $N_{v\setminus u}=N_v\setminus N_u$. Let $d_{u\setminus v}=\left|N_{u\setminus v}\right|$ and $d_{v\setminus u}=\left|N_{v\setminus u}\right|$. We also assume

$$d_{u\setminus v}\sim \mathrm{Poisson}({\lambda }_u-{\lambda }_{u,v}),$$

$$d_{v\setminus u}\sim \mathrm{Poisson}({\lambda }_v-{\lambda }_{u,v}),$$

where ${\lambda }_u\ge {\lambda }_{u,v}$ and ${\lambda }_v\ge {\lambda }_{u,v}$. Similar to $N_{u,i},1\le i\le k$, we define

$$N_{u\cap v,i}=\{w:i_w=i,w\in N_{u\cap v}\},$$

$$N_{u\setminus v,i}=\{w:i_w=i,w\in N_{u\setminus v}\},$$

$$N_{v\setminus u,i}=\{w:i_w=i,w\in N_{v\setminus u}\}.$$

Let $d_{u\cap v,i}=\left|N_{u\cap v,i}\right|$, $d_{u\setminus v,i}=\left|N_{u\setminus v,i}\right|$, and $d_{v\setminus u,i}=\left|N_{v\setminus u,i}\right|$. Similar to Equation (2), we find that $d_{u\cap v,1}$, …, $d_{u\cap v,k}$, $d_{u\setminus v,1}$, …, $d_{u\setminus v,k}$, $d_{v\setminus u,1}$, …, $d_{v\setminus u,k}$ are independent, and they are distributed according to the following Poisson distributions

$$d_{u\cap v,i}\sim \mathrm{Poisson}\left(\frac{{\lambda }_{u,v}}{k}\right),$$

$$d_{u\setminus v,i}\sim \mathrm{Poisson}\left(\frac{{\lambda }_u-{\lambda }_{u,v}}{k}\right),$$

$$d_{v\setminus v,i}\sim \mathrm{Poisson}\left(\frac{{\lambda }_v-{\lambda }_{u,v}}{k}\right).$$

Define $x_{u\cap v,i}={min}_{w\in N_{u\cap v,i}}{r}_w$, $x_{u\setminus v,i}={min}_{w\in N_{u\setminus v,i}}{r}_w$, and $x_{v\setminus u,i}={min}_{w\in N_{v\setminus u,i}}{r}_w$. Then, we find that

$$x_{u,i}=min(x_{u\cap v,i},x_{u\setminus v,i}),$$

$$x_{v,i}=min(x_{u\cap v,i},x_{v\setminus u,i}).$$

Let $f(x_{u,i}=x,x_{v,i}=x^{\prime }|{\lambda }_u,{\lambda }_v,{\lambda }_{u,v})$ denote the PDF of the random variable pair $(x_{u,i},x_{v,i})$ at $(x,x^{\prime })$, given ${\lambda }_u$, ${\lambda }_v$, and ${\lambda }_{u,v}$. In what follows, we omit the conditions ${\lambda }_u$, ${\lambda }_v$, and ${\lambda }_{u,v}$ for simplicity when no confusion is raised. We derive $f(x_{u,i}=x,x_{v,i}=x^{\prime })$ for all possible relations between $x_{u,i}$ and $x_{v,i}$ as follows:

Case 1:$x_{u,i}=x_{v,i}=1$. This case indicates $d_{u\cap v,i}=d_{u\setminus v,i}=d_{v\setminus u,i}=0$. Therefore, we have

$$\begin{array}{cc}\hfill & f(x_{u,i}=1,x_{v,i}=1)\hfill \\ \hfill & =P(d_{u\cap v,i}=0)P(d_{u\setminus v,i}=0)P(d_{v\setminus u,i}=0)\hfill \\ \hfill & =e^{-\frac{{\lambda }_{u,v}}{k}}{e}^{-\frac{{\lambda }_u-{\lambda }_{u,v}}{k}}{e}^{-\frac{{\lambda }_v-{\lambda }_{u,v}}{k}}\hfill \\ \hfill & =e^{-\frac{{\lambda }_u+{\lambda }_v-{\lambda }_{u,v}}{k}}.\hfill \end{array}$$

(6)

Case 2:$x_{u,i}=1\wedge 0<x_{v,i}<1$.This case indicates $d_{u\cap v,i}=d_{u\setminus v,i}=0$ and $0<x_{v\setminus u,i}=x_{v,i}<1$. Similar to Equation (4), we have $f(x_{v\setminus u,i}=x)=\frac{{\lambda }_v-{\lambda }_{u,v}}{k}{e}^{-\frac{({\lambda }_v-{\lambda }_{u,v})x}{k}}$. Then, we have

$$\begin{array}{cc}\hfill & f(x_{u,i}=1,x_{v,i}=x)\hfill \\ \hfill & =f(x_{v\setminus u,i}=x)P(d_{u\cap v,i}=0)P(d_{u\setminus v,i}=0)\hfill \\ \hfill & =\frac{{\lambda }_v-{\lambda }_{u,v}}{k}{e}^{-\frac{{\lambda }_u+({\lambda }_v-{\lambda }_{u,v})x}{k}},0<x<1.\hfill \end{array}$$

(7)

Case 3:$0<x_{u,i}<1\wedge x_{v,i}=1$. Similar to Case 2, we have

$$\begin{array}{cc}\hfill & f(x_{u,i}=x,x_{v,i}=1)\hfill \\ \hfill & =f(x_{u\setminus v,i}=x)P(d_{u\cap v,i}=0)P(d_{v\setminus u,i}=0)\hfill \\ \hfill & =\frac{{\lambda }_u-{\lambda }_{u,v}}{k}{e}^{-\frac{{\lambda }_v+({\lambda }_u-{\lambda }_{u,v})x}{k}},0<x<1.\hfill \end{array}$$

(8)

Case 4:$0<x_{u,i}=x_{v,i}<1$. This case indicates that $x_{u\cap v,i}<x_{u\setminus v,i}$ and $x_{u\cap v,i}<x_{v\setminus u,i}$. Similar to Equation (4), we obtain $f(x_{u\cap v,i}=x)=\frac{{\lambda }_{u,v}}{k}{e}^{-\frac{{\lambda }_{u,v}x}{k}}$, $f(x_{u\setminus v,i}>x)=e^{-\frac{({\lambda }_u-{\lambda }_{u,v})x}{k}}$, and $f(x_{v\setminus u,i}>x)=e^{-\frac{({\lambda }_v-{\lambda }_{u,v})x}{k}}$. Therefore, we have

$$\begin{array}{cc}\hfill & f(x_{u,i}=x,x_{v,i}=x)\hfill \\ \hfill & =f(x_{u\cap v,i}=x)f(x_{u\setminus v,i}>x)f(x_{v\setminus u,i}>x)\hfill \\ \hfill & =\frac{{\lambda }_{u,v}}{k}{e}^{-\frac{({\lambda }_u+{\lambda }_v-{\lambda }_{u,v})x}{k}},0<x<1.\hfill \end{array}$$

(9)

Case 5:$0<x_{u,i}<x_{v,i}<1$. This case indicates that $x_{u\setminus v,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 \mathrm{Poisson}\left(\frac{{\lambda }_v}{k}\right)$, and $f(min(x_{u\cap v,i},x_{v\setminus u,i})=x^{\prime })=\frac{{\lambda }_v}{k}{e}^{-\frac{{\lambda }_v{x}^{\prime }}{k}}$. Therefore, we have

$$\begin{array}{cc}\hfill & f(x_{u,i}=x,x_{v,i}=x^{\prime })\hfill \\ \hfill & =f(x_{u\setminus v,i}=x)f(min(x_{u\cap v,i},x_{v\setminus u,i})=x^{\prime })\hfill \\ \hfill & =\frac{({\lambda }_u-{\lambda }_{u,v}){\lambda }_v}{k^2}{e}^{-\frac{({\lambda }_u-{\lambda }_{u,v})x+{\lambda }_v{x}^{\prime }}{k}},0<x<x^{\prime }<1.\hfill \end{array}$$

(10)

Case 6:$0<x_{v,i}<x_{u,i}<1$. Similar to Case 5, we have

$$\begin{array}{cc}\hfill & f(x_{u,i}=x,x_{v,i}=x^{\prime })\hfill \\ \hfill & =f(min(x_{u\cap v,i},x_{u\setminus v,i})=x)f(x_{v\setminus u,i}=x^{\prime })\hfill \\ \hfill & =\frac{({\lambda }_v-{\lambda }_{u,v}){\lambda }_u}{k^2}{e}^{-\frac{({\lambda }_v-{\lambda }_{u,v})x^{\prime }+{\lambda }_{u}x}{k}},0<x^{\prime }<x<1.\hfill \end{array}$$

(11)

Let ${\mathrm{\Phi }}_{u,v}^{\left(j\right)}$ denote the set of integers $i\in \{1,\dots ,k\}$, such that the relation between $x_{u,i}$ and $x_{v,i}$ is Case j, $1\le j\le 6$. Define $k_{u,v}^{\left(j\right)}=\left|{\mathrm{\Phi }}_{u,v}^{\left(j\right)}\right|$. Then, we have $k_u=k_{u,v}^{\left(1\right)}+k_{u,v}^{\left(2\right)}$, $k_v=k_{u,v}^{\left(1\right)}+k_{u,v}^{\left(3\right)}$, ${\mathrm{\Phi }}_u={\mathrm{\Phi }}_{u,v}^{\left(3\right)}\cup {\mathrm{\Phi }}_{u,v}^{\left(4\right)}\cup {\mathrm{\Phi }}_{u,v}^{\left(5\right)}\cup {\mathrm{\Phi }}_{u,v}^{\left(6\right)}$, and ${\mathrm{\Phi }}_v={\mathrm{\Phi }}_{u,v}^{\left(2\right)}\cup {\mathrm{\Phi }}_{u,v}^{\left(4\right)}\cup {\mathrm{\Phi }}_{u,v}^{\left(5\right)}\cup {\mathrm{\Phi }}_{u,v}^{\left(6\right)}$. Now, we obtain the likelihood function of $\overrightarrow{\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{array}{cc}\hfill & \mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)={\Pi }_{i=1}^{k}f(x_{u,i},x_{v,i})=e^{-\frac{({\lambda }_u+{\lambda }_v-{\lambda }_{u,v})k_{u,v}^{\left(1\right)}}{k}}\hfill \\ \hfill & \times {\left(\frac{{\lambda }_v-{\lambda }_{u,v}}{k}\right)}^{k_{u,v}^{\left(2\right)}}{e}^{-\frac{{\lambda }_u{k}_{u,v}^{\left(2\right)}+({\lambda }_v-{\lambda }_{u,v}){\sum }_{i\in {\mathrm{\Phi }}_{u,v}^{\left(2\right)}}{x}_{v,i}}{k}}\hfill \\ \hfill & \times {\left(\frac{{\lambda }_u-{\lambda }_{u,v}}{k}\right)}^{k_{u,v}^{\left(3\right)}}{e}^{-\frac{{\lambda }_v{k}_{u,v}^{\left(3\right)}+({\lambda }_u-{\lambda }_{u,v}){\sum }_{i\in {\mathrm{\Phi }}_{u,v}^{\left(3\right)}}{x}_{u,i}}{k}}\hfill \\ \hfill & \times {\left(\frac{{\lambda }_{u,v}}{k}\right)}^{k_{u,v}^{\left(4\right)}}{e}^{-\frac{({\lambda }_u+{\lambda }_v-{\lambda }_{u,v}){\sum }_{i\in {\mathrm{\Phi }}_{u,v}^{\left(4\right)}}{x}_{u,i}}{k}}\hfill \\ \hfill & \times {\left(\frac{({\lambda }_u-{\lambda }_{u,v}){\lambda }_v}{k^2}\right)}^{k_{u,v}^{\left(5\right)}}{e}^{-\frac{{\sum }_{i\in {\mathrm{\Phi }}_{u,v}^{\left(5\right)}}({\lambda }_u-{\lambda }_{u,v})x_{u,i}+{\lambda }_v{x}_{v,i}}{k}}\hfill \end{array}$$

$$\begin{array}{cc}\hfill & \times {\left(\frac{({\lambda }_v-{\lambda }_{u,v}){\lambda }_u}{k^2}\right)}^{k_{u,v}^{\left(6\right)}}{e}^{-\frac{{\sum }_{i\in {\mathrm{\Phi }}_{u,v}^{\left(6\right)}}({\lambda }_v-{\lambda }_{u,v})x_{v,i}+{\lambda }_u{x}_{u,i}}{k}}\hfill \\ \hfill =& e^{-\frac{{\lambda }_u{\sum }_{i=1}^k{x}_{u,i}}{k}}{e}^{-\frac{{\lambda }_v{\sum }_{i=1}^k{x}_{v,i}}{k}}{e}^{\frac{{\lambda }_{u,v}{\sum }_{i=1}^{k}min(x_{u,i},x_{v,i})}{k}}\hfill \\ \hfill & \times {\left(\frac{{\lambda }_u-{\lambda }_{u,v}}{k}\right)}^{k_{u,v}^{\left(3\right)}+k_{u,v}^{\left(5\right)}}{\left(\frac{{\lambda }_v-{\lambda }_{u,v}}{k}\right)}^{k_{u,v}^{\left(2\right)}+k_{u,v}^{\left(6\right)}}\hfill \\ \hfill & \times {\left(\frac{{\lambda }_u}{k}\right)}^{k_{u,v}^{\left(6\right)}}{\left(\frac{{\lambda }_v}{k}\right)}^{k_{u,v}^{\left(5\right)}}{\left(\frac{{\lambda }_{u,v}}{k}\right)}^{k_{u,v}^{\left(4\right)}}.\hfill \end{array}$$

We use the Newton–Raphson method [71] to compute the MLE of $\overrightarrow{\lambda }=({\lambda }_u,{\lambda }_v,{\lambda }_{u,v})$, i.e., $\widehat{\overrightarrow{\lambda }}=arg{max}_{\overrightarrow{\lambda }}\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)$. The Newton–Raphson method starts from an initial estimation, ${\overrightarrow{\lambda }}^{\left(0\right)}$, and then repeats the following procedure

$${\overrightarrow{\lambda }}^{(l+1)}\leftarrow {\overrightarrow{\lambda }}^{\left(l\right)}-{\left(H\left({\overrightarrow{\lambda }}^{\left(l\right)}\right)\right)}^{-1}g\left({\overrightarrow{\lambda }}^{\left(l\right)}\right),$$

until a sufficiently accurate root of function $g\left(\overrightarrow{\lambda }\right)={(0,0,0)}^{\mathsf{T}}$ is reached, where $g\left(\overrightarrow{\lambda }\right)$ and $H\left(\overrightarrow{\lambda }\right)$ are the gradient and the Hessian matrix of $log\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)$ at $\overrightarrow{\lambda }$ is defined as

$$\begin{array}{cc}\hfill & g\left(\overrightarrow{\lambda }\right)=\hfill \\ \hfill & {\left(\frac{\partial log\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)}{\partial {\lambda }_u},\frac{\partial log\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)}{\partial {\lambda }_v},\frac{\partial log\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)}{\partial {\lambda }_{u,v}}\right)}^{\mathsf{T}},\hfill \end{array}$$

$$H\left(\overrightarrow{\lambda }\right)=\left[\begin{array}{ccc}\frac{{\partial }^{2}log\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)}{\partial {\lambda }_u^2},\hfill & \frac{{\partial }^{2}log\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)}{\partial {\lambda }_u\partial {\lambda }_v},\hfill & \frac{{\partial }^{2}log\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)}{\partial {\lambda }_u\partial {\lambda }_{u,v}}\hfill \\ \frac{{\partial }^{2}log\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)}{\partial {\lambda }_v\partial {\lambda }_u},\hfill & \frac{{\partial }^{2}log\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)}{\partial {\lambda }_v^2},\hfill & \frac{{\partial }^{2}log\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)}{\partial {\lambda }_v\partial {\lambda }_{u,v}}\hfill \\ \frac{{\partial }^{2}log\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)}{\partial {\lambda }_{u,v}\partial {\lambda }_u},\hfill & \frac{{\partial }^{2}log\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)}{\partial {\lambda }_{u,v}\partial {\lambda }_v},\hfill & \frac{{\partial }^{2}log\mathcal{L}({\overrightarrow{x}}_u,{\overrightarrow{x}}_v)}{\partial {\lambda }_{u,v}^2}\hfill \end{array}\right].$$

The closed formulas of $g\left(\overrightarrow{\lambda }\right)$ and $H\left(\overrightarrow{\lambda }\right)$ are given in Appendix A. To set ${\overrightarrow{\lambda }}^{\left(0\right)}=({\lambda }_u^{\left(0\right)},$${\lambda }_v^{\left(0\right)},{\lambda }_{u,v}^{\left(0\right)}{)}^{\mathsf{T}}$, we initialize ${\lambda }_u^{\left(0\right)}$ and ${\lambda }_v^{\left(0\right)}$ using the estimates of ${\lambda }_u$ and ${\lambda }_v$ given in Section 5.2 (i.e., ${\lambda }_u^{\left(0\right)}=\frac{k(k-k_u)}{{\sum }_{i=1}^k{x}_{u,i}}$ and ${\lambda }_v^{\left(0\right)}=\frac{k(k-k_v)}{{\sum }_{i=1}^k{x}_{v,i}}$) and initialize ${\lambda }_{u,v}^{\left(0\right)}=\frac{{\widehat{J}}_{u,v}({\widehat{\lambda }}_u^{\left(0\right)}+{\lambda }_v^{\left(0\right)})}{{\widehat{J}}_{u,v}+1}$, where ${\widehat{J}}_{u,v}=\frac{{\sum }_{i=1}^k\mathbf{1}(x_{u,i}^{*}=x_{v,i}^{*})}{k}$ is an estimate of Jaccard similarity $J_{u,v}$, which is introduced in Section 5.1.

Next, we analyze the error of obtained MLE ${\widehat{\lambda }}_{u,v}^{*}$. The Fisher information matrix of $\overrightarrow{\lambda }$ is defined as

$$\mathcal{I}\left(\overrightarrow{\lambda }\right)=-\mathbb{E}\left(H\left(\overrightarrow{\lambda }\right)\right).$$

The closed formula of $\mathbb{E}\left(H\left(\overrightarrow{\lambda }\right)\right)$ is given in Appendix A. Let ${\left(\mathcal{I}\left(\overrightarrow{\lambda }\right)\right)}_{3,3}^{-1}$ be the $(3,3)$ element of the inverse of matrix $\mathcal{I}\left(\overrightarrow{\lambda }\right)$. From [70], we find that the MLE ${\widehat{\lambda }}_{u,v}^{*}$ is an asymptotically efficient unbiased estimator of ${\widehat{\lambda }}_{u,v}$, and its MSE asymptotically approaches the CRLB of ${\lambda }_{u,v}$, i.e., ${\left(\mathcal{I}\left(\overrightarrow{\lambda }\right)\right)}_{3,3}^{-1}$. Lastly, we use ${\widehat{\lambda }}_{u,v}^{*}$ to approximate $d_{u\cap v}$.

5.4. Space and Time Complexities

Complexities of online generating OH sketches. We use k registers for each occurring user in stream $\mathrm{\Gamma }$, and the time complexity of processing each element of stream $\mathrm{\Gamma }$ is $O\left(1\right)$.

Complexities of densification. No extra memory space is required for densification. From [22], we find that computing a user u’s DOH sketch from its OH sketch ${\overrightarrow{x}}_u$ requires time complexity $O\left(k(\frac{k_u}{k-k_u}+2)\right)$.

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\left(k\right)$.

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\left(k\right)$.

Complexities of Jaccard similarity estimation. No extra memory space is required for common-interest count estimation. Based on two users’ DOH sketches, time $O\left(k\right)$ is required when estimating two users’ Jaccard similarity.

Complexities of nearest neighbor search. Given DOH sketches of users in U, space $O\left(\right|U\left|b\right)$ and time $O\left(\right|U\left|b\right)$ are required for building LSH tables, and searching a query user’s nearest neighbors requires time $O(klog|U\left|\right)$.

6. Evaluation

In this section, we evaluate the runtime and accuracy of our framework, SimCar, compared to the state of the art. All experiments were run on the same machine with an Intel Xeon CPU E5-2620 v3 with 2.4 GHz, and all algorithms were implemented in Python.

6.1. Datasets

We performed our experiments on six real-world datasets from different areas. The dataset Flickr [72] is a bipartite network of Flickr users and their group memberships. The dataset Movie [73] is a bipartite network consisting of one million movie ratings from MovieLens (http://movielens.umn.edu/, accessed on 10 March 2022).

The dataset Wikipedia [74] is a bipartite network of excellent articles in the English Wikipedia (http://en.wikipedia.org/wiki/Wikipedia, accessed on 10 March 2022) which meet a core set of editorial standards, and the words they contain. The dataset Reuters [75] is a bipartite network of article-word inclusions in documents that appeared on Reuters newswire in 1987. The dataset Tropes [76] is a bipartite network of TV tropes (http://tvtropes.org, accessed on 10 March 2022), characterizing artistic works by their tropes. The dataset TREC [77] is a bipartite network of 1.7 million text documents from the Text Retrieval Conference’s (TREC) (http://trec.nist.gov/data/docs_eng.html, accessed on 10 March 2022), containing 556,000 words of different languages. The detailed statistics of these real-world datasets are summarized in Table 2.

Table 2. Real-world datasets used in our experiments, where “size” refers to the number of elements in the stream.

	# Users	# Interests	Size
Movie	6040	9746	1,000,209
Reuters	21,557	60,234	1,464,182
Tropes	152,093	64,415	3,232,134
Wikipedia	2780	276,739	7,846,807
Flickr	499,610	395,979	8,545,307
TREC	556,077	1,729,302	151,632,178

Table 2. Real-world datasets used in our experiments, where “size” refers to the number of elements in the stream.

	# Users	# Interests	Size
Movie	6040	9746	1,000,209
Reuters	21,557	60,234	1,464,182
Tropes	152,093	64,415	3,232,134
Wikipedia	2780	276,739	7,846,807
Flickr	499,610	395,979	8,545,307
TREC	556,077	1,729,302	151,632,178

6.2. 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 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 ${\widehat{d}}_u$, ${\widehat{d}}_v$, and ${\widehat{d}}_{u\cup v}$ of $d_u$, $d_v$, and $d_{u\cup v}=|N_u\cup N_v|$ from HLL sketches and our OH sketches; (2) estimation ${\widehat{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) ${\widehat{d}}_{u\cap v}={\widehat{d}}_u+{\widehat{d}}_v-{\widehat{d}}_{u\cup v}$; (scheme 2) ${\widehat{d}}_{u\cap v}={\widehat{J}}_{u,v}{\widehat{d}}_{u\cup v}$; (scheme 3) ${\widehat{d}}_{u\cap v}=\frac{{\widehat{J}}_{u,v}}{{\widehat{J}}_{u,v}+1}({\widehat{d}}_u+{\widehat{d}}_v)$. Similar to MinHash and HLL method [15], we initialize the parameter ${\overrightarrow{\lambda }}^{\left(0\right)}={({\lambda }_u^{\left(0\right)},{\lambda }_v^{\left(0\right)},{\lambda }_{u,v}^{\left(0\right)})}^{\mathsf{T}}={({\widehat{d}}_u,{\widehat{d}}_v,{\widehat{d}}_{u\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.

6.3. Metric

We evaluated both the efficiency and effectiveness of our method, SimCar, in comparison with the above two baseline methods. For efficiency, we evaluated the running time of all methods. Specially, we used the online sketching time to measure the time of online processing stream $\mathrm{\Gamma }$. For user cardinality estimation, common-interest count estimation, and Jaccard similarity estimation, we evaluated the error of estimation $\widehat{\mu }$ with respect to its true value $\mu$ using the normalized root mean square error (NRMSE), which is defined as $\mathrm{NRMSE}\left(\widehat{\mu }\right)=\sqrt{\mathrm{MSE}\left(\widehat{\mu }\right)}/\mu$, where $\mathrm{MSE}\left(\widehat{\mu }\right)=\mathbb{E}\left({(\widehat{\mu }-\mu )}^2\right)=\mathrm{Var}\left(\widehat{\mu }\right)+{\left(\mathbb{E}\left(\widehat{\mu }\right)-\mu \right)}^2$. For the nearest neighbor search, given a query user, we report the average size of the retrieved user set, as well as the recall of the top 10 most similar users among that set. In our experiments, we computed the above metrics over 100 independent runs.

6.4. Runtime

As shown in Figure 2a, where we set $k_1=k=2^9$, our framework, SimCar, significantly outperforms MinHash and HLL and OPH and HLL on all datasets in Table 2. For example, for Reuters, the online sketching time of SimCar is about 2 seconds, while MinHash and HLL and OPH and HLL need about 764 and $5.3$ seconds, respectively. On average, SimCar is about 400 and $2.5$ times faster than MinHash and HLL and OPH and HLL, respectively. Figure 2b shows the online sketching time for different k. We can see that the online sketching time of SimCar and OPH+HLL is almost constant, while the online sketching time of MinHash and HLL increases linearly to k, because Minhash needs to update each of its k registers when updating each element that occurs in stream $\mathrm{\Gamma }$.

6.5. 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\%$∼$40\%$ (resp. $10\%$∼$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 6a–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 $2k$, and the results are shown in Figure 6d–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\ge 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.

Table 3. Performance of our framework, SimCar, compared with MinHash and OPH for Jaccard similarity estimation and nearest neighbor search with $k=2^9$, $c=2$.

	Jaccard Similarity Estimation			Top 10 Nearest Neighbor Search
	NRMSE			Recall			the Number of Retrieved Users
	SimCar	MinHash	OPH	SimCar	MinHash	OPH	SimCar	MinHash	OPH
Reuters	0.177	0.175	0.176	0.732	0.735	0.732	151	156	151
Movie	0.072	0.072	0.073	0.800	0.800	0.800	599	597	598
Wikipedia	0.085	0.085	0.085	0.799	0.800	0.800	2395	2398	2395
Tropes	0.168	0.171	0.170	0.555	0.561	0.556	220	222	220
Flickr	0.172	0.175	0.174	0.765	0.764	0.764	299	301	299
Actor	0.240	0.235	0.239	0.740	0.734	0.739	174	175	175
TREC	0.076	0.077	0.077	0.894	0.896	0.894	219	227	220

Table 3. Performance of our framework, SimCar, compared with MinHash and OPH for Jaccard similarity estimation and nearest neighbor search with $k=2^9$, $c=2$.

	Jaccard Similarity Estimation			Top 10 Nearest Neighbor Search
	NRMSE			Recall			the Number of Retrieved Users
	SimCar	MinHash	OPH	SimCar	MinHash	OPH	SimCar	MinHash	OPH
Reuters	0.177	0.175	0.176	0.732	0.735	0.732	151	156	151
Movie	0.072	0.072	0.073	0.800	0.800	0.800	599	597	598
Wikipedia	0.085	0.085	0.085	0.799	0.800	0.800	2395	2398	2395
Tropes	0.168	0.171	0.170	0.555	0.561	0.556	220	222	220
Flickr	0.172	0.175	0.174	0.765	0.764	0.764	299	301	299
Actor	0.240	0.235	0.239	0.740	0.734	0.739	174	175	175
TREC	0.076	0.077	0.077	0.894	0.896	0.894	219	227	220

7. Conclusions and Future Work

In this paper, a framework—SimCar—was developed for mining users’ interest sets. We built an OH sketch for each user that occurred in the data stream of interest, and one can query several mining results of users’ interest sets at any time of the data stream. Specially, we developed accurate methods for estimating cardinalities, common-interest counts, and Jaccard similarities of users’ interest sets. In addition, we used OH sketches to build LSH tables to quickly search for users with similar interests with sub-linear time. We evaluated the performance of our methods on real-world datasets. The experimental results demonstrated the effectiveness and efficacy of our methods. In future, we plan to use techniques such as register sharing (i.e., compress the OH sketches of all users into a large register array) to further reduce the memory usage.