We develop the “generalized consistent weighted sampling” (GCWS) for hashing the “powered-GMM” (pGMM) kernel (with a tuning parameter $p$). It turns out that GCWS provides a numerically stable scheme for applying power transformation on the original data, regardless of the magnitude of $p$ and the data. The power transformation is often effective for boosting the performance, in many cases considerably so. We feed the hashed data to neural networks on a variety of public classification datasets and name our method “GCWSNet”. Our extensive experiments show that GCWSNet often improves the classification accuracy. Furthermore, it is evident from the experiments that GCWSNet converges substantially faster. In fact, GCWS often reaches a reasonable accuracy with merely (less than) one epoch of the training process. This property is much desired because many applications, such as advertisement click-through rate (CTR) prediction models, or data streams (i.e., data seen only once), often train just one epoch. Another beneficial side effect is that the computations of the first layer of the neural networks become additions instead of multiplications because the input data become binary (and highly sparse).

Empirical comparisons with (normalized) random Fourier features (NRFF) are provided. We also propose to reduce the model size of GCWSNet by count-sketch and develop the theory for analyzing the impact of using count-sketch  on the accuracy of GCWS. Our analysis shows that an “8-bit” strategy should work well in that we can always apply an 8-bit count-sketch hashing on the output of GCWS hashing without hurting the accuracy much. Note that the outputs of count-sketch on top of GCWS hashing are also integers meaning that a lot of multiplications in training neural nets can still be avoided.

There are many other ways to take advantage of GCWS when training deep neural networks. For example,  one can apply GCWS on the outputs of the last layer to boost the accuracy of trained deep neural networks. In our view, GCWS and variants are a gem which has not been exploited much in the machine learning community. We hope this work would generate more interest in pGMM, GCWS, and their variants, for research and industrial practice.  GCWSNet has been implemented with the PaddlePaddle <https://www.paddlepaddle.org.cn> deep learning platform.

§ INTRODUCTION

There has been a surge of interest in speeding up the training process of large-scale machine learning algorithms. For example, Weinberger et al., 2009 applied count-sketch type of randomized algorithms [Charikar et al., 2004] to approximate large-scale linear classifiers.  [Li et al., 2011] applied (b-bit) minwise hashing [Broder et al., 1997, Broder et al., 1998, Li and Church, 2005, Li and König, 2010] to approximate the resemblance (Jaccard) kernel for high-dimensional binary (0/1) data, using highly efficient linear classifiers. In this paper, we first propose the “pGMM” kernel and then present the idea of “generalized consistent weighted sampling” (GCWS) to approximate the pGMM kernel, in the context of training neural networks.

The so-called “generalized min-max” (GMM) kernel was proposed in [Li, 2017]. For defining the GMM kernel, the first step is a simple transformation on the original data. Consider, for example, the original data vector $u_i$, $i=1$ to $D$. The following transformation, depending on whether an entry $u_i$ is positive or negative,

