smallequation

$\BODY$

(1)

smallalign

$\BODY$

(2)

# C-OPH: Improving the Accuracy of One Permutation Hashing (OPH) with
Circulant Permutations

Xiaoyun Li and Ping Li

Cognitive Computing Lab
Baidu Research
10900 NE 8th St. Bellevue, WA 98004, USA
{xiaoyunli<EMAIL_ADDRESS>
###### Abstract

Minwise hashing (MinHash) is a classical method for efficiently estimating the
Jaccrad similarity in massive binary (0/1) data. To generate $K$ hash values
for each data vector, the standard theory of MinHash requires $K$ independent
permutations. Interestingly, the recent work on “circulant MinHash”
(C-MinHash) (Li and Li, 2021b) has shown that merely two permutations are
needed. The first permutation breaks the structure of the data and the second
permutation is re-used $K$ time in a circulant manner. Surprisingly, the
estimation accuracy of C-MinHash is proved to be strictly smaller than that of
the original MinHash. The more recent work (Li and Li, 2021a) further
demonstrates that practically only one permutation is needed. Note that those
two papers (Li and Li, 2021a, b) are different from the well-known work on
“One Permutation Hashing (OPH)” published in NIPS’12 (Li et al., 2012). OPH
and its variants using different “densification” schemes are popular
alternatives to the standard MinHash. The densification step is necessary in
order to deal with empty bins which exist in One Permutation Hashing.

In this paper, we propose to incorporate the essential ideas of C-MinHash to
improve the accuracy of One Permutation Hashing. Basically, we develop a new
densification method for OPH, which achieves the smallest estimation variance
compared to all existing densification schemes for OPH. Our proposed method is
named C-OPH (Circulant OPH). After the initial permutation (which breaks the
existing structure of the data), C-OPH only needs a “shorter” permutation of
length $D/K$ (instead of $D$), where $D$ is the original data dimension and
$K$ is the total number of bins in OPH. This short permutation is re-used in
$K$ bins in a circulant shifting manner. It can be shown that the estimation
variance of the Jaccard similarity is strictly smaller than that of the
existing (densified) OPH methods.

Additionally, our work leads to an interesting and useful consequence. That
is, if we neglect the cost of the initial permutation needed by the bin-
dividing step, then we actually just need “$1/K$” permutation instead of one
permutation. It turns out that the initial permutation can be safely replaced
by an approximate permutation such as 2-universal (2U) hashing, as verified by
an extensive empirical study.

##  1 Introduction

With the explosive growth in the scale of data, efficient methods for search,
data storage, and large-scale machine learning have become increasingly
important. The method of minwise hashing (MinHash) (Broder, 1997; Broder et
al., 1998; Li and König, 2011) is a classical and popular hashing algorithm
for binary 0/1 data. The hashed values of two data points
$\bm{v},\bm{w}\in\\{0,1\\}^{D}$, which are non-negative integers, have
collision probability equal to the Jaccard similarity (resemblance) between
the two data points defined as

$\displaystyle
J(\bm{v},\bm{w})=\frac{\sum_{i=1}^{D}\mathbbm{1}\\{v_{i}=w_{i}=1\\}}{\sum_{i=1}^{D}\mathbbm{1}\\{v_{i}+w_{i}\geq
1\\}}.$ (3)

When using MinHash in practice, in order to ensure reliable accuracy, one
typically needs to generate hundreds to thousands hash values per data point
depending on the applications. We use $K$ to denote the target number of
hashes (per data point). Operationally, to achieve a strict performance
guarantee that matches the theory, the standard MinHash requires $K$
independent permutations, with each hash value being the minimal permuted
index of the non-zero elements of the data vector.

Over the past decades, MinHash and variants have been widely used in numerous
applications, for similarity estimation, approximate nearest neighbor search,
duplicate detection, clustering, classification, image retrieval, database
systems, etc. (Broder et al., 1997; Charikar, 2002; Fetterly et al., 2003; Das
et al., 2007; Buehrer and Chellapilla, 2008; Bendersky and Croft, 2009; Lee et
al., 2010; Li et al., 2011; Deng et al., 2012; Chum and Matas, 2012;
Shrivastava and Li, 2012; Tamersoy et al., 2014; Zhu et al., 2017; Nargesian
et al., 2018; Wang et al., 2019; Lemiesz, 2021; Tseng et al., 2021; Feng and
Deng, 2021; Jia et al., 2021).

Here, we should also mention that, in the very early development of minwise
hashing, only one permutation was used by storing the first $K$ non-zero
locations after the permutation (Broder, 1997; Broder et al., 1997). Later Li
and Church (2005) proposed maximum likelihood estimators to significantly
improve the estimation accuracy, and Li and Church (2007) further extended the
method to estimating three-way and multi-way associations. However, because
the hashed values in Broder (1997); Broder et al. (1997); Li and Church (2005,
2007) did not form a metric space (i.e., satisfy the triangle inequality),
they could not be used for numerous important applications that require metric
space.

###  1.1 Circulant Minwise Hashing (C-MinHash)

Recently, Li and Li (2021b) proposes a convenient variant of MinHash that
rigorously reduces the number of independent permutations required to merely
2. In the so-called Circulant MinHash method, noted as
C-MinHash-$(\sigma,\pi)$, the first permutation $\sigma$ is used for initially
permuting the data (pre-processing), and the second (independent) permutation
$\pi$ is used for generating the hash values, repeatedly for $K$ times by
circulant shifts. For example, if $\pi=[3,2,4,1]$, then $\pi_{\rightarrow
1}=[1,3,2,4]$ is the permutation shifted rightwards by 1 element, and so on.
C-MinHash uses $\pi_{\rightarrow 1}$, $\pi_{\rightarrow 2}$, …, to generate
the hash values, instead of the independent permutations as in the standard
MinHash. The concrete procedure is summarized in Algorithm 1.

1 Input: Binary data vector $\bm{v}\in\\{0,1\\}^{D}$, Permutation vectors
$\pi$ and $\sigma$: $[D]\rightarrow[D]$

2Output: Hash values $h_{1}(\bm{v}),...,h_{K}(\bm{v})$

3

4Initial permutation: $\bm{v}^{\prime}$ = $\sigma(\bm{v})$

5For $k=1$ to $K$

6 Shift $\pi$ circulantly rightwards by $k$ units: $\pi_{k}=\pi_{\rightarrow
k}$

7 $h_{k}(\bm{v})\leftarrow\min_{i:v_{i}^{\prime}\neq 0}\pi_{\rightarrow k}(i)$

8End For

Algorithm 1 C-MinHash-$(\sigma,\pi)$

Surprisingly, it was proved in Li and Li (2021b) that using merely 2
permutations, the Jaccard estimator of C-MinHash has uniformly smaller
variance than that of the classical MinHash (with $K$ independent
permutations). Moreover, in a followup work (Li and Li, 2021a), they further
verified by extensive empirical results that actually one can more
conveniently use merely one permutation, i.e., simply letting $\sigma=\pi$ in
Algorithm 1. That is, one can use $\pi$ for both initialization (pre-
processing) and circulant hashing. While the dependence between initial
permutation and those for hashing makes the theoretical analysis very
complicated, the authors of (Li and Li, 2021a) provided the exact expression
of the mean estimation of C-MinHash-$(\pi,\pi)$. Even though the Jaccard
estimator of C-MinHash-$(\pi,\pi)$ is biased, the bias is too small to have
any noticeable impact on the overall mean square error (MSE), where MSE =
variance + bias2.

Practically speaking, C-MinHash provides a convenient strategy for the design
of hashing systems. For instance, when the data space is not ultra large
(e.g., $\leq 2^{30}$, a billion features), we can simply save one “permutation
vector” to generate all $K$ hash values. A vector of length $2^{30}$ can be
easily stored, even in GPU memory. However, saving thousands of such
permutations might be still unrealistic and wasteful. The benefit of using
exact permutations, instead of approximation by hash functions, is that the
empirical performance would always match the theory. We will elaborate more on
this point later in the paper.

###  1.2 One Permutation Hashing (OPH)

While C-MinHash methods need to use only one or two permutations, it should be
clear that they are different from the work on “one permutation hashing (OPH)”
and its many variants of “densification” schemes. The idea of OPH (Li et al.,
2012) is to randomly divide the data vector of size $D$ into $K$ equal-sized
bins (by applying a random permutation $\sigma$). Then, minwise hashing is
applied in each bin, producing $K$ hash values from $K$ bins. An illustrative
example is presented in Figure 1. The theoretical correctness of this approach
is built upon the proof that, the expected “bin-wise” Jaccard similarity in
each simultaneously non-empty bin is the same as the true $J$ of the whole
data vectors $\bm{v},\bm{w}$ (Li et al., 2012).

Figure 1: A toy example of One Permutation Hashing (OPH) provided by Li et al.
(2019) on three binary vectors, $v_{1},v_{2},v_{3}$. The data vector $\bm{v}$
is first randomly split into $K=4$ bins,
$\mathcal{B}_{1},...,\mathcal{B}_{4}$, by a random permutation $\sigma$. Then,
the hash value is taken as the smallest non-zero index within each bin
(effectively doing a minwise hashing within the bin). If a bin is empty, we
record “$E$”. For instance, $h(v_{1})=[E,5,11,14]$.

Note that, as shown in Figure 1, OPH really only needs one permutation (if the
number of hash values is smaller than $K$). After the data vector is permuted
by $\sigma$ and broken into $K$ bins, the “small permutation” within each bin
is already completed. Nevertheless, for the convenience of explaining our
proposed idea in this paper, we can still conceptually view OPH as a “two-
permutation” scheme. That is, the initial permutation $\sigma$ is applied and
the data vector is divided after the permutation. A second permutation $\pi$
is broken evenly into $K$ small permutations and each small permutation is
used in one bin to conduct minwise hashing within the bin. As proved in Li et
al. (2012), for OPH, we can simply let $\pi=\sigma$. This interpretation would
be helpful to understand the densification and re-randomization procedures
which will soon be introduced.

There are possibly empty bins, especially for relatively sparse data vectors,
as reflected in Figure 1. To tackle the problem of empty bins, Shrivastava and
Li (2014a, b) developed two “densification” schemes, which were later improved
by Shrivastava (2017); Li et al. (2019), among other works.

###  1.3 Summary of Contributions

In this work, we seek to improve the estimation accuracy of the existing OPH
framework as well its densification methods, by incorporating the essential
idea of circulant MinHash (Li and Li, 2021b, a). After the initial bin-
dividing process, we use a “small” permutation of size $D/K$, where $D$ is the
data dimension and $K$ is the number of bins. Without loss of generality, we
assume $D/K$ is an integer (otherwise we can always pad zeros). This
permutation is re-used in all bins in a circulant shifting manner. We derive
the precise variance formula of the Jaccard estimator, and show that C-OPH
reduces the prior known optimal Jaccard estimation variance of densified OPH
(Li et al., 2019). Numerical results are provided to validate the theory.

In addition to achieving improved accuracy, there is also another beneficial
consequence. That is, if we neglect the cost of the initial permutation for
the bin-dividing procedure, we actually only need “$1/K$ permutation” to
generate $K$ hash values, instead of using one permutation of size $D$. It
turns out that the initial permutation can be safely replaced by an
approximation such as the 2-universal (2U) hashing and other approximate
hashing methods such as 4-universal (4U) hashing. Consider the original
Circulant MinHash with two permutations C-MinHash-$(\sigma,\pi)$. If we
replace the initial permutation $\sigma$ by 2U hashing, it becomes
C-MinHash-$(2U,\pi)$. Likewise, if we replace the second permutation $\pi$ by
2U hashing, we obtain C-MinHash-$(\sigma,2U)$. Our experimental study has
shown that C-MinHash-$(2U,\pi)$ achieves essentially the same accuracy as
C-MinHash-$(\sigma,\pi)$. The accuracy of C-MinHash-$(\sigma,2U)$, however,
can be much worse than C-MinHash-$(\sigma,\pi)$. in certain datasets.

The above observation provides the intuition for developing
C-OPH-$(2U,\pi/K)$. That is, in Circulant OPH, we use the 2U hashing for the
initial permutation and use one single (small) permutation of size $D/K$ to
generate hashes from the bins, in a circulant shifting fashion. This strategy
would allow practitioners to be able to use C-OPH-$(2U,\pi/K)$ in datasets of
much higher dimensions. For example, consider a dataset with $D=2^{40}$ and we
let $K=2^{10}$. Then we just need a small permutation of size $D/K=2^{30}$ for
this very high dimensional dataset, and $2^{30}$ is small enough even for the
GPU memory.

##  2 Background: Densified One Permutation Hashing (OPH)

We first provide the details about OPH and its densification schemes. The
generic framework of OPH is provided in Algorithm 2, where $[K]$ denotes the
set $\\{1,...,K\\}$. For illustration, we present ReDen (Re-randomized
Densified), the most recent and theoretically the most accurate densified OPH
(Li et al., 2019). Here, we consider a flexible implementation of OPH to allow
the number of bins $K$ and the number of hash values $M$ to be different. This
is a convenient and practical setting where one may hope to continue
generating more than $K$ hashes after each bin has contributed one hash.

1 Input: Binary data vector $\bm{v}\in\\{0,1\\}^{D}$; Number of bins $K$;
Number of hash values $M$

2Output: OPH hashes $h_{1}(\bm{v}),...,h_{M}(\bm{v})$

3

4Use a permutation $\sigma$ to randomly split $[D]$ into $K$ equal-size bins
$\mathcal{B}_{1},...,\mathcal{B}_{K}$,
$\mathcal{B}_{i}=\\{j:(i-1)\frac{D}{K}+1\leq\sigma(j)\leq i\frac{D}{K}\\}$

5Assign each hash an independent permutation $\pi^{(i)}:[D/K]\mapsto[D/K]$,
$i\in[M]$

6For $k=1$ to $M$

7 Select a bin $i_{k}\in[K]$ by some strategy (option (i) or (ii)) //First
scan bin selection

8 If $\mathcal{B}_{i_{k}}$ is not empty

9 $h_{k}(\bm{v})\leftarrow\min_{j\in\mathcal{B}_{i_{k}}:v_{j}\neq
0}\pi^{(k)}(\sigma(j)-(i_{k}-1)\frac{D}{K})+(i_{k}-1)\frac{D}{K}$ //MinHash
within non-empty bin

10 Else

11 $h_{k}(\bm{v})=E$ //Empty bin

12 End If

13End For

14For $k=1$ to $M$

15 If $h_{k}(\bm{v})=E$

16 Select a non-empty bin $i_{k}^{\prime}\in[K]$ //Densification bin selection

17 $h_{k}(\bm{v})\leftarrow\min_{j\in\mathcal{B}_{i_{k}^{\prime}}:v_{j}\neq
0}\pi^{(k)}(\sigma(j)-(i_{k}^{\prime}-1)\frac{D}{K})+(i_{k}^{\prime}-1)\frac{D}{K}$
//Re-randomized Densification

18 End If

End For

Algorithm 2 Generic One Permutation Hashing (OPH) with Re-randomized
Densification (ReDen)

The general procedure of ReDen is as follows:

  1. 1.

Bin split and permutation generation: use a permutation $\sigma$ to randomly
split the data vector $\bm{v}$ into $K$ bins, where
$\mathcal{B}_{i}=\\{j:(i-1)\frac{D}{K}+1\leq\sigma(j)\leq i\frac{D}{K}\\}$.
Assign each hash $k=1,...,M$ an independent “bin-wise” permutation
$\pi^{(k)}:[D/K]\mapsto[D/K]$.

  2. 2.

First scan: for $k=1,...,M$, select a bin $i_{k}\in[K]$ by some strategy. If
bin $i_{k}$ is non-empty, set
$h_{k}(\bm{v})=\displaystyle{\min_{j:j\in\mathcal{B}_{i_{k}},v_{j}\neq
0}\pi^{(k)}(\sigma(j)-(i_{k}-1)\frac{D}{K}})+(i_{k}-1)\frac{D}{K}$, where the
addition is to recover the original index to prevent accidental collision;
otherwise, set $h_{k}(\bm{v})=E$.

  3. 3.

Second scan and Re-randomized Densification: We do another screening over hash
samples $h_{k}$, $k=1,...,M$: if the $k$-th hash is empty (“$E$”), find a non-
empty bin $\mathcal{B}_{i_{k}^{\prime}}$. Densify the $k$-th hash by
$h_{k}(\bm{v})=\displaystyle{\min_{j:j\in\mathcal{B}_{i_{k}^{\prime}},v_{j}\neq
0}\pi^{(k)}(\sigma(j)-(i_{k}^{\prime}-1)\frac{D}{K})+(i_{k}^{\prime}-1)\frac{D}{K}}$.

Note that, in the densification process, ReDen applies independent permutation
$\pi^{(k)}\rotatebox[origin={c}]{90.0}{$\models$}\pi^{(k^{\prime})}$ to get
the hash sample for an empty bin $k$. That said, the “local” permutations used
within bins for producing the hash for each $h_{k}$ are all independent.
Moreover, as mentioned in Section 1.2, the permutation $\sigma$ used for
random bin split also implies the independent bin-wise permutations
$\pi^{(1)},...,\pi^{(M)}$ as required, when $M\leq K$. This is because, for
the permutation $\sigma$ on $[D]$, its “partial” sub-permutations split by
consecutive bins (local order) are also perfectly random and independent.
Therefore, for the $k$-th hash, applying $\sigma$ for bin split implicitly
accomplishes the role of applying an additional bin-wise permutation
$\pi^{(k)}$. Consequently, in practical implementation, when $M\leq K$, we
only need one long permutation $\sigma$, which achieves bin split and implies
all the bin-wise short permutations. When $M>K$, we will need additional
$(M-K)$ “bin-wise” permutations for the purpose of re-randomization.

###  2.1 Bin Selection Strategies

In Algorithm 2, two important ingredients are the first scan bin selection and
the densification bin selection, as depicted by line 6 and line 15,
respectively. Regarding the first scan bin selection (line 6), there are two
available strategies:

  1. (i)

We strictly pick the $K$ bins one by one. For hash value $h_{k}$ with $k>K$,
we apply a rotation strategy, i.e., to pick the $[mod(k-1,K)+1]$-th bin.

  2. (ii)

For every $k\in[M]$, we uniformly randomly choose a bin out of $K$ bins.

Strategy (i) can be regarded as fixing the number of times each bin is chosen,
while strategy (ii) is more flexible. Strategy (i) typically has smaller
Jaccard estimation variance than (ii) (Li et al., 2019). Therefore, in the
remainder, we will stick to strategy (i) as the scanning bin selection for all
the analysis and simulations.

For the densification bin selection strategy (line 15), the earlier work
proposed to rotationally select a nearest non-empty bin in a clock-wise
direction. Later, Shrivastava (2017) proposed to uniformly randomly select
non-empty bins for densification through 2-universal hashing, which is also
adopted in Li et al. (2019). The exact implementation is more complicated in
practice, and we refer interested readers to the aforementioned papers for
more details. It is known that the uniform sampling strategy would lead to
reduced Jaccard estimation variance. Therefore, in our paper, we will focus on
this densification bin selection routine. Note that, the main contribution of
this work, which is the improvement brought by using circulation in OPH, is
valid for all types or combinations of bin selection methods.

###  2.2 Densification Strategies

Line 16 of Algorithm 2 is another important component of OPH, which is the
strategy to generate the (densified) hash value once the non-empty bin is
selected. In ReDen, the re-randomization procedure proposes to re-do an
independent bin-wise permutation. For example, if the hash $h_{k}$ is empty
(i.e., $h_{k}(\bm{v})=E$) and the $j$-th bin is chosen for densifying $h_{k}$,
then $\pi^{(k)}$ is applied to the data in bin $\mathcal{B}_{j}$ to get
$h_{k}(\bm{v})$. In earlier works, e.g., Shrivastava and Li (2014a);
Shrivastava (2017), for densification, the hash value is directly copied from
the non-empty bin to the empty bin, i.e., $h_{k}(\bm{v})\leftarrow
h_{j}(\bm{v})$. However, this strategy leads to larger estimation variance
especially on highly sparse data, since the densification of many empty bins
would output many identical hash values. Intuitively speaking, empty bins
would not provide much useful additional information of the data. Overall, the
ReDen method as presented in Algorithm 2 with option (i) for bin selection and
re-randomized densification is the most recent framework that achieves the
smallest Jaccard similarity estimation variance among all densified OPH
schemes.

##  3 C-OPH: Circulant One Permutation Hashing

In this section, we present our proposed C-OPH method, inspired by the idea of
circulant minwise hashing.

1 Input: Binary data vector $\bm{v}\in\\{0,1\\}^{D}$; Number of bins $K$;
Number of hash values $M$

2 Permutation $\sigma:[D]\mapsto[D]$, $\pi:[D/K]\mapsto[D/K]$

3Output: C-OPH hashes $h_{1}(\bm{v}),...,h_{M}(\bm{v})$

4

5Use $\sigma$ to randomly split $[D]$ into $K$ equal-size bins
$\mathcal{B}_{1},...,\mathcal{B}_{K}$,
$\mathcal{B}_{i}=\\{j:(i-1)\frac{D}{K}+1\leq\sigma(j)\leq i\frac{D}{K}\\}$

6For $k=1$ to $M$

7 Select a bin $i_{k}=mod(k-1,K)+1$ by option (i)

8 If $\mathcal{B}_{i_{k}}$ is not empty

9 $h_{k}(\bm{v})\leftarrow\min_{j\in\mathcal{B}_{i_{k}}:v_{j}\neq
0}\pi_{\rightarrow k}(\sigma(j)-(i_{k}-1)\frac{D}{K})+(i_{k}-1)\frac{D}{K}$
//MinHash within non-empty bin

10 Else

11 $h_{k}(\bm{v})=E$ //Empty bin

12 End If

13End For

14For $k=1$ to $M$

15 If $h_{k}(\bm{v})=E$

16 Select a non-empty bin $i_{k}^{\prime}\in[M]$ uniformly at random

17 $h_{k}(\bm{v})\leftarrow\min_{j\in\mathcal{B}_{i_{k}^{\prime}}:v_{j}\neq
0}\pi_{\rightarrow
k}(\sigma(j)-(i_{k}^{\prime}-1)\frac{D}{K})+(i_{k}^{\prime}-1)\frac{D}{K}$
//C-OPH Densification

18 End If

End For

Algorithm 3 Circulant One Permutation Hashing (C-OPH-$(\sigma,\pi)$) Figure 2:
An illustration of the proposed C-OPH strategy. The data vector $\bm{v}$ is
first randomly split into $K=4$ bins. For ReDen (Li et al., 2019), we use
independent permutation $\pi^{(1)}$, …, $\pi^{(4)}$ to perform MinHash within
each bin. For C-OPH, we use circulant permutations $\pi_{\rightarrow 1}$, …,
$\pi_{\rightarrow 4}$ instead. In this toy example, the 2nd bin
$\mathcal{B}_{2}$ is empty. In both approaches, we randomly select a non-empty
bin ($\mathcal{B}_{4}$ for ReDen, and $\mathcal{B}_{1}$ for C-OPH), and min-
hash the data in that bin with the permutation associated with
$\mathcal{B}_{2}$.

###  3.1 Approach: An Improved Densification Scheme

As shown in Algorithm 3, the proposed Circulant One Permutation Hashing
(C-OPH) method admits the same “bin-wise hashing + densification” protocol as
ReDen. The key difference is the bin-wise permutations used for hashing.
Recall that in Algorithm 2, to generate each hash $h_{k}(\bm{v})$, we use an
independent length-$D/K$ permutation $\pi^{(k)}:[D/K]\mapsto[D/K]$,
$k=1,...,M$. In the proposed C-OPH protocol, we indeed only need one
length-$D/K$ permutation, $\pi$, which is used circulantly in the same spirit
as in C-MinHash. That is, we use $\pi_{\rightarrow k}$ to generated the $k$-th
hash, for both the first scan and the densification. We provide an
illustrative example in Figure 2 of C-OPH. Here, to make sure that no
circulant permutation is repeatedly used, we assume that $KM\leq D$, which is
also needed for establishing rigorous theoretical results.

###  3.2 Theoretical Analysis

We prove that the prior-known minimal Jaccard estimation variance among OPH
methods, which is achieved by ReDen, can be further reduced by the proposed
C-OPH. For conciseness, we assume $M=K$ and $K^{2}\leq D$. For both ReDen
(Algorithm 2) and C-OPH (Algorithm 3), the Jaccard estimator between two
binary data vectors $\bm{v},\bm{w}\in\\{0,1\\}^{D}$ is in the form of average
hash collisions,

$\displaystyle\hat{J}(\bm{v},\bm{w})=\frac{1}{K}\sum_{k=1}^{K}\mathbbm{1}\\{h_{k}(\bm{v})=h_{k}(\bm{w})\\}.$
(4)

Denote $\hat{J}_{ReD}$ and $\hat{J}_{COPH}$ as the estimator resulting from
Algorithm 2 and Algorithm 3 (both with same bin selection options as in
Algorithm 3), respectively. Suppose the length of each bin $d=D/K$ is an
integer. Throughout the paper, we denote

$a=\sum_{i=1}^{D}\mathbbm{1}\\{\bm{v}_{i}=1\text{ and }\bm{w}_{i}=1\\},\quad
f=\sum_{i=1}^{D}\mathbbm{1}\\{\bm{v}_{i}=1\text{ or }\bm{w}_{i}=1\\}.$

The following conditional probability regarding the bin split would be needed
for our analysis.

######  Lemma 3.1.

Let $d=D/K$. Define function $H$ with the following recursion: $\forall 1\leq
k\leq K$, integer $n>0$,

$H(k,n|d)=\sum_{j=1\vee(n-(k-1)d)}^{d\wedge(n-k+1)}{d\choose
j}H(k-1,n-j|d),\hskip 7.22743ptH(1,n|d)={d\choose n}.$

Then, conditional on the event that Algorithm 3 has $m$ non-empty bins, denote
$\tilde{a}=\sum_{i\in\mathcal{B}_{k}}\mathbbm{1}\\{v_{i}+w_{i}=2\\}$,
$\tilde{f}=\sum_{i\in\mathcal{B}_{k}}\mathbbm{1}\\{v_{i}+w_{i}=1\\}$ in a non-
empty bin $\mathcal{B}_{k}$. For $0\leq a^{\prime}\leq\min\\{a,d\\}$, $1\leq
f^{\prime}\leq\min\\{f,d\\}$, $a^{\prime}\leq f^{\prime}$, we have the
conditional distribution as

$\displaystyle
P\left[\tilde{a}=a^{\prime},\tilde{f}=f^{\prime}|m\right]=\frac{{d\choose
f^{\prime}}H(m-1,f-f^{\prime}|d)}{H(m,f|d)}\cdot\frac{{a\choose
a^{\prime}}{f-a\choose f^{\prime}-a^{\prime}}}{{f\choose f^{\prime}}}.$ (5)

###### Proof.

By Lemma 1 of Li et al. (2019), we know that conditional on the event that
there are $m$ non-empty bins (denoted as “$m$” in the formulas for
simplicity), the marginal distribution of $\tilde{f}$ follows

$\displaystyle P\left[\tilde{f}=f^{\prime}|m\right]=\frac{{d\choose
f^{\prime}}H(m-1,f-f^{\prime}|d)}{H(m,f|d)}.$

Thus, the joint distribution can be characterized by

$\displaystyle P\left[\tilde{a}=a^{\prime},\tilde{f}=f^{\prime}|m\right]$
$\displaystyle=P[\tilde{a}=a^{\prime}|\tilde{f}=f^{\prime},m]P[\tilde{f}=f^{\prime}|m]$
$\displaystyle=\frac{{d\choose
f^{\prime}}H(m-1,f-f^{\prime}|d)}{H(m,f|d)}\cdot\frac{{a\choose
a^{\prime}}{f-a\choose f^{\prime}-a^{\prime}}}{{f\choose f^{\prime}}},$

due to the fact that given $\tilde{f}$ within a non-empty bin, $\tilde{a}$
follows a hyper-geometric distribution Hyper($f,a,f^{\prime},a^{\prime}$). ∎

The variance of $\hat{J}_{COPH}$ is provided as below.

######  Theorem 3.2.

Denote $d=D/K$. Assume $K^{2}\leq D$ and $f\leq\frac{K-1}{K}D$. Let
$N_{emp}=K-m$ be the number of empty bins after the bin split, $J=\frac{a}{f}$
and $\tilde{J}=\frac{a-1}{f-1}$. We have

$\displaystyle Var[\hat{J}_{COPH}]$
$\displaystyle=\mathbb{E}\left[KJ+N_{emp}(2K-N_{emp}-1)E_{1}+(K-N_{emp})(K-N_{emp}-1)J\tilde{J}\right],$

with

$\displaystyle E_{1}$
$\displaystyle=\frac{1}{m}\sum_{(a^{\prime},f^{\prime})\in\Omega(m)}\tilde{\mathcal{E}}(a^{\prime},f^{\prime},d)p(a^{\prime},f^{\prime}|m)+\frac{m-1}{m}\tilde{J}J,$

where $\Omega(m)$ is the set of all possible $(\tilde{a},\tilde{f})$ defined
as in Lemma 3.1 within a non-empty bin, and $p(a^{\prime},f^{\prime}|m)$ is
given by (5). Additionally, for any $1\leq a^{\prime}\leq f^{\prime}\leq d$,

$\displaystyle\tilde{\mathcal{E}}(a^{\prime},f^{\prime},d)=\sum_{\\{l_{0},l_{2},g_{0},g_{1}\\}}\Bigg{\\{}\left(\frac{l_{0}}{f^{\prime}+g_{0}+g_{1}}+\frac{a(g_{0}+l_{2})}{(f^{\prime}+g_{0}+g_{1})f^{\prime}}\right)$
$\displaystyle\hskip
36.135pt\times\sum_{s=l}^{d-f^{\prime}-1}\frac{\binom{d-f^{\prime}}{s}\binom{f^{\prime}-a^{\prime}-1}{d-f^{\prime}-s-1}\binom{s}{n_{1}}\binom{d-f^{\prime}-s}{n_{2}}\binom{d-f^{\prime}-s}{n_{3}}\binom{f^{\prime}-a^{\prime}-(d-f-s)}{n_{4}}\binom{a^{\prime}-1}{a^{\prime}-l_{1}-l_{2}}}{\binom{d-a^{\prime}-1}{d-f^{\prime}-1}\binom{d-1}{a^{\prime}}}\Bigg{\\}},$

where

$\displaystyle n_{1}=g_{0}-(d-f^{\prime}-s-g_{1}),\hskip
23.84923ptn_{2}=d-f^{\prime}-s-g_{1},$ $\displaystyle
n_{3}=l_{2}-g_{0}+(d-f^{\prime}-s-g_{1}),\hskip
5.78172ptn_{4}=l_{1}-(d-f^{\prime}-s-g_{1}),$

and the feasible set of $\\{l_{0},l_{2},g_{0},g_{1}\\}$ satisfies the
intrinsic constraints that for non-negative
$l|_{0}^{2},g|_{0}^{2},h|_{0}^{2}$,

$\displaystyle l_{0}+l_{1}+l_{2}=l_{0}+g_{0}+h_{0}=a^{\prime},$ $\displaystyle
g_{0}+g_{1}+g_{2}=l_{1}+g_{1}+h_{1}=d-f^{\prime},$ $\displaystyle
h_{0}+h_{1}+h_{2}=l_{2}+g_{2}+h_{2}=f^{\prime}-a^{\prime}.$

In particular, it holds that $Var[\hat{J}_{COPH}]<Var[\hat{J}_{ReD}]$.

######  Remark 3.1.

In Theorem 3.2, the expectation is with respect to the number of empty bins,
$N_{emp}$. The exact probability distribution of this random variable is

$Pr\left[N_{emp}=j\right]=\sum_{\ell=0}^{K-j}(-1)^{\ell}{K\choose
j}{K-j\choose\ell}{D(1-(j+\ell)/K)\choose f}\bigg{/}{D\choose f}.$

We refer interested readers to Li et al. (2019) for the detailed derivation.

###### Proof.

Firstly, we separate the event of matching hash values into two distinct
events. Denote $C_{k}^{E}$ the indicator of hash collision at bin $k$ when $k$
is empty, and $C_{k}^{N}$ the indicator of collision when $k$ is
simultaneously non-empty. Consequently, we have $C_{k}=C_{k}^{N}+C_{k}^{E}$.
Denote $I_{emp,k}$ as the indicator function of the $k$-th bin being empty.
According to Li et al. (2012), for non-empty bins we have

$\mathbb{E}(C_{k}^{N}|I_{emp,k}=0)=\mathbb{E}(C_{k}^{E}|I_{emp,k}=0)=J,$
$\mathbb{E}[(C_{k}^{N})^{2}|I_{emp,k}=0]=\mathbb{E}[(C_{k}^{E})^{2}|I_{emp,k}=0]=J.$

Based on above notations, for both schemes we can write
$\hat{J}=\frac{1}{K}\sum_{k=1}^{K}(C_{k}^{E}+C_{k}^{N})$. For any unbiased
estimator, we can expand

$Var(\hat{J})=\mathbb{E}[\frac{1}{K^{2}}(\sum_{k=1}^{K}(C_{k}^{E}+C_{k}^{N}))^{2}]-J^{2}\triangleq\frac{1}{K^{2}}A-J^{2}.$
(6)

It suffices to analyze $A$. Conditional on the event that the number of non-
empty bins $K-N_{emp}=m$, we have

$A=\mathbb{E}[\mathbb{E}[(\sum_{k=1}^{K}(C_{k}^{E}+C_{k}^{N}))^{2}|K-N_{emp}=m]].$

For the ease of notation, we simply let $m$ denote the event
$\\{K-N_{emp}=m\\}$. One important fact of C-OPH is that, the expectation of
$C_{i}^{N}C_{j}^{N}$ for non-empty bins $\mathcal{B}_{i},\mathcal{B}_{j}$
where $\pi$ is used circulantly equals that of ReDen where two independent
permutations are applied to $\mathcal{B}_{i}$ and $\mathcal{B}_{j}$
respectively. This is because in the algorithms, the bin split is uniform at
random. Keeping this in mind, for both ReDen and C-OPH we have

$\displaystyle A$
$\displaystyle=\mathbb{E}[\mathbb{E}[(\sum_{k=1}^{M}(C_{k}^{E}+C_{k}^{N}))^{2}|m]]$
$\displaystyle=\mathbb{E}[\mathbb{E}[\sum_{k=1}^{K}[(C_{k}^{E})^{2}+(C_{k}^{N})^{2}]+\sum_{i\neq
j}C_{i}^{E}C_{j}^{E}$ $\displaystyle\hskip 93.95122pt+2\sum_{i\neq
j}C_{i}^{E}C_{j}^{N}+\sum_{i\neq j}C_{i}^{N}C_{j}^{N}|m]]$
$\displaystyle=\mathbb{E}[KJ+N_{emp}(N_{emp}-1)E_{1}+2N_{emp}(K-N_{emp})E_{1}$
$\displaystyle\hskip 93.95122pt+(K-N_{emp})(K-N_{emp}-1)J\tilde{J}]$
$\displaystyle=\mathbb{E}[KJ+N_{emp}(2K-N_{emp}-1)E_{1}$ $\displaystyle\hskip
93.95122pt+(K-N_{emp})(K-N_{emp}-1)J\tilde{J}],$ (7)

where $E_{1}=\mathbb{E}[C_{i}^{E}C_{j}^{E}|m]$, for $i\neq j$. Since
$f\leq\frac{K-1}{K}D$, this expectation is always positive. Denote event
$\Upsilon$ as bin $i$ and bin $j$ choosing the same non-empty bin in the
densification bin selection procedure. Expanding the expectation yields

$\displaystyle E_{1}$ $\displaystyle=P[C_{i}^{E}=C_{j}^{E}=1|m]$
$\displaystyle=P[C_{i}^{E}=C_{j}^{E}=1|\Upsilon,m]P[\Upsilon|m]+P[C_{i}^{E}=C_{j}^{E}=1|\Upsilon^{c},m]P[\Upsilon^{c}|m]$
$\displaystyle=\frac{1}{m}P[C_{i}^{E}=C_{j}^{E}=1|\Upsilon,m]+\frac{m-1}{m}\tilde{J}J.$

Suppose both bins select bin $k$ (non-empty). Let $\mathcal{I}_{k}$ be the
index set of bin $k$. Denote
$a_{k}=|\\{i\in\mathcal{I}_{k}:v_{i}+w_{i}=2\\}|$,
$f_{k}=|\\{i\in\mathcal{I}_{k}:v_{i}+w_{i}=1\\}|$ as the number of two types
of simultaneously non-zero elements in bin $k$. Let $\Omega(m)$ be the
collection of possible $(a_{k},f_{k})$ conditional on $m$ non-empty bins. We
proceed with

$\displaystyle E_{1}$
$\displaystyle=\frac{1}{m}\sum_{(a^{\prime},f^{\prime})\in\Omega(m)}\Big{\\{}P\left[C_{i}^{E}=C_{j}^{E}=1|(a_{k},f_{k})=(a^{\prime},f^{\prime}),\Upsilon,m\right]$
$\displaystyle\hskip 50.58878pt\times
P\left[(a_{k},f_{k})=(a^{\prime},f^{\prime})|\Upsilon,m\right]\Big{\\}}+\frac{m-1}{m}\tilde{J}J.$
(8)

In (8), the second probability is precisely the conditional probability given
by Lemma 3.1. The first probability can be computed as
$\tilde{\mathcal{E}}(a^{\prime},f^{\prime},d)$ by Lemma 3.3 in Li and Li
(2021b), applied to the selected non-empty bin for densification. We refer
interested readers to Li and Li (2021b) for details. Aggregating parts
together gives the exact formula of the variance of C-OPH Jaccard estimator.

To show that $Var[\hat{J}_{COPH}]$ is smaller than $Var[\hat{J}_{ReD}]$,
notice that in (8), the distributions of $(a_{k},f_{k})$ and $m$ only depend
on the bin split procedure which is shared by both ReDen and C-OPH. Therefore,
using circulant permutations in fact only affects the term

$\displaystyle B\triangleq
P[C_{i}^{E}=C_{j}^{E}=1|(a_{k},f_{k})=(a^{\prime},f^{\prime}),\Upsilon,m],$

for each $(a^{\prime},f^{\prime})$, consider bin $k$ as a length-$D/K$ data
vector with within-bin Jaccard index $J^{\prime}=a^{\prime}/f^{\prime}$. Since
$K^{2}\leq D$, applying the arguments of Theorem 3.4 in Li and Li (2021b)
within the bin, we know that C-OPH gives smaller term $B$ than ReDen by the
variance reduction of circulant permutations applied within the bin. Now
combining (6) and (7) proves the desired result. ∎

Theorem 3.2 says that, C-OPH can further improve the prior known smallest
variance of the OPH-type Jaccard estimators, which is the main theoretical
merit of the proposed C-OPH. It is easy to show that this strict variance
reduction holds for arbitrary $K$ and $M$ with $MK\leq D$, which is usually
true in practice for high-dimensional data. Moreover, even if this condition
is not present, the variance of C-OPH can still be considerably smaller. In
line 8 and line 16 of Algorithm 3, we can change “$\pi_{\rightarrow k}$” into
“$\pi_{\rightarrow(k+\lfloor kd/D\rfloor)}$”, where the term $\lfloor
kd/D\rfloor$ is to deploy an additional periodic shifting. For example,
suppose $d=\frac{D}{K}=\frac{M}{2}$ (i.e., $MK=2D$). In the first
$k=d=\frac{M}{2}$-th hashes, the permutation used to generate hash from, e.g.,
$\mathcal{B}_{1}$, is $\pi_{\rightarrow 1}$. With the shifting term, the
permutation used in the last $\frac{M}{2}$ hash values for $\mathcal{B}_{1}$
would be $\pi_{k+\rightarrow\lfloor k/K\rfloor}=\pi_{\rightarrow(d+2)}$, which
is different from the first permutation $\pi_{\rightarrow 1}$ used for
$\mathcal{B}_{1}$. Otherwise (without this shifting term), since
$\pi_{\rightarrow(d+1)}=\pi_{\rightarrow 1}$, the permutations (for
$\mathcal{B}_{1}$) will repeat, leading to exactly the same hash values and
consequently larger estimation variance. However, if $\mathcal{B}_{1}$ is an
empty bin, then we still have $1/m$ chance of using the same permutation to
generate hashes from a same non-empty bin (densification bin collision), where
$m$ is the number of non-empty bins in total. This would slightly increase the
variance of C-OPH from the rigorous theoretical perspective. Nonetheless, in
most practical cases where $f=|\bm{v}\cup\bm{w}|$ is not very small (i.e., not
extremely sparse data in the absolute scale), the impact of the densification
bin collision would be negligible (e.g., see our empirical verification). To
sum up, the variance reduction of C-OPH is valid rigorously when $MK\leq D$,
and is true empirically even when $MK>D$.

Figure 3: Empirical Mean Squared Error (MSE) of simulated data pairs,
$D=2^{12}$, $f=|\bm{v}\cup\bm{w}|=2^{11}$, with various $J$. 1st row:
$K=2^{5}$. 2nd row: $K=2^{7}$. We confirm that the MSE of C-OPH is smaller
than that of ReDen in all cases.

In Figure 3, we plot the empirical MSE of C-OPH versus ReDen on several
synthetic binary data pairs to demonstrate the variance reduction effect and
justify the theory. Here we simulate data vectors with various dimensionality
$D$ and Jaccard similarity values. The bin split is realized by a random
permutation on all data elements. We validate that C-OPH can indeed incur
smaller estimation variance than ReDen. More numerical examples on real-world
data can be found in Section 4 (Figure 5 and 6).

##  4 Practical Implementation

So far, our discussion has assumed that we have access to a uniformly random
bin split. One can certainly achieve this by doing a random permutation on the
data vector, and then split non-zero elements into different bins based on
their permuted location. In practice, however, applying exact permutations
might not be desirable when the data dimensionality is extremely large, due to
the high memory consumption to store the “permutation vector”. Instead, using
hash functions to approximate random permutations is a common choice, which
waves the need to store explicitly the permutation. In this section, we
provide some discussion on the practical implementation of C-OPH, to show how
hash functions can be effectively used in C-OPH. Recall that, C-MinHash (Li
and Li, 2021b, a) can reduce the $K$ permutations used in standard MinHash to
merely one permutation, allowing the efficient usage of one “permutation
vector” such that the practical estimation always matches the theory.
Interestingly, when combined with OPH, our proposed C-OPH can further reduce
the number of permutations used to just “$1/K$”, practically speaking.

###  4.1 When shall we use hash functions?

In many applications involving very high ($D$) dimensional data, storing exact
random permutations may be too costly. A simple alternative is to use simple
hash functions to approximate the permutations. It is well-known that, in some
cases, simply replacing the permutations with hash functions in MinHash may
lead to undesirable and systematic estimation inconsistencies. However,
interestingly as shown in Figure 4, for C-MinHash-$(\sigma,\pi)$, we can
safely replace the first permutation $\sigma$ by simple 2-universal (2U)
hashing.

Figure 4: Mean Squared Error (MSE) of C-MinHash-$(\sigma,\pi)$,
C-MinHash-$(2U,\pi)$ and C-MinHash-$(\sigma,2U)$ on data pairs from the Words
dataset (Li and Church, 2005), with various $J$. We see that replacing the
initial (pre-processing) permutation $\sigma$ by a 2U hash function (i.e.,
C-MinHash-$(2U,\pi)$) gives virtually the same estimation MSE as
C-MinHash-$(\sigma,\pi)$. However, replacing the second permutation $\pi$ by
2U (i.e., C-MinHash-$(\sigma,2U)$) leads to larger estimation errors. In each
plot, the two vectors from Li and Church (2005) denote whether the words
appear in the documents of the repository.

Here, the 2U hash function is defined by $\mathcal{H}:[D]\mapsto[D]$ for a
non-negative integer $x\in[D]$: $\mathcal{H}(x)=ax+b\ \text{mod}\ p$, where
$p>D$ is a prime number, $a$ and $b$ are uniformly chosen from
$\\{0,1,...,p-1\\}$ and $a$ is odd. There are also known tricks to avoid the
modulo operations. As shown in Figure 4, for C-MinHash-$(\sigma,\pi)$, we can
safely replace by the first permutation $\sigma$ by 2U hash. However, we can
observe obvious performance deviations once we place the second permutation
$\pi$ by 2U hash (i.e., C-MinHash-$(\sigma,2U)$). We have experimented with
other simple hashing functions including 4-universal hashing and murmur
hashing, but the observations are essentially very similar to using 2U
hashing.

###  4.2 From One Permutation to “$1/K$” Permutation

Therefore, we naturally develop C-OPH-$(2U,\pi)$. That is, we can replace the
initial permutation $\sigma$ in the original C-OPH-$(\sigma,\pi)$. This means,
we actually just need “$1/K$” permutation instead of one permutation. This
might need to a substantial convenience in pratice. For example, if $D=2^{40}$
and $K=2^{10}$, then we just need one short permutation of size $D/K=2^{30}$,
which is small enough even for GPU memory.

Figure 5 and Figure 6 provide another set of experiments for sanity check: (i)
C-OPH-$(\sigma,\pi)$ improves “ReDen” the prior best densification (Li et al.,
2019); (2) The “$1/K$ permutation version C-OPH-$(2U,\pi)$ performs
essentially the same as C-OPH-$(\sigma,\pi)$, using the same “Words” dataset
(Li and Church, 2005). From the plots with various $K$, we validate again that
the proposed C-OPH provides smaller estimation MSEs than ReDen. Furthermore,
using hash function for bin split (C-OPH-$(2U,\pi)$) essentially gives same
empirical accuracy as the standard C-OPH-$(\sigma,\pi)$.

Figure 5: Mean Squared Error (MSE) of ReDen, C-OPH-$(\sigma,\pi)$ and
C-OPH-$(2U,\pi)$ on word pairs from the Words dataset, $K=2^{7}$. We see that
C-OPH improves the MSE of ReDen, and using hash function to perform bin split
empirically gives same MSE as using perfectly random permutation.

Figure 6: Mean Squared Error (MSE) of ReDen, C-OPH-$(\sigma,\pi)$ and
C-OPH-$(2U,\pi)$ on word pairs from the Words dataset, $K=2^{9}$. We see that
C-OPH improves the MSE of ReDen, and using hash function to perform bin split
empirically gives same MSE as using perfectly random permutation.

##  5 Conclusion

The popular minwise hashing (MinHash) method has been improved by the so-
called Circulant MinHash (C-MinHash) (Li and Li, 2021b, a). To generate $K$
hash values, C-MinHash only needs two permutations or even just one
permutation, instead of using $K$ independent permutations as required by the
standard MinHash. It is clear that C-MinHash is different from the previous
known work on “One Permutation Hashing” (OPH) (Li et al., 2012) and its
variants (due to different “densification” schemes). In this paper, by
incorporating the central ideas of circulant permutations, we propose
Circulant OPH (C-OPH) to improve the accuracy of the state-of-the-art
densified OPH, i.e., the “ReDen” method developed in Li et al. (2019).

The basic idea of Circulant OPH (C-OPH) is to first randomly divide the data
vectors into equal-sized $K$ bins, then use a smaller permutation (of size
$D/K$, where $D$ is the data dimension) to generate the required number of
hash values in a circulant manner. We show that the proposed C-OPH achieves a
smaller estimation variance than “ReDen”, the previous best (most accurate)
densified OPH algorithm. In addition to achieving improved estimation
accuracy, another interesting benefit of C-OPH is that, practically speaking,
C-OPH just needs “$1/K$” permutation instead of one permutation. This
consequence would be useful in practice. For example, consider a dataset with
$D=2^{40}$ and $K=2^{10}$. Then we just need a small permutation of size
$D/K=2^{30}$ for this high-dimensional dataset, and $2^{30}$ is small even for
the GPU memory.

## References

  * 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.
  * Broder (1997) Andrei Z. Broder.  On the resemblance and containment of documents.  In _Proceedings of the Conference on Compression and Complexity of SEQUENCES_ , pages 21–29, Positano, Amalfitan Coast, Salerno, Italy, 1997\.
  * Broder et al. (1997) Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, and Geoffrey Zweig.  Syntactic clustering of the web.  _Comput. Networks_ , 29(8-13):1157–1166, 1997\.
  * 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 communities.  In _Proceedings of the International Conference on Web Search and Web Data Mining (WSDM)_ , pages 95–106, Stanford, CA, 2008.
  * 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.
  * Chum and Matas (2012) Ondrej Chum and Jiri Matas.  Fast computation of min-hash signatures for image collections.  In _Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 3077–3084, Providence, RI, 2012.
  * Das et al. (2007) Abhinandan Das, Mayur Datar, Ashutosh Garg, and Shyamsundar Rajaram.  Google news personalization: scalable online collaborative filtering.  In _Proceedings of the 16th International Conference on World Wide Web (WWW)_ , pages 271–280, Banff, Canada, 2007.
  * Deng et al. (2012) Fan Deng, Stefan Siersdorfer, and Sergej Zerr.  Efficient jaccard-based diversity analysis of large document collections.  In _Proceedings of the 21st ACM International Conference on Information and Knowledge Management (CIKM)_ , pages 1402–1411, Maui, HI, 2012\.
  * Feng and Deng (2021) Weiqi Feng and Dong Deng.  Allign: Aligning all-pair near-duplicate passages in long texts.  In _Proceedings of the International Conference on Management of Data (SIGMOD)_ , pages 541–553, Virtual Event, China, 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.
  * Jia et al. (2021) Peng Jia, Pinghui Wang, Junzhou Zhao, Shuo Zhang, Yiyan Qi, Min Hu, Chao Deng, and Xiaohong Guan.  Bidirectionally densifying LSH sketches with empty bins.  In _Proceedings of the International Conference on Management of Data (SIGMOD)_ , pages 830–842, Virtual Event, China, 2021.
  * Lee et al. (2010) David C. Lee, Qifa Ke, and Michael Isard.  Partition min-hash for partial duplicate image discovery.  In _Proceedings of the 11th European Conference on Computer Vision (ECCV), Part I_ , pages 648–662, Heraklion, Crete, Greece, 2010.
  * Lemiesz (2021) Jakub Lemiesz.  On the algebra of data sketches.  _Proc. VLDB Endow._ , 14(9):1655–1667, 2021\.
  * 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 Church (2007) Ping Li and Kenneth Ward Church.  A sketch algorithm for estimating two-way and multi-way associations.  _Comput. Linguistics_ , 33(3):305–354, 2007.
  * Li and König (2011) Ping Li and Arnd Christian König.  Theory and applications of _b_ -bit minwise hashing.  _Commun. ACM_ , 54(8):101–109, 2011.
  * Li et al. (2011) Ping Li, Anshumali Shrivastava, Joshua Moore, and Arnd Christian König.  Hashing algorithms for large-scale learning.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 2672–2680, Granada, Spain, 2011.
  * Li et al. (2012) Ping Li, Art B Owen, and Cun-Hui Zhang.  One permutation hashing.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 3122–3130, Lake Tahoe, NV, 2012.
  * 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 and Li (2021a) Xiaoyun Li and Ping Li.  C-MinHash: Practically reducing two permutations to just one.  _arXiv preprint arXiv:2109.04595_ , 2021a.
  * Li and Li (2021b) Xiaoyun Li and Ping Li.  C-MinHash: Rigorously reducing $k$ permutations to two.  _arXiv preprint arXiv:2109.03337_ , 2021b.
  * Nargesian et al. (2018) Fatemeh Nargesian, Erkang Zhu, Ken Q. Pu, and Renée J. Miller.  Table union search on open data.  _Proc. VLDB Endow._ , 11(7):813–825, 2018.
  * Shrivastava (2017) Anshumali Shrivastava.  Optimal densification for fast and accurate minwise hashing.  In _Proceedings of the 34th International Conference on Machine Learning (ICML)_ , pages 3154–3163, Sydney, Australia, 2017.
  * 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, 2012\.
  * Shrivastava and Li (2014a) Anshumali Shrivastava and Ping Li.  Densifying one permutation hashing via rotation for fast near neighbor search.  In _Proceedings of the 31th International Conference on Machine Learning (ICML)_ , Beijing, China, 2014a.
  * Shrivastava and Li (2014b) Anshumali Shrivastava and Ping Li.  Improved densification of one permutation hashing.  In _Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence (UAI)_ , Quebec City, Canada, 2014b.
  * Tamersoy et al. (2014) Acar Tamersoy, Kevin A. Roundy, and Duen Horng Chau.  Guilt by association: large scale malware detection by mining file-relation graphs.  In _Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)_ , pages 1524–1533, New York, NY, 2014.
  * Tseng et al. (2021) Tom Tseng, Laxman Dhulipala, and Julian Shun.  Parallel index-based structural graph clustering and its approximation.  In _Proceedings of the International Conference on Management of Data (SIGMOD)_ , pages 1851–1864, Virtual Event, China, 2021.
  * Wang et al. (2019) Pinghui Wang, Yiyan Qi, Yuanming Zhang, Qiaozhu Zhai, Chenxu Wang, John C. S. Lui, and Xiaohong Guan.  A memory-efficient sketch method for estimating high similarities in streaming sets.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD)_, pages 25–33, Anchorage, AK, 2019.
  * Zhu et al. (2017) Erkang Zhu, Ken Q. Pu, Fatemeh Nargesian, and Renée J. Miller.  Interactive navigation of open data linkages.  _Proc. VLDB Endow._ , 10(12):1837–1840, 2017\.