\begin{align}\label{eqn:transform}
\left\{\begin{array}{cc}
\hspace{-.11in}\tilde{u}_{2i-1} = u_i,\hspace{0.1in} \tilde{u}_{2i} = 0&\text{if } \ u_i >0\\
\tilde{u}_{2i-1} = 0,\hspace{0.1in} \tilde{u}_{2i} =  -u_i &\text{if } \ u_i \leq 0
\end{array}\right.
\end{align}

converts general data types to non-negative data only. For example, when $D=2$ and $u = [-3\ \ 17]$, the transformed data vector becomes $\tilde{u} = [0\ \ 3\ \ 17\ \ 0]$. The GMM kernel is then defined as follows:

\begin{align}\label{eqn:GMM}
{\textit{GMM}}(u,v) = \frac{\sum_{i=1}^{2D}\min\{\tilde{u}_i,\tilde{v}_i\}}{\sum_{i=1}^{2D} \max\{\tilde{u}_i,\tilde{v}_i\}}.
\end{align}

[Li and Zhang, 2017] developed some (rather limited) theories for the GMM kernel. For example, under certain distributional assumptions on the data, the GMM similarity converges to the following interesting limit:

\begin{align}
\textit{GMM}(u,v) \rightarrow \frac{1-\sqrt{(1-\rho)/2}}{1+\sqrt{(1-\rho)/2}},
\end{align}

where $\rho$ is the true correlation between $u$ and $v$. More precisely, $\rho$ is the correlation parameter in the bi-variate distribution from which $u$ and $v$ are generated.

Note that, the GMM kernel defined in (<ref>) still has no tuning parameter, unlike (e.g.,) the popular Gaussian (RBF) kernel. An extremely simple strategy to introduce tuning parameters is our proposed “pGMM” kernel:

\begin{align}\label{eqn:pGMM}
&{\textit{pGMM}}(u,v;p) =  \frac{\sum_{i=1}^{2D}\left(\min\{\tilde{u}_i,\tilde{v}_i\}\right)^p}{\sum_{i=1}^{2D}\left( \max\{\tilde{u}_i,\tilde{v}_i\}\right)^p},
\end{align}

where $p\in\mathbb{R}$ is a tuning parameter.
Immediately, readers would notice that this is mathematically equivalent to first applying a power transformation on the data ($\tilde{u}, \tilde{v}$) before computing the GMM kernel. Readers will soon see that, combined with GCWS hashing, our proposal of pGMM provides a convenient and also numerically highly stable scheme for applying the power transformation, regardless of the magnitude of $p$.

§.§ Kernel SVM Experiments

While the main focus of this paper is on training neural networks, we nevertheless provide a set of experimental studies on kernel SVMs for evaluating the pGMM kernel as formulated in (<ref>), in comparison with the linear kernel and the (best-tuned) RBF (Gaussian) kernel. The results are reported in Table <ref>. One reason for presenting this set of experiments is for ensuring reproducibility, as we (and probably many practitioners too) have noticed that tools like LIBSVM/LIBLINEAR are easy to use with essentially deterministic predictions.

For example, for the SEMG dataset, the accuracies for the linear kernel and the (best-tuned) RBF kernel are very low, which are $19.3\%$ and $29.0\%$, respectively. Perhaps surprisingly, the GMM kernel reaches $54\%$ (with no tuning parameter) and the pGMM kernel achieves an accuracy of $56.1\%$ when $p=2$. For the M-Noise1 dataset, the best power parameter is $p = 80$ with an accuracy of $85.2\%$. Readers can check out the deep learning experiments reported in Larochelle et al., 2007 and confirm that they are inferior to the pGMM kernel, for the M-Noise1 dataset.

Public classification datasets and $l_2$-regularized kernel SVM results. We report the test classification accuracies for the linear kernel, the best-tuned RBF kernel, the original (tuning-free) GMM kernel, and the best-tuned pGMM kernel, at their individually-best SVM regularization $C$ values. The results on linear kernels were conducted using LIBLINEAR [Fan et al., 2008] and the kernel SVM experiments were conducted using LIBSVM and pre-computed kernel matrices (hence it is difficult to train on datasets of more than 30,000 data points). All datasets are from the UCI repository except for M-Noise1 and M-Image, which were used by Larochelle et al., 2007, Li, 2010 for testing deep learning algorithms and tree methods.

Dataset        # train     # test     # dim     # class     linear     RBF     GMM     pGMM (p)

SEMG     1800     1,800     2,500     6     19.3     29.0     54.0     56.1 (2)

DailySports     4,560     4,560     5,625     19     77.7     97.6     99.6     99.6 (0.6)

M-Noise1     10,000     4,000     784     10     60.3     66.8     71.4     85.2 (80)

M-Image     12,000     50,000     784     10     70.7     77.8     80.9     89.5 (50)

PAMAP101     188,209     188,208     51     20     75.3     —      —     —

Covtype     290,506     290,506     54     7     71.5     —      —     —

It is not at all our intention to debate which type of classifiers work the best. We believe the performance highly depends on the datasets. Nevertheless, we hope that it is clear from Table <ref> that the pGMM kernel is able to achieve comparable or better accuracy than the RBF kernel on a wide range of datasets. Note that, there are more than 10 datasets used in Larochelle et al., 2007, Li, 2010, such as M-Noiose2, ..., M-Noise6, etc which exhibit similar behaviors as M-Noise1. To avoid boring the readers, we therefore only present the experimental results for M-Noise1 and M-Image.

§.§ Linearizing pGMM Kernel via Generalized Consistent Weighted Sampling

When using LIBSVM pre-computed kernel functionality, we have found it is already rather difficult if the number of training examples exceeds merely 30,000. It has been a well-known challenging task to scale up kernel learning for large datasets [Bottou et al., 2007]. This has motivated many studies for developing hashing methods to approximately linearize nonlinear kernels. In this paper, we propose using the “generalized consistent weighted sampling” (GCWS) to approximate the pGMM kernel, in the context of training neural networks for any tuning parameter $p$, as illustrated in Algorithm <ref>.

Input: Data vector $u_i$  ($i=1$ to $D$)

Generate vector $\tilde{u}$ in $2D$-dim by (<ref>).

For $i$ from 1 to $2D$

$r_i\sim \textit{Gamma}(2, 1)$, $c_i\sim \textit{Gamma}(2, 1)$,  $\beta_i\sim \textit{Uniform}(0, 1)$

$t_i\leftarrow \lfloor p\frac{\log \tilde{u}_i }{r_i}+\beta_i\rfloor$, $a_i\leftarrow \log(c_i)- r_i(t_i+1-\beta_i)$

End For

Output: $i^* \leftarrow \textit{arg}\min_i \ a_i$,  $t^* \leftarrow t_{i^*}$
Generalized consistent weighted sampling (GCWS) for hashing the pGMM kernel.

Given another data vector $v$, we feed it to GCWS using the same set of random numbers: $r_i$, $c_i$, $\beta_i$. To differentiate the hash samples, we name them, respectively,
$(i^*_{u}, t^*_{u})$ and $(i^*_{v}, t^*_{v})$. We first present the basic probability result as the following theorem.

\begin{align}\label{eqn:GCWS_Prob}
\end{align}

The proof of Theorem <ref> directly follows from the basic theory of consistent weighted sampling (CWS) [Manasse et al., 2010, Ioffe, 2010, Li et al., 2021]. Although the original CWS algorithm is designed (and proved) only for non-negative data, we can see that the two transformations, i.e., converting general data types to non-negative data by (<ref>) and applying the power on the converted data as in (<ref>), are only pre-processing steps and the same proof for CWS will go through for GCWS.

Note that, in Algorithm <ref>, while the value of the output $i^*$ is upper bounded by $2D$, the other integer output $t^*$ is actually unbounded. This makes it less convenient for the implementation. The next Theorem provides the basis for the (b-bit) implementation of GCWS. The proof is also straightforward.

Assume that we can map $(i_u^*, t_u^*)$ uniformly to a space of $b$ bits denoted by $(i_u^*, t_u^*)_b$. Similarly, we have $(i_v^*, t_v^*)_b$. Then

\begin{align}\label{eqn:pGMM_b}
P[(i_u^*,t_u^*)_b=(i_v^*,t_v^*)_b]=\textit{pGMM}(u,v) + \frac{1}{2^b}\left\{1-\textit{pGMM}(u,v)\right\}.
\end{align}

§.§ Practical Implementation of GCWS

For each input data vector, we need to generate $k$ hash values, for example, $(i^*_{u,j}, t^*_{u,j})$, $j = 1$ to $k$, for data vector $u$. The mapping of $(i^*_{u,j}, t^*_{u,j})$ uniformly to $(i^*_{u,j}, t^*_{u,j})_b$ is actually not a trivial task, in part because $t^*$ is unbounded. Based on the intensive experimental results in [Li, 2015] (for the original CWS algorithm), we will take advantage of following approximation:

\begin{align}\label{eqn:GCWS_Prob_approx}
P[i_u^*=i_v^*]\approx P[(i_u^*,t_u^*)=(i_v^*,t_v^*)] =\textit{pGMM}(u,v).
\end{align}

and will only keep the lowest $b$ bits of $i^*$ (unless we specify otherwise).

Suppose that, for data vector $u$, we have obtained $k=3$ hash values which after we keep only the lowest $b =2$ bits, become $(3,0,1)$. We then concatenate their “one-hot” representations to obtain $[1\ 0\ 0\ 0 \ \ 0\ 0\ 0\ 1 \ \ 0\ 0\ 1\ 0]$, which is fed to subsequent algorithms for classification, regression, or clustering. In other words, with $k$ hashes and $b$ bits, for each input data vector we obtain a binary vector of length $2^b \times k$ with exactly $k$ 1's.

§.§ The History of Consistent Weighted Sampling

For binary (0/1) data, the pGMM kernel becomes the resemblance (Jaccard) similarity and GCWS is essentially equivalent to the celebrated minwise hashing algorithm [Broder et al., 1997, Broder et al., 1998, Li and Church, 2005, Li and König, 2010], with numerous practical applications [Fetterly et al., 2003, Jindal and Liu, 2008, Buehrer and Chellapilla, 2008, Urvoy et al., 2008, Dourisboure et al., 2009, Forman et al., 2009, Pandey et al., 2009, Cherkasova et al., 2009, Chierichetti et al., 2009, Gollapudi and Sharma, 2009, Najork et al., 2009, Bendersky and Croft, 2009, Li et al., 2011, Shrivastava and Li, 2012, Schubert et al., 2014, Fu et al., 2015, Pewny et al., 2015, Manzoor et al., 2016, Raff and Nicholas, 2017, Tymoshenko and Moschitti, 2018, Zhu et al., 2019, Lei et al., 2020, Thomas and Kovashka, 2020]. Note that minwise hashing can also be used to estimate 3-way and multi-way resemblances [Li et al., 2010], not limited to only pairwise similarity.

For general non-binary and non-negative data, the development of consistent weighted sampling algorithm in its current form was due to [Manasse et al., 2010, Ioffe, 2010], as well as the earlier versions such as [Gollapudi and Panigrahy, 2006]. [Li, 2015] made the observation about the “0-bit” CWS, i.e., (<ref>) and applied it to approximate large-scale kernel machines using linear algorithms. [Li, 2017] generalized CWS to general data types which can have negative entries and demonstrated the considerable advantage of CWS over random Fourier features [Rahimi and Recht, 2007, Li and Li, 2021]. From the computational perspective, CWS is efficient in sparse data. For dense data, algorithms based on rejection sampling [Kleinberg and Tardos, 1999, Charikar, 2002, Shrivastava, 2016, Li and Li, 2021] can be much more efficient than CWS. For relatively high-dimensional datasets, the method of “bin-wise CWS” (BCWS) [Li et al., 2019] would always be recommended. Simply speaking, the basic idea of BCWS is to divide the data matrix into bins and then apply CWS (for sparse data) or rejection sampling (for dense data) in each bin. Finally, we should add that the mathematical explanation of the “0-bit” approximation (<ref>), empirically observed by [Li, 2015], remains an open problem. The recent work by [Li et al., 2021] developed a related algorithm based on extremal processes and mathematically proved the effectiveness of the “0-bit” approximation for that algorithm, which is closely related to but not CWS.

§.§ Our Contributions

In this paper, we develop GCWS (generalized CWS) for hashing the pGMM kernel and then apply GCWS for efficiently training neural networks. We name our procedure GCWSNet and show that GCWSNet can often achieve more accurate results compared with the standard neural networks. We also have another beneficial observation, that the convergent speed of GCWSNet can be substantially faster than the standard neural networks. In fact, we notice that GCWS typically achieves a reasonable accuracy in (less than) one epoch. This characteristic of GCWSNet might be a huge advantage. For example, in many applications such as data streams, one of the 10 challenges in data mining [Yang and Wu, 2006], each sample vector is only seen once and hence only one epoch is allowed in the training process. In commercial search engines, when training click-through rate (CTR) deep learning models, typically only one epoch is used [Fan et al., 2019, Zhao et al., 2019, Fei et al., 2021, Xu et al., 2021] because the training data size is  on the petabyte scale and new observations (i.e., user click information) keep arriving at a very fast rate. Additionally, there is another side benefit of GCWSNet, because the computations at the first layer become additions instead of multiplications.

§ GCWSNET

For each input data vector, we first generate $k$ hash values $(i^*, t^*)$ using GCWS as in Algorithm <ref>. We adopt the “0-bit” approximation (<ref>) and keep only the lowest $b$ bits of $i^*$. For example, suppose $k=3$,  $b =2$ bits, and the hash values become $(3,0,1)$. We concatenate their “one-hot” representations to obtain $[1\ 0\ 0\ 0 \ \ 0\ 0\ 0\ 1 \ \ 0\ 0\ 1\ 0]$, which is the input data fed to neural networks. In short, with $k$ hashes and $b$ bits, for each input data vector we obtain a binary vector of length $2^b \times k$ with exactly $k$ 1's.

The experiments were conducted on the  PaddlePaddle  <https://www.paddlepaddle.org.cn> deep learning platform. We adopted the Adam optimizer [Kingma and Ba, 2015] and set the initial learning rate to be $0.001$. We use “ReLU” for the activation function; other learning rates gave either similar or worse results in our experiments. The batch size was set to be 32 for all datasets except Covtype for which we use 128 as the batch size.  We report experiments for neural nets with no hidden units (denoted by “$L=1$”), one layer of $H$ hidden units (denoted by “$L = 2$”) and two layers (denoted by “$L=3$”) of hidden units ($H$ units in the first hidden layer and $H/2$ units in the second hidden layer). We have also experimented with more layers.

Figure <ref> presents the experimental results on the SEMG dataset using GCWS (with $p=1$) along with the results  on the original data (dashed black curves). This is a small dataset with only 1,800 training samples and 1,800 testing samples. It is relatively high-dimensional with 2,500 features. Recall that in Table <ref>, on this dataset, we obtain an accuracy of $19.3\%$ using linear classifier and $29\%$ using the (best-tuned) RBF kernel. In Figure <ref>, the dashed (black) curves for $L=1$ (i.e., neural nets with no hidden units) are consistent with the results in Table <ref>, i.e., an accuracy of $<20\%$ for using linear classifier. Using one layer of $H$ hidden units (i.e., $L=2$) improves the accuracy quite noticeably (to about $25\%$). However, using two layers of hidden units (i.e., $L=3$) further improves the accuracy only very little (if any).

For the SEMG dataset, GCWS (even with $p=1$) seems to be  highly effective. We report the experiments for $b\in\{1,2,4,8\}$ and $K\in\{64,128,256,512\}$. The cost of training SGD is largely determined by the number of nonzero entries. Note that even with $k=512$, the number of nonzero entries in each input training data vector is only $k=512$ while the original SEMG dataset has 2,500 nonzero entries in each data vector.

We recommend using a large $b$ value as long as the model is still small enough to be stored. With $b=8$ bits, we notice that, regardless of $H$ and $K$ (and the number of hidden layers), GCWSNet converges  fast and typically  reaches a reasonable accuracy at the end of one epoch. Here “one epoch” means all the training samples have been used exactly once. This property can be highly beneficial in practice. In data stream applications, one of the 10 challenges in data mining [Yang and Wu, 2006], each training example is seen only once and the process of model training is by nature one-epoch.

GCWSNet with $p=1$, for $b\in\{1,2,4,8\}$ and $k\in\{64,128,256,512\}$, on the SEMG dataset (see Table <ref> for the details). We report the test accuracy for 5 epochs. Here “one epoch” means all the training data points have been used exactly once.   “$L = 1$” means no hidden units, i.e., just logistic regression. “$L=2$” means one hidden layer of $H$ units. “$L=3$” means two hidden layers with $H$ units in the first hidden layer and $H/2$ units in the second hidden layer. The results for the original data are reported as dashed (black) curves, which are substantially worse than the results of GCWSNet, as one would expect from Table <ref>. One important observation is that GCWSNet converges much faster, (for this dataset) reaching  the close-to-the-best accuracy after finishing merely one epoch of training.

There are other important applications which would also prefer one-epoch training. For example, in commercial search engines such as <www.baidu.com> and <www.google.com>, a crucial component is the click-through rate (CTR) prediction task, which routinely uses very large distributed deep learning models. The training data size is  on the petabyte scale and new observations (i.e., user clicks) keep arriving at an extremely fast rate. As far as we know from our own experience, the training of CTR model is typically just one epoch [Fan et al., 2019, Zhao et al., 2019, Fei et al., 2021, Xu et al., 2021].

GCWSNet with $p=2$ on the SEMG dataset. Note that for the original data (dashed black curves), we still report the original results without applying the power transformation. The results on the original data with power transformation using $p=2$ are actually not too much different from using $p=1$.

Table <ref> shows that, for the SEMG dataset, the pGMM kernel with $p=2$ improves the classification accuracy. Thus, we also report the results of GCWSNet for $p=2$ in Figure <ref>. Compared with the corresponding plots/curves in Figure <ref>, the improvements are quite obvious. Figure <ref> also  again confirms that training just one epoch can already reach good accuracies.

Next we examine the experimental results on the Covtype dataset, in Figure <ref> for 100 epochs. Again, we can see that GCWSNet converges substantially faster.  To view the convergence rate more clearly, we repeat the same plots in Figure <ref> but for just 1 epoch. As the Covtype dataset has 290,506 training samples, we cannot compute the pGMM kernel directly. LIBLINEAR reports an accuracy of $71.5\%$, which is more or less consistent with the results for $L=1$ (i.e., no hidden layer).

The experiments on the Covtype dataset reveal a practically important issue, if applications only allow training for one epoch, even though training more epochs might lead to noticeably better accuracies. For example, consider the plots in the right-bottom corner in both  Figure <ref> and Figure <ref>, for $b=8$, $L=2$,  $H=200$. For the original data, if we stop after one epoch, the accuracy would drop from about $89\%$ to $77\%$, corresponding to a $13.5\%$ drop of accuracy. However, for GCWSNet with $k=64$, if the training stops after one epoch, the accuracy  would drop from $91\%$ to just $84\%$ (i.e., a $7.7\%$ drop). This again confirms the benefits of GCWSNet in the scenario of one-epoch training.

GCWSNet with $p=1$, for $b\in\{2,4,8\}$ and $k\in\{64,128,256,512\}$, on the Covtype dataset, for 100 epochs. The results for the original data are reported as dashed (black) curves, which are substantially worse than the results of GCWSNet. Again, GCWSNet converges much faster than training on the original data.

GCWSNet with $p=1$, for $b\in\{2,4,8\}$ and $k\in\{64,128,256,512\}$, on the Covtype dataset, for just one epoch,  to better illustrate that GCWSNet converges much faster than training on the original data.

Summary results of GCWSNet with $p=1$ on the Covtype dataset, at the end of the first epoch.

Figure <ref> reports the summary of the test accuracy for the Covtype dataset for just one epoch, to better illustrate the impact of $b$, $H$, $K$, as well as $L$.

Next, Figure <ref> and Figure <ref> present the experimental results on the PAMAP101 dataset, for  We report the results for 100 epochs in Figure <ref> and the results for just 1 epoch in Figure <ref>.  Again, we can see that GCWSNet converges much faster and can reach a reasonable accuracy even with only one epoch of training.

GCWSNet with $p=1$, for $b\in\{1,2,4\}$ and $k\in\{64,128,256,512\}$, on the PAMAP101 dataset, for 100 epochs.  Again, we can see that GCWSNet converges much faster than training on the original data.

GCWSNet with $p=1$, for $b\in\{1,2,4\}$ and $k\in\{64,128,256,512\}$, on the PAMAP101 dataset, just for 1 epoch. Again, we can see that GCWSNet converges much faster than training on the original data.

Next, we summarize the results on the DailySports dataset, the M-Noise1 dataset, and the M-Image dataset, in Figure <ref>, Figure <ref>, and Figure <ref>, respectively, for just 1 epoch.  For DailySports, we let $p=1$. For M-Noise1 and M-Image, we use $p=80$ and $p=50$, respectively,  as suggested in Table <ref>.

GCWSNet with $p=1$ on the DailySports dataset, for just 1 epoch.

GCWSNet with $p=80$ on the M-Noise1 dataset, for just 1 epoch.

GCWSNet with $p=50$ on the M-Image dataset, for just 1 epoch.

§ USING BITS FROM $T^*$

GCWSNet  for M-Noise (with $p=80$) and M-Image (with $p=50$) by using 0 bit (solid), 1 bit (dashed), and 2 bits (dashed dot) for $t^*$ in the output of GCWS hashing $(i^*, t^*)$

In Figure <ref>, we report the experiments for using 1 or 2  bits from $t^*$, which  have not been used in all previously presented experiments. Recall the approximation in (<ref>)

\begin{align}\notag
P[i_u^*=i_v^*]\approx P[(i_u^*,t_u^*)=(i_v^*,t_v^*)] =\textit{pGMM}(u,v),
\end{align}

which, initially, was purely an  empirical observation [Li, 2015]. The recent work [Li et al., 2021] hoped to explain the above approximation by developing a new algorithm based on extremal processes which is closely related to CWS. Nevertheless, characterizing this approximation for CWS remains an open problem. Figure <ref> provides a validation study on M-Noise and M-Image, by adding the lowest 1 bit (dashed curve) or 2 bits (dashed dot curves) of $t^*$. We can see that adding 1 bit of $t^*$  indeed helps slightly when we only use $b=1$ or $b=2$ bits for $i^*$. Using 2 bits for $t^*$ does not lead further improvements. When we already use $b=4$ or $b=8$ bits to encode $i^*$, then adding the information  for 1 bit from $t^*$ does not help in a noticeable manner.

In practice, we expect that practitioners would anyway need to use a sufficient number of bits for $i^*$ such as 8 bits. We therefore do not expect that using bits from $t^*$  would help. Nevertheless, if it is affordable, we would suggest using the lowest 1 bit of $t^*$ in addition to using $b$ bits for $i^*$.

§ COMBINING GCWS WITH COUNT-SKETCH

GCWS generates high-dimensional binary  sparse inputs. With $k$ hashes and $b$ bits for encoding each hashed value, we obtain a vector of size $2^b \times k$ with exactly $k$ 1's, for each original data vector. While the (online) training cost is mainly determined by $k$ the number of nonzero entries, the model size is still proportional to $2^b\times k$. This might be an issue for the GPU memory when both $k$ and $b$ are large. In this scenario, the well-known method of “count-sketch” might be helpful for reducing the model size.

Count-sketch [Charikar et al., 2004] was originally developed for recovering sparse signals (e.g., “elephants” or “heavy hitters” in network/database terminology). [Weinberger et al., 2009] applied count-sketch as a dimension reduction tool. The work of [Li et al., 2011], in addition to developing hash learning algorithm based on minwise hashing, also provided the thorough theoretical analysis for count-sketch in the context of estimating inner products. The conclusion from [Li et al., 2011]  is that,  to estimate inner products, we should use count-sketch (or very sparse random projections [Li, 2007])  instead of the original (dense) random projections, because count-sketch is not only computationally much more efficient but also (slightly) more accurate, as far as the task of similarity estimation is concerned.

We use this opportunity to review count-sketch [Charikar et al., 2004] and the detailed analysis in [Li et al., 2011]. The key step  is to independently and uniformly hash elements of the data vectors to buckets $\in\{1, 2, 3, ..., B\}$ and the hashed value is the weighted sum of the elements in the bucket, where the weights are generated from a random distribution which must be $\{-1, 1\}$ with equal probability (the reason will soon be clear).   That is, we have $h(i) = j$ with probability $\frac{1}{B}$, where $j \in\{1, 2, ..., B\}$. For convenience, we introduce an indicator function:

\begin{align}\notag
I_{ij} =\left\{\begin{array}{ll}
1 &\text{if } h(i) = j\\
0 &\text{otherwise}
\end{array}
\right.\end{align}

Consider two vectors $x, y\in\mathbb{R}^d$ and assume $d$ is divisible by $B$, without loss of generality.  We also generate a random vector $r_i$, $i  = 1 $ to $d$, i.i.d., with the following property:

\begin{align}
E(r_i) = 0, \hspace{0.2in} E(r_i^2) = 1, \hspace{0.2in} E(r_i^3) = 0, \hspace{0.2in} E(r_i^4) = s
\end{align}

Then we can generate $k$ (count-sketch) hashed values for $x$ and $y$, as follows,

\begin{align}\label{eqn:z,w}
z_j = \sum_{i=1}^d x_{i} r_i I_{ij}, \hspace{0.5in} w_{j} = \sum_{i=1}^d y_{i} r_i I_{ij}, \ \ \ j = 1, 2, ..., B
\end{align}

The following Theorem <ref> says that the inner product $<z,w> = \sum_{j=1}^B z_j w_j$ is an unbiased estimator of $<x,y>$.

\begin{align}
& E\{<z,w>\} = <x,y> = \sum_{i=1}^d x_{i}y_{i},\\
&\textit{Var}\{<z,w>\} = (s-1)\sum_{i=1}^dx_{i}^2y_{i}^2 + \frac{1}{B}\left[\sum_{i=1}^d x_{i}^2\sum_{i=1}^d y_{i}^2 + \left(\sum_{i=1}^d x_{i}y_{i}\right)^2-2\sum_{i=1}^d x_{i}^2y_{i}^2\right].
\end{align}

From the above theorem, we can see that we must have $E(r_i^4) = s = 1$. Otherwise, the variance $\textit{Var}\{<z,w>\}$ will end up with a positive term which does not vanish with increasing  $B$ the number of bins. There is only one such distribution, i.e., $\{-1, +1\}$ with equal probability.

Now we are ready to present our idea of combining GCWS with count-sketch. Recall that in the ideal scenario, we map the output of GCWS $(i^*, t^*)$ uniformly to a $b$-bit space of size $2^b$, denoted by $(i^*,t^*)_b$. For the original data vector $u$, we generate $k$ such (integer) hash values, denoted by $(i^*_{u,j},t^*_{u,j})_b$, $j = 1$ to $k$.  Then we concatenate the $k$ one-hot representations of $(i^*_{u,j},t^*_{u,j})_b$, we obtain a binary vector of size $d = 2^b\times k$ with exactly $k$ 1's.  Similarly, we have $(i^*_{v,j},t^*_{v,j})_b$, $j = 1$ to $k$ and the corresponding binary vector of length $2^b \times k$.  Once we have the sparse binary vectors, we can apply count-sketch with $B$ bins. For convenience, we denote

\begin{align}
B = (2^b\times k)/m.
\end{align}

That is, $m$ represents the dimension reduction factor, and $m=1$ means no reduction. We can then generate the ($B$-bin) count-sketch samples, $z$ and $w$, as in (<ref>).  We present the theoretical results on the inner product $<z,w>$ as the next theorem.

Consider original data vector $u$ and $v$. Denote $P_b = P\left\{(i_u^*, t^*_u) _b = (i_v^*, t_v^*)_b\right\}$. Vector $z$ of size $B$ is the ($B$-bin) count-sketch samples  generated from the concatenated binary vector  from the one-hot representation of $(i^*_{u,j},t^*_{u,j})_b$. Similarly, $w$ of size $B$ is the count-sketch samples for $v$. Also, denote

\begin{align}
a = \sum_{j=1}^k 1\left\{(i^*_{u,j},t^*_{u,j})_b = (i^*_{v,j},t^*_{v,j})_b\right\}.
\end{align}

Conditioning on the GCWS output $(i^*_{u,j},t^*_{u,j})_b, (i^*_{v,j},t^*_{v,j})_b$ and using Theorem <ref> with $s=1$, we  have

\begin{align}
& E\left\{<z,w>|\textit{GCWS}\right\} =a,\\
&Var\{<z,w>|\textit{GCWS}\} = \frac{1}{B}\left[k^2 + a^2-2a\right].
\end{align}

Note that $a$ is binomial $\textit{Bin}(k,P_b)$, i.e., $E(a) = kP_b, \textit{Var}(a) = kP_b(1-P_b)$.  Unconditionally, we have

\begin{align}
& E\left\{<z,w>\right\} = kP_b,\\
&\textit{Var}\{<z,w>\} = \frac{1}{B}\left[k^2+k^2P_b^2-kP^2_b-kP_b\right] + kP_b(1-P_b).
\end{align}

Define the estimator $\hat{P}_b$ as

\begin{align}
\hat{P}_b = \frac{<z,w>}{k}.
\end{align}

\begin{align}
&E\left(\hat{P}_b\right) = P_b,\\\label{eqn:var_Pb_cs}
&\textit{Var}\left(\hat{P}_b\right) = \frac{P_b(1-P_b)}{k} +  \frac{1}{B}\left[1+P^2_b - P_b^2/k - P_b/k\right].
\end{align}

The variance  $\textit{Var}\left(\hat{P}_b\right)$ (<ref>) in Theorem <ref> has two parts. The first term $\frac{P_b(1-P_b)}{k}$ is the usual variance without using count-sketch. The second term $\frac{1}{B}\left[1+P^2_b - P_b^2/k - P_b/k\right]$ represents the additional variance due to count-sketch. The hope is  that the additional variance would not be too large, compared with  $\frac{P_b(1-P_b)}{k}$. Let $B = (2^b\times k)/m$, then the second term can be written as $\frac{1}{k}\frac{m}{2^b}\left[1+P^2_b - P_b^2/k - P_b/k\right]$.

Thus, to assess the impact of count-sketch, we just need to compare $P_b(1-P_b)$ with $\frac{m}{2^b}\left[1+P^2_b - P_b^2/k - P_b/k\right]$, which is approximately $\frac{m}{2^b}\left[1+P^2_b\right]$, as $k$ has to be sufficiently large. Recall from Theorem <ref> $P_b = J + \frac{1}{2^b}(1-J)$, where $J = \textit{pGMM}(u,v;p) =  \frac{\sum_{i=1}^{2D}\left(\min\{\tilde{u}_i,\tilde{v}_i\}\right)^p}{\sum_{i=1}^{2D}\left( \max\{\tilde{u}_i,\tilde{v}_i\}\right)^p}$.  Therefore, we can resort to the following “ratio” to assess the impact of count-sketch on the variance:

\begin{align}\label{eqn:cs_ratio}
R = R(b,J,m)= \frac{m}{2^b}\frac{1+P_b^2}{P_b(1-P_b)}, \hspace{0.2in} \text{where } P_b = J + \frac{1}{2^b}(1-J).
\end{align}

The ratio (<ref>) $R = \frac{m}{2^b}\frac{1+P_b^2}{P_b(1-P_b)}$, where $P_b = J + \frac{1}{2^b}(1-J)$ and $J$ the pGMM similarity of interest, for $b \in\{8, 12, 16\}$ and a series of $m$ values. Ideally, we would like to see large $m$ and small ratio values.

As shown in Figure <ref>, when $b=16$, the ratio is small even for $m=1000$. However, when $b=8$, the ratio is not too small after $m>10$; and hence  we  should only expect a saving by an order magnitude if $b=8$ is used. The choice of $b$ has, to a good extent, to do with  $D$, the original data dimension. When the data are extremely high-dimensional, say $D=2^{30}$, we expect an excellent storage savings can be achieved by using a large $b$  and a large $m$.

For practical consideration, we consider two strategies for choosing $m$, as illustrated in  Figure <ref>. The first strategy (left panel) is “always using half of the bits”, that is, we let $m = 2^{b/2}$. This method is probably a bit conservative for $b\geq 16$. The second strategy (right panel) is “always using 8 bits” which corresponds to almost like a single curve, because $R = \frac{1}{2^8}\frac{1+P_b^2}{P_b(1-P_b)}$ in this case and $P_b = J + (1-J)\frac{1}{2^b}\approx J$ when $b\geq 8$.

The ratio (<ref>) for two strategy of choosing $m$. In the left panel, we let $m = 2^{b/2}$ (i.e., always using half of the bits). In the right panel, for $b\geq 8$ we let $m = 2^{b-8}$ (i.e., always using  8 bits).

We believe the “always using 8 bits” strategy might be a good practice. In implementation, it is convenient to use 8 bits (i.e., one byte). Even when we really just need 5 or 6 bits in some cases, we might as well simply use one byte to avoid the trouble of performing bits-packing.

We conclude this section by providing an empirical study on M-Noise1 and M-Image and summarize the results in Figure <ref>. For both datasets, when $m<=16$, we do not see an obvious drop of accuracy, compared with $m=1$ (i.e., without using count-sketch). This confirms the effectiveness of our proposed procedure by combining GCWSNet with count-sketch.

GCWS combined with count-sketch for reducing the model size by a factor of $m$, where $m = (2^b\times k)/B$ and $B$ is the number of bins in the count-sketch step.  $m=1$ means there is no reduction. We can see that at least with $m=8$ or $m=16$, there is  no obvious loss of accuracy.

§ GCWS AS A ROBUST POWER TRANSFORMATION

In Algorithm <ref>, this step (on nonzero entries)

\begin{align}
t_i\leftarrow \left\lfloor p\frac{\log \tilde{u}_i }{r_i}+\beta_i\right\rfloor
\end{align}

suggests that GCWS can be viewed as a robust power transformation on the data. It should be clear that GCWS is not simply taking the log-transformation on the original data.  We will compare  three different strategies for data preprocessing. (i) GCWS; (ii) directly feeding the power transformed data (e.g., $u^p$) to neural nets; (iii) directly feeding the log-power transformed data (e.g., $p\log u$) to neural nets.

Even though GCWSNet is obviously not a tree algorithm, there might be some interesting hidden connections. Basically, in GCWS, data entries with (relatively) higher values would be more likely to be picked (i.e., whose locations are chosen as $i^*$'s) in a probabilistic manner. Recall that in  trees [Brieman et al., 1983, Hastie et al., 2001], only the relative orders of the data values matter, i.e., trees are invariant to any monotone transformation. GCWS is somewhat in-between. It is affected by monotone transformations but not “too much”.

Naively applying power transformation on the original data might encounter practical problems. For example, when data entries contain large values such as “1533” or “396”, applying a powerful transformation such as $p=80$ might lead to overflow problems and other issues such as loss of accuracy during computations. Using the log-power transformation, i.e., $p\times \log u$, should alleviate many problems but new issues might arise. For example, when data entries ($u$) are small. How to handle zeros is another headache with log-power transformation.

GCWS with a wide range of $p$ values, on the UCI Pendigits dataset, for $b=8$ and $k\in\{64, 512\}$.  We can see that using $p\in[0.5,\ 5]$ produces the best results. Also, the results of GCWSNet are still reasonable even with very large or very small $p$ values. In comparison, we apply the power transformation (i.e., $u^p$) and log-power transformation (i.e., $p\log u$, treating $u\log 0 = 0$) on the original data and feed the transformed data directly to neural nets. Their results are not as accurate compared with GCWSNet. Also, the power transformation encountered numerical issues with $p\geq 15$.

Here, we provide an experimental study on the UCI Pendigits dataset, which contains positive integers features (and many zeros). The first a few entries of the training dataset are “8 1:47 2:100 3:27 4:81 5:57 6:37 7:26 10:23 11:56”  (in LIBSVM format). As shown in Figure <ref>, after $p\geq 15$, directly applying the power transformation (i.e., $u^p$) makes the training fail. The log-transformation (i.e., $p\log u$) seems to be quite robust in this dataset, because we use a trick by letting $p\log 0 = 0$, which seems to work well for this dataset. On the other hand, GCWS with any $p$ produces reasonable predictions, although it appears that $p\in[0.5,\  5]$ (which is quite a wide range) is the optimal range for GCWSNet. This set of experiments on the Pendigits dataset confirms the robustness of GCWSNet with any $p$. Additionally, the experiments once again verify that GCWSNet converges really fast and achieves a reasonable accuracy as early as in 0.1 epoch.

Next, we present the experiments on the M-Noise1 dataset, which is quite different from the Pendigits dataset. The first a few entries are “3 1:0.82962122 2:0.56410292 3:0.27904908 4:0.25310652 5:0.29387237” (also in LIBSVM format). This dataset is actually dense, with (almost) no zero entries. As shown in Figure <ref>, using the log-power transformation produced very bad results, except for $p$ close 1. Directly applying the power transformation seems to work well on this dataset (unlike Pendigits), although we can see that GCWSNet still produces more accurate predictions.

To conclude this section, we should emphasize that we do not claim that we have fully solved the data preprocessing problem, which is a highly crucial task for practical applications. We simply introduce GCWSNet with one single tuning parameter which happens to be quite robust, in comparison with obvious (and commonly used) alternatives for power transformations.

GCWS with different $p$ values, on the M-Noise1 dataset, for $b=8$ and $k\in\{64, 512\}$.  We can see that using $p\in[60,\ 150]$ produces the best results. The results of GCWSNet are still reasonable even with $p=1$. Using the log-power transformation produces bad results except for $p$ close to 1.  Applying the power transformation directly on the original data produces pretty good results, which are still obviously worse than the results of GCWSNet.

§ APPLYING GCWS ON THE LAST LAYER OF TRAINED NETWORKS

We can always apply GCWS on the trained embedding vectors. Figure <ref> illustrates such an example. We train a neural net on the original data  with one hidden layer (i.e., $L=2$) of $H\in \{200,400\}$ hidden units. We directly apply GCWS on the output of the hidden layer and perform the classification task (i.e.,  a logistic regression)  using the output of GCWS. We do this for every iteration of the neural net training process so that we can compare the entire history. From the plots, we can see that GCWS (solid red curves) can drastically improve the original test accuracy (dashed black curves), especially at the beginning of the training process, for example, improving the test accuracy from $20\%$ to $70\%$ after the first batch.

We apply GCWS (with $k=256$ and $b=8$) on the output of the last layer of neural net. This case, the network has one hidden layer (i.e., $L =2$) and $H\in \{200,400\}$. We perform this operation at every batch, without affecting the accuracy of the original network. This way, we obtain a history of improvements.

§ COMPARISON WITH NORMALIZED RANDOM FOURIER FEATURES (NRFF)

The method of random Fourier features (RFF) [Rudin, 1990, Rahimi and Recht, 2007] is a popular randomized algorithm for approximating the RBF (Gaussian) kernel. See, for example, a recent work in [Li and Li, 2021] on quantizing RFFs for achieving storage savings and speeding up computations. Here, we first review the normalized RFF (NRFF) in [Li, 2017] which recommended the following procedure when applying RFF.

At first, the input data vectors are normalized to have unit $l_2$ norms, i.e., $\|u\| = \|v\| =1$. The RBF (Gaussian) kernel is then  $RBF(u,v;\gamma) = e^{-\gamma(1-\rho)}$,  where $\rho=\rho(u,v) = <u,v>$ is the cosine and $\gamma>0$ is a  tuning parameter. We sample $w\sim \textit{uniform}(0,2\pi)$, $r_{i}\sim N(0,1)$ i.i.d., and denote  $x = \sum_{i=1}^D u_i r_{ij}$, $y = \sum_{i=1}^D v_i r_{ij}$.  It is clear that $x \sim N(0,1)$ and $y \sim N(0,1)$. The procedure is repeated $k$ times to generate $k$ RFF samples for each data vector.

[Li, 2017] proved the next Theorem for the so-called  “normalized RFF” (NRFF).

Consider $k$ iid samples ($x_j, y_j, w_j$) where $x_j\sim N(0,1)$, $y_j\sim N(0,1)$,  $E(x_jy_j) = \rho$, $w_j\sim \textit{uniform}(0,2\pi)$, $j =1, 2, ..., k$. Let $X_j = \sqrt{2}\cos\left(\sqrt{\gamma}x_j + w_j\right)$ and $Y_j = \sqrt{2}\cos\left(\sqrt{\gamma}y_j + w_j\right)$. As $k\rightarrow\infty$, the following asymptotic normality holds:

\begin{align}\label{eqn_NRFF}
&\sqrt{k}\left(\frac{\sum_{j=1}^k X_j Y_j}{\sqrt{\sum_{j=1}^k X_j^2}\sqrt{\sum_{j=1}^k Y_j^2}} - e^{-\gamma(1-\rho)}\right)\overset{D}{\Longrightarrow}
\end{align}

\begin{align}\label{eqn_NRFF_Var}
&V_{n,\rho,\gamma} = V_{\rho,\gamma}- \frac{1}{4}e^{-2\gamma(1-\rho)} \left[3-e^{-4\gamma(1-\rho)}  \right]\\
&V_{\rho,\gamma} = \frac{1}{2}+\frac{1}{2}\left(1-e^{-2\gamma(1-\rho)}\right)^2
\end{align}

In the above theorem, $V_{\rho,\gamma}$ is the corresponding variance term without normalizing the output RFFs. Obviously, $V_{n,\rho,\gamma} < V_{\rho,\gamma}$, meaning that it is always a good idea to normalize the output RFFs before feeding NRFF samples to the subsequent tasks.

Figure <ref> provides an experimental study to compare NRFF with GCWS on two datasets. While we still use $k\in\{64, 128, 256, 512\}$ for GCWS (solid curves), we have to present for $k$ as large as 8192 for NRFF (dashed curves) because it is well-known that RFF needs a large number of samples in order to obtain reasonable results. It is quite obvious from Figure <ref> that, at least on these two datasets, GCWS performs considerably better than NRFF at the same $k$ (even if we just use $b=1$ bit for GCWS). Also, we can see that GCWS converges much faster.

The method of random Fourier features is very popular in academic research. In comparison, research activities on consistent weighted sampling and variants are sparse. We hope this study might generate more interest in GCWS and motivate researchers as well as practitioners to try this interesting method.

NRFF (dashed curves) versus GCWS (solid curves), for two datasets: SEMG and DailySports and $b\in\{1,8\}$. We use much larger $k$ values for NRFF, as large as $8192$.

§ CONCLUDING REMARKS

In this paper, we propose the pGMM kernel with a single tuning parameter $p$ and use GCWS (generalized consistent weighted sampling) to generate hash values, producing sparse binary data vectors of size $2^b\times k$, where $k$ is the number of hash samples and $b$ is the number of bits  to store each hash value. These binary vectors are fed to neural networks for subsequent tasks such as regression or classification. Many interesting  findings can be summarized  which might benefit future research or practice.

Experiments show that GCWS converges fast and typically reaches a reasonable accuracy at (less than) one epoch. This characteristic of GCWS could be highly beneficial in practice because many important applications such as data streams or CTR predictions in commercial search engines train only one epoch.

GCWS with a single tuning parameter $p$ provides a beneficial and  robust power transformation on the original data. By adding this tuning parameter, the performance can often be improved, in some cases considerably so. Inside GCWS, this tuning parameter acts on the (nonzero) data entry as $p\log u$ (which is typically robust). The nature of GCWS is that the coordinates of entries with larger values have a higher chance to be picked as output (in a probabilistic manner). In other words, both the absolute values and relative orders matter, and the power transformation does impact the performance unlike trees which are invariant to monotone transformations. Experiments show that GCWSNet with a tuning parameter $p$ produces more accurate results compared with two obvious strategies: 1) feeding power-transformed data ($u^p$) directly to neural nets; 2) feeding log-power-transformed data ($p\log u$, with zeros handled separately) directly to neural nets.

GCWSNet can be combined with count-sketch to reduce the model size of GCWSNet, which is proportional to $2^b\times k$ and can be pretty large if $b$ is large such as 16 or 24. Our theoretical analysis for the impact of count-sketch on the estimation variance provides the explanation for the effectiveness of count-sketch demonstrated in the experiments. We recommend the “8-bit” practice in that we always use $2^8$ bins for count-sketch if GCWS uses $b\geq 8$. With this strategy, even when $k=2^{10} = 1024$, the model size is only proportional to $2^{8} \times 2^{10} =2^{18}$, which is not a large number. Note that the outputs of applying count-sketch on top of GCWS remain to be integers, meaning that a lot of multiplications can be still be avoided.

There are other ways to take advantage of GCWS. For example, one can always apply GCWS on the embeddings of trained neural nets to hopefully boost the performance of existing network models. We also hope the comparison of GCWS with random Fourier features would promote interest in future research.

Finally, we should mention again that hashing pGMM can be conducted efficiently. For dense data, we recommend algorithms based on rejection sampling [Shrivastava, 2016, Li and Li, 2021]. For sparse data, we suggest GCWS. For relatively high-dimensional data, we always recommend the bin-wise algorithm in [Li et al., 2019] combined with rejection sampling or GCWS, depending on data sparsity.

All reported  experiments were conducted on the PaddlePaddle <https://www.paddlepaddle.org.cn> deep learning platform.

[Bendersky and Croft, 2009]
Michael Bendersky and W. Bruce Croft.
Finding text reuse on the web.
In Proceedings of the Second International Conference on Web
Search and Web Data Mining (WSDM), pages 262–271, Barcelona, Spain, 2009.

[Bottou et al., 2007]
Léon Bottou, Olivier Chapelle, Dennis DeCoste, and Jason Weston, editors.
Large-Scale Kernel Machines.
The MIT Press, Cambridge, MA, 2007.

[Brieman et al., 1983]
Leo Brieman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone.
Classification and Regression Trees.
Wadsworth, Belmont, CA, 1983.

[Broder et al., 1997]
Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, and Geoffrey Zweig.
Syntactic clustering of the web.
Comput. Networks, 290 (8-13):0 1157–1166,

[Broder et al., 1998]
Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher.
Min-wise independent permutations.
In Proceedings of the Thirtieth Annual ACM Symposium on the
Theory of Computing (STOC), pages 327–336, Dallas, TX, 1998.

[Buehrer and Chellapilla, 2008]
Gregory Buehrer and Kumar Chellapilla.
A scalable pattern mining approach to web graph compression with
In Proceedings of the International Conference on Web Search
and Web Data Mining (WSDM), pages 95–106, Stanford, CA, 2008.

[Charikar et al., 2004]
Moses Charikar, Kevin Chen, and Martin Farach-Colton.
Finding frequent items in data streams.
Theor. Comput. Sci., 3120 (1):0 3–15, 2004.

[Charikar, 2002]
Moses S. Charikar.
Similarity estimation techniques from rounding algorithms.
In Proceedings on 34th Annual ACM Symposium on Theory of
Computing (STOC), pages 380–388, Montreal, Canada, 2002.

[Cherkasova et al., 2009]
Ludmila Cherkasova, Kave Eshghi, Charles B. Morrey III, Joseph Tucek, and
Alistair C. Veitch.
Applying syntactic similarity algorithms for enterprise information
In Proceedings of the 15th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining (KDD), pages 1087–1096,
Paris, France, 2009.

[Chierichetti et al., 2009]
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Michael Mitzenmacher,
Alessandro Panconesi, and Prabhakar Raghavan.
On compressing social networks.
In Proceedings of the 15th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining (KDD), pages 219–228,
Paris, France, 2009.

[Dourisboure et al., 2009]
Yon Dourisboure, Filippo Geraci, and Marco Pellegrini.
Extraction and classification of dense implicit communities in the
web graph.
ACM Trans. Web, 30 (2):0 1–36, 2009.

[Fan et al., 2019]
Miao Fan, Jiacheng Guo, Shuai Zhu, Shuo Miao, Mingming Sun, and Ping Li.
MOBIUS: towards the next generation of query-ad matching in baidu's
sponsored search.
In Proceedings of the 25th ACM SIGKDD International
Conference on Knowledge Discovery & Data Mining, (KDD) 2019, pages
2509–2517, Anchorage, AK, 2019.

[Fan et al., 2008]
Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and
Chih-Jen Lin.
LIBLINEAR: A library for large linear classification.
J. Mach. Learn. Res., 9:0 1871–1874, 2008.

[Fei et al., 2021]
Hongliang Fei, Jingyuan Zhang, Xingxuan Zhou, Junhao Zhao, Xinyang Qi, and Ping
Gemnn: Gating-enhanced multi-task neural networks with feature
interaction learning for CTR prediction.
In Proceedings of the 44th International ACM SIGIR
Conference on Research and Development in Information Retrieval (SIGIR),
pages 2166–2171, Virtual Event, Canada, 2021.

[Fetterly et al., 2003]
Dennis Fetterly, Mark Manasse, Marc Najork, and Janet L. Wiener.
A large-scale study of the evolution of web pages.
In Proceedings of the Twelfth International World Wide Web
Conference (WWW), pages 669–678, Budapest, Hungary, 2003.

[Forman et al., 2009]
George Forman, Kave Eshghi, and Jaap Suermondt.
Efficient detection of large-scale redundancy in enterprise file
SIGOPS Oper. Syst. Rev., 430 (1):0 84–91,
ISSN 0163-5980.

[Fu et al., 2015]
Min Fu, Dan Feng, Yu Hua, Xubin He, Zuoning Chen, Wen Xia, Yucheng Zhang, and
Yujuan Tan.
Design tradeoffs for data deduplication performance in backup
In Proceedings of the 13th USENIX Conference on File and
Storage Technologies (FAST), pages 331–344, Santa Clara, CA, 2015.

[Gollapudi and Panigrahy, 2006]
Sreenivas Gollapudi and Rina Panigrahy.
Exploiting asymmetry in hierarchical topic extraction.
In Proceedings of the 2006 ACM CIKM International
Conference on Information and Knowledge Management (CIKM), pages 475–482,
Arlington, VA, 2006.

[Gollapudi and Sharma, 2009]
Sreenivas Gollapudi and Aneesh Sharma.
An axiomatic approach for result diversification.
In Proceedings of the 18th International Conference on World
Wide Web (WWW), pages 381–390, Madrid, Spain, 2009.

[Hastie et al., 2001]
Trevor J. Hastie, Robert Tibshirani, and Jerome H. Friedman.
The Elements of Statistical Learning:Data Mining, Inference,
and Prediction.
Springer, New York, NY, 2001.

[Ioffe, 2010]
Sergey Ioffe.
Improved consistent sampling, weighted minhash and L1 sketching.
In Proceedings of the 10th IEEE International Conference on
Data Mining (ICDM), pages 246–255, Sydney, Australia, 2010.

[Jindal and Liu, 2008]
Nitin Jindal and Bing Liu.
Opinion spam and analysis.
In Proceedings of the International Conference on Web Search
and Web Data Mining (WSDM), pages 219–230, Palo Alto, CA, 2008.

[Kingma and Ba, 2015]
Diederik P. Kingma and Jimmy Ba.
Adam: A method for stochastic optimization.
In Proceedings of the 3rd International Conference on Learning
Representations (ICLR), San Diego, CA, 2015.

[Kleinberg and Tardos, 1999]
Jon Kleinberg and Eva Tardos.
Approximation algorithms for classification problems with pairwise
relationships: Metric labeling and Markov random fields.
In 40th Annual Symposium on Foundations of Computer Science
(FOCS), pages 14–23, New York, NY, 1999.

[Larochelle et al., 2007]
Hugo Larochelle, Dumitru Erhan, Aaron C. Courville, James Bergstra, and Yoshua
An empirical evaluation of deep architectures on problems with many
factors of variation.
In Proceedings of the Twenty-Fourth International Conference on
Machine Learning (ICML), pages 473–480, Corvalis, Oregon, 2007.

[Lei et al., 2020]
Yifan Lei, Qiang Huang, Mohan S. Kankanhalli, and Anthony K. H. Tung.
Locality-sensitive hashing scheme based on longest circular
In Proceedings of the 2020 International Conference on
Management of Data (SIGMOD), pages 2589–2599, Online conference [Portland,
OR, USA], 2020.

[Li, 2007]
Ping Li.
Very sparse stable random projections for dimension reduction in
$l_\alpha$ ($0<\alpha\leq2$) norm.
In Proceedings of the 13th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining (KDD), pages 440–449, San
Jose, CA, 2007.

[Li, 2010]
Ping Li.
Robust logitboost and adaptive base class (abc) logitboost.
In Proceedings of the Twenty-Sixth Conference Annual Conference
on Uncertainty in Artificial Intelligence (UAI), pages 302–311, Catalina
Island, CA, 2010.

[Li, 2015]
Ping Li.
0-bit consistent weighted sampling.
In Proceedings of the 21th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining (KDD), pages 665–674,
Sydney, Australia, 2015.

[Li, 2017]
Ping Li.
Linearized GMM kernels and normalized random Fourier features.
In Proceedings of the 23rd ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining (KDD), pages 315–324,

[Li and Church, 2005]
Ping Li and Kenneth Ward Church.
Using sketches to estimate associations.
In Proceedings of the Conference on Human Language Technology
and the Conference on Empirical Methods in Natural Language Processing
(HLT/EMNLP), pages 708–715, Vancouver, Canada, 2005.

[Li and König, 2010]
Ping Li and Arnd Christian König.
b-bit minwise hashing.
In Proceedings of the 19th International Conference on World
Wide Web (WWW), pages 671–680, Raleigh, NC, 2010.

[Li and Zhang, 2017]
Ping Li and Cun-Hui Zhang.
Theory of the GMM kernel.
In Proceedings of the 26th International Conference on World
Wide Web (WWW), pages 1053–1062, Perth, Australia, 2017.

[Li et al., 2010]
Ping Li, Arnd Christian König, and Wenhao Gui.
b-bit minwise hashing for estimating three-way similarities.
In Advances in Neural Information Processing Systems (NIPS),
Vancouver, BC, 2010.

[Li et al., 2019]
Ping Li, Xiaoyun Li, and Cun-Hui Zhang.
Re-randomized densification for one permutation hashing and bin-wise
consistent weighted sampling.
In Advances in Neural Information Processing Systems 32: Annual
Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14
December 2019, Vancouver, BC, Canada, pages 15900–15910, 2019.

[Li et al., 2021]
Ping Li, Xiaoyun Li, Gennady Samorodnitsky, and Weijie Zhao.
Consistent sampling through extremal process.
In Proceedings of the Web Conference (WWW), Virtual, 2021.

[Li and Li, 2021]
Xiaoyun Li and Ping Li.
One-sketch-for-all: Non-linear random features from compressed linear
In Proceedings of the 24th International Conference on
Artificial Intelligence and Statistics (AISTATS), pages 2647–2655, Virtual
Event, 2021a.

[Li and Li, 2021]
Xiaoyun Li and Ping Li.
Rejection sampling for weighted jaccard similarity revisited.
In Proceedings of the Thirty-Fifth AAAI Conference on
Artificial Intelligence (AAAI), Virtual Event, 2021b.

[Li et al., 2011]
Zhen Li, Huazhong Ning, Liangliang Cao, Tong Zhang, Yihong Gong, and Thomas S.
Learning to search efficiently in high dimensions.
In Advances in Neural Information Processing Systems (NIPS),
Granada, Spain, 2011.

[Manasse et al., 2010]
Mark Manasse, Frank McSherry, and Kunal Talwar.
Consistent weighted sampling.
Technical Report MSR-TR-2010-73, Microsoft Research, 2010.

[Manzoor et al., 2016]
Emaad A. Manzoor, Sadegh M. Milajerdi, and Leman Akoglu.
Fast memory-efficient anomaly detection in streaming heterogeneous
In Proceedings of the 22nd ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining (KDD), pages 1035–1044,
San Francisco, CA, 2016.

[Najork et al., 2009]
Marc Najork, Sreenivas Gollapudi, and Rina Panigrahy.
Less is more: sampling the neighborhood graph makes salsa better and
In Proceedings of the Second International Conference on Web
Search and Web Data Mining (WSDM), pages 242–251, Barcelona, Spain, 2009.

[Pandey et al., 2009]
Sandeep Pandey, Andrei Broder, Flavio Chierichetti, Vanja Josifovski, Ravi
Kumar, and Sergei Vassilvitskii.
Nearest-neighbor caching for content-match applications.
In Proceedings of the 18th International Conference on World
Wide Web (WWW), pages 441–450, Madrid, Spain, 2009.

[Pewny et al., 2015]
Jannik Pewny, Behrad Garmany, Robert Gawlik, Christian Rossow, and Thorsten
Cross-architecture bug search in binary executables.
In Proceedings of the 2015 IEEE Symposium on Security and
Privacy (SP), pages 709–724, San Jose, CA, 2015.

[Raff and Nicholas, 2017]
Edward Raff and Charles K. Nicholas.
An alternative to NCD for large sequences, lempel-ziv jaccard
In Proceedings of the 23rd ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining (KDD), pages 1007–1015,
Halifax, Canada, 2017.

[Rahimi and Recht, 2007]
Ali Rahimi and Benjamin Recht.
Random features for large-scale kernel machines.
In Advances in Neural Information Processing Systems (NIPS),
pages 1177–1184, Vancouver, Canada, 2007.

[Rudin, 1990]
Walter Rudin.
Fourier Analysis on Groups.
John Wiley & Sons, New York, NY, 1990.

[Schubert et al., 2014]
Erich Schubert, Michael Weiler, and Hans-Peter Kriegel.
Signitrend: scalable detection of emerging topics in textual streams
by hashed significance thresholds.
In Proceedings of the 20th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining (KDD), pages 871–880, New
York, NY, 2014.

[Shrivastava, 2016]
Anshumali Shrivastava.
Simple and efficient weighted minwise hashing.
In Neural Information Processing Systems (NIPS), pages
1498–1506, Barcelona, Spain, 2016.

[Shrivastava and Li, 2012]
Anshumali Shrivastava and Ping Li.
Fast near neighbor search in high-dimensional binary data.
In Proceedings of European Conference on Machine Learning and
Knowledge Discovery in Databases (ECML-PKDD), pages 474–489, Bristol, UK,

[Thomas and Kovashka, 2020]
Christopher Thomas and Adriana Kovashka.
Preserving semantic neighborhoods for robust cross-modal retrieval.
In Proceedings of the 16th European Conference on Computer
Vision (ECCV), Part XVIII, pages 317–335, Glasgow, UK, 2020.

[Tymoshenko and Moschitti, 2018]
Kateryna Tymoshenko and Alessandro Moschitti.
Cross-pair text representations for answer sentence selection.
In Proceedings of the 2018 Conference on Empirical Methods in
Natural Language Processing (EMNLP), pages 2162–2173, Brussels, Belgium,

[Urvoy et al., 2008]
Tanguy Urvoy, Emmanuel Chauveau, Pascal Filoche, and Thomas Lavergne.
Tracking web spam with html style similarities.
ACM Trans. Web, 20 (1):0 1–28, 2008.

[Weinberger et al., 2009]
Kilian Q. Weinberger, Anirban Dasgupta, John Langford, Alexander J. Smola, and
Josh Attenberg.
Feature hashing for large scale multitask learning.
In Proceedings of the 26th Annual International Conference on
Machine Learning (ICML), pages 1113–1120, Montreal, Canada, 2009.

[Xu et al., 2021]
Zhiqiang Xu, Dong Li, Weijie Zhao, Xing Shen, Tianbo Huang, Xiaoyun Li, and
Ping Li.
Agile and accurate CTR prediction model training for massive-scale
online advertising systems.
In Proceedings of the International Conference on Management of
Data (SIGMOD), pages 2404–2409, Virtual Event, China, 2021.

[Yang and Wu, 2006]
Qiang Yang and Xindong Wu.
10 challenging problems in data mining research.
International Journal of Information Technology & Decision
Making, 50 (04):0 597–604, 2006.

[Zhao et al., 2019]
Weijie Zhao, Jingyuan Zhang, Deping Xie, Yulei Qian, Ronglai Jia, and Ping Li.
Aibox: CTR prediction model training on a single node.
In Proceedings of the 28th ACM International Conference on
Information and Knowledge Management (CIKM), pages 319–328, Beijing, China,

[Zhu et al., 2019]
Erkang Zhu, Dong Deng, Fatemeh Nargesian, and Renée J. Miller.
JOSIE: overlap set similarity search for finding joinable tables in
data lakes.
In Proceedings of the 2019 International Conference on
Management of Data (SIGMOD), pages 847–864, Amsterdam, The Netherlands,