Differentially Private One Permutation Hashing

## Abstract

Abstract Minwise hashing (MinHash) is a standard algorithm widely used in the industry, for large-scale search and learning applications with the binary (0/1) Jaccard similarity. One common use of MinHash is for processing massive n-gram text representations so that practitioners do not have to materialize the original data (which would be prohibitive). Another popular use of MinHash is for building hash tables to enable sub-linear time approximate near neighbor (ANN) search. MinHash has also been used as a tool for building large-scale machine learning systems. The standard implementation of MinHash requires applying K 𝐾 K italic_K random permutations. In comparison, the method of one permutation hashing (OPH, developed in 2012), is an efficient alternative of MinHash which splits the data vectors into K 𝐾 K italic_K bins and generates hash values within each bin. OPH is substantially more efficient and also more convenient to use. In many practical scenarios, practitioners can simply store one perfect random permutation as opposed to storing K 𝐾 K italic_K permutations or resorting to approximate random permutations such as universal hashing. In this paper, we combine the differential privacy (DP) with OPH (as well as MinHash), to propose the DP-OPH framework with three variants: DP-OPH-fix, DP-OPH-re and DP-OPH-rand, depending on which densification strategy is adopted to deal with empty bins in OPH. A detailed roadmap to the algorithm design is presented along with the privacy analysis. An analytical comparison of our proposed DP-OPH methods with the DP minwise hashing (DP-MH) is provided to justify the advantage of DP-OPH. Experiments on similarity search confirm the merits of DP-OPH, and guide the choice of the proper variant in different practical scenarios. Our technique is also extended to bin-wise consistent weighted sampling (BCWS) to develop a new DP algorithm called DP-BCWS for non-binary data. Experiments on classification tasks (logistic regression and neural nets) demonstrate that DP-BCWS is able to achieve excellent utility at around ϵ = 5 ∼ 10 italic-ϵ 5 similar-to 10 \epsilon=5\sim 10 italic_ϵ = 5 ∼ 10 , where ϵ italic-ϵ \epsilon italic_ϵ is the standard parameter in the language of ( ϵ , δ ) italic-ϵ 𝛿 (\epsilon,\delta) ( italic_ϵ , italic_δ ) -DP.

## 1 Introduction

Let $\bm{u},\bm{v}\in\{0,1\}^{D}$ be two $D$-dimensional binary vectors. In this paper, we first focus on hashing algorithms for the binary Jaccard similarity (a.k.a. the “resemblance”) defined as

$$ $J(\bm{u},\bm{v})=\frac{\sum_{i=1}^{D}\mathbbm{1}\{u_{i}=v_{i}=1\}}{\sum_{i=1}^ {D}\mathbbm{1}\{u_{i}+v_{i}\geq 1\}}.$ (1) $$

This is a widely used similarity metric in machine learning and web applications. For example, the vectors $\bm{u}$ and $\bm{v}$ can be viewed as two sets of items represented by the locations of non-zero entries. In industrial applications with massive data size, directly calculating the pairwise Jaccard similarity among the data points becomes too costly as the sample size grows. To accelerate large-scale search and learning, the celebrated “minwise hashing” (MinHash) algorithm (Broder, ; Broder et al., , ; Li and Church, ; Li and König, ) is a standard hashing technique for approximating the Jaccard similarity in massive binary datasets. It has seen numerous applications such as near neighbor search, duplicate detection, malware detection, clustering, large-scale learning, social networks, and computer vision (Charikar, ; Fetterly et al., ; Das et al., ; Buehrer and Chellapilla, ; Bendersky and Croft, ; Chierichetti et al., ; Pandey et al., ; Lee et al., ; Deng et al., ; Chum and Matas, ; He et al., ; Tamersoy et al., ; Shrivastava and Li, ; Zhu et al., ; Nargesian et al., ; Wang et al., ; Lemiesz, ; Feng and Deng, ; Jia et al., ).

The outputs of MinHash are integers. For large-scale applications, to store and use the hash values more conveniently and efficiently, Li and König () proposed $b$-bit MinHash that only stores the lowest $b$ bits of the hashed integers, which is memory-efficient and convenient for similarity search and machine learning. In recent years, $b$-bit MinHash has become a standard implementation of MinHash (Li et al., , ; Shah and Meinshausen, ; Yu and Weber, ). In addition, we would like to mention “circulant MinHash” (C-MinHash) (Li and Li, ) which, by using only one permutation circularly, improved the hashing efficiency and, perhaps surprisingly, also improved the estimation accuracy. However, the mechanism behind C-MinHash is different from (or even orthogonal to) what is commonly known as the “one permutation hashing” (OPH).

### 1.1 One Permutation Hashing (OPH)

To use MinHash in practice, we need to generate $K$ hash values to achieve good utility. This requires applying $K$ random permutations (or hash functions as approximations) per data point, yielding an $O(Kf)$ complexity where $f$ is the average number of non-empty entries of the data vectors. The method of one permutation hashing (OPH) (Li et al., ) provides a way to significantly reduce the complexity to $O(f)$. The idea of OPH is: to generate $K$ hashes, we split the data vector into $K$ non-overlapping bins, and conduct MinHash within each bin. However, since the data are sparse, some bins might be empty. To deal with empty bins, various densification schemes (Shrivastava and Li, , ; Shrivastava, ; Li et al., ; Jia et al., ) have been proposed that fill the empty bins (e.g., with values from non-empty bins). It is shown that OPH with densification also provides unbiased Jaccard similarity estimation, and interestingly the estimation variance of certain densification algorithms might be even smaller than that of the standard MinHash. Owing to its much improved efficiency, OPH has been widely used as an alternative in practice for replacing MinHash (Dahlgaard et al., ; Zhao et al., ; Tseng et al., ; Jiang et al., ). We also note that, OPH can be further improved by adopting the idea of “circulation”, to become the “C-OPH” algorithm (Li and Li, ).

### 1.2 Non-binary Data and Bin-wise Consistent Weighted Sampling (BCWS)

MinHash and OPH handle binary data (unweighted sets). In the literature, the weighted Jaccard similarity is a popular extension to the real-valued data (weighted sets), defined as

$$ $\displaystyle J_{w}(\bm{u},\bm{v})=\frac{\sum_{i=1}^{D}\min\{u_{i},v_{i}\}}{ \sum_{i=1}^{D}\max\{u_{i},v_{i}\}},$ $$

where $\bm{u},\bm{v}\in\mathbb{R}_{+}^{D}$ be two non-negative data vectors. Since weighted data usually contains richer information than binary data, the weighted Jaccard has also been studied and used in many areas including theory, databases, machine learning, and information retrieval (Kleinberg and Tardos, ; Charikar, ; Fetterly et al., ; Gollapudi and Sharma, ; Bollegala et al., ; Delgado et al., ; Schubert et al., ; Wang et al., ; Fu et al., ; Pewny et al., ; Manzoor et al., ; Raff and Nicholas, ; Tymoshenko and Moschitti, ; Bag et al., ; Pouget-Abadie et al., ; Yang et al., ; Zhu et al., ; Fuchs et al., ; Lei et al., ; Li et al., ; Zheng et al., ). Particularly, the weighted Jaccard similarity has been shown to be a powerful non-linear kernel in large-scale classification and regression (Li, ). It may outperform the popular RBF kernel on many tasks/datasets.

Correspondingly, large-scale hashing algorithms have also been developed for the efficient estimation/approximation of the weighted Jaccard similarity. A series of works (Kleinberg and Tardos, ; Charikar, ; Shrivastava, ; Ertl, ; Li and Li, ) proposed and refined the hashing algorithm using the rejection sampling technique which is efficient on dense data vectors. Gollapudi and Panigrahy (); Manasse et al. (); Ioffe () developed Consistent Weighted Sampling (CWS, Algorithm [7](#alg7)), which has $O(Kf)$ complexity same as that of MinHash and runs efficiently on relatively sparse data. Li et al. () proposed Extremal Sampling (ES) built upon the extremal stochastic process. Li et al. () extended the “binning + densification” idea of OPH to CWS, and proposed Bin-wise Consistent Weighted Sampling (BCWS) with $O(f)$ complexity, i.e., roughly $K$-fold speedup compared to standard CWS.

### 1.3 Hashing/Sketching and Differential Privacy

At a higher level, MinHash, OPH and BCWS all belong to the broad family of hashing/sketching methods which generate sketches for data samples that are designed for various applications. Examples of sketching methods include the random projection (RP) based methods for estimating the $l_{2}$ distance, the inner product/cosine and their non-linear transformations (Goemans and Williamson, ; Charikar, ; Datar et al., ; Vempala, ; Rahimi and Recht, ; Li et al., ; Li, ; Li and Li, ), the count-sketch (CS) for frequency estimation (Charikar et al., ), and the Flajolet-Martin (FM) sketch (Flajolet and Martin, ) and HyperLogLog sketch (Flajolet et al., ) for cardinality estimation, etc. Since the data sketches produce “summaries” of the data which contain the original data information, protecting the privacy of the data sketches becomes an important topic that has gained growing research interest in recent years.

The differential privacy (DP) (Dwork et al., ) has become a standard privacy definition with rigorous mathematical formulation, which is widely applied to clustering, regression and classification, principle component analysis, matrix completion, optimization and deep learning (Blum et al., ; Chaudhuri and Monteleoni, ; Feldman et al., ; Gupta et al., ; Chaudhuri et al., ; Kasiviswanathan et al., ; Zhang et al., ; Abadi et al., ; Agarwal et al., ; Ge et al., ; Wei et al., ; Dong et al., ; Fan et al., ), etc. Moreover, prior efforts have also been conducted to combine differential privacy with the aforementioned hashing algorithms, including RP (Blocki et al., ; Kenthapadi et al., ; Stausholm, ; Li and Li, ), count-sketch (Zhao et al., ), and FM sketch (Smith et al., ; Dickens et al., ). Recently, Aumüller et al. () proposed DP for MinHash. Although their design does not satisfy DP, we will make an important (and technically minor) fix for their method. The revised method is named DP-MH and will be compared with DP-OPH, our proposed DP algorithms for OPH.

Among those DP algorithms for sketching/hashing, some works (e.g., Blocki et al. (); Smith et al. (); Dickens et al. ()) assumed “internal randomness”, i.e., the randomness of the hash functions are kept private, and showed that some hashing methods themselves already possess strong DP property, when there is a sufficient number of elements in the data vector (e.g., for the FM sketch) or the data matrix has sufficiently large eigenvalues. However, this setting is more restrictive in practice since it requires that the hash keys or projection matrices cannot be accessed by any adversary. In another setup (e.g., Kenthapadi et al. (); Aumüller et al. (); Stausholm (); Zhao et al. (); Li and Li ()), both the randomness of the hash functions and the algorithm outputs are treated as public information, and perturbation mechanisms are developed to make the corresponding hashing algorithms differentially private.

### 1.4 Our Contributions

In this paper, we mainly focus on the differential privacy of one permutation hashing (OPH), for hashing the binary Jaccard similarity. We consider the practical and general setup where the randomness (e.g., the permutation) of the algorithm is “external” and public. We develop three variants under the DP-OPH framework, DP-OPH-fix, DP-OPH-re, and DP-OPH-rand, corresponding to fixed densification, re-randomized densification, and random-bit densification for OPH, respectively. We provide detailed algorithm design and privacy analysis for each variant, and compare them with the DP MinHash (DP-MH) method. In our retrieval experiments, we show that the proposed DP-OPH method substantially improves DP-MH, and re-randomized densification (DP-OPH-re) is superior to fixed densification (DP-OPH-fix) in terms of differential privacy. The DP-OPH-rand variant performs the best when $\epsilon$ is small, while DP-OPH-re is the strongest competitor in the larger $\epsilon$ region. Here, $\epsilon$ is the standard parameter in the $(\epsilon,\delta)$-DP language. Moreover, we also empirically evaluate an extension of our method to the weighted Jaccard similarity called DP-BCWS for non-binary data. Experiments on classification demonstrate the effectiveness of the proposed methods in machine learning tasks under privacy constraints.

## 2 Background on MinHash, b 𝑏 b italic_b -bit Coding, and Differential Privacy

Figure: Algorithm 1 Minwise hashing (MinHash)

Minwise hashing (MinHash). The algorithm is summarized in Algorithm [1](#alg1). We first generate $K$ independent permutations $\pi_{1},...,\pi_{K}:[D]\mapsto[D]$, where the seeds ensure that all data vectors use the same set of permutations. Here, $[D]$ denotes $\{1,...,D\}$. For each permutation, the hash value is simply the first non-zero location in the permuted vector, i.e., $h_{k}(\bm{u})=\min_{i:v_{i}\neq 0}\pi_{k}(i)$, $\forall k=1,...,K$. Analogously, for another data vector $\bm{v}\in\{0,1\}^{D}$, we also obtain $K$ hash values, $h_{k}(\bm{v})$.

The MinHash estimator of $J(\bm{u},\bm{v})$ is the average over the hash collisions:

$$ $\displaystyle\hat{J}_{MH}(\bm{u},\bm{v})=\frac{1}{K}\sum_{k=1}^{K}\mathbbm{1} \{h_{k}(\bm{u})=h_{k}(\bm{v})\},$ (2) $$

where $\mathbbm{1}\{\cdot\}$ is the indicator function. By some standard probability calculations, we can show that

$$ $\displaystyle\mathbb{E}[\hat{J}_{MH}]=J,\hskip 28.90755ptVar[\hat{J}_{MH}]= \frac{J(1-J)}{K}.$ $$

$b$-bit coding of the hash value. Li and König () proposed “$b$-bit minwise hashing” as a convenient coding strategy for the integer hash value $h(\bm{u})$ generated by MinHash (or by OPH which will be introduced later). Basically, we only keep the lowest $b$ bits of each hash value. In our analysis, for convenience, we assume that “taking the lowest $b$-bits” can be achieved by some “rehashing” trick to map the integer values onto $\{0,...,2^{b}-1\}$ uniformly. There are at least three benefits of this coding strategy: (i) storing only $b$ bits saves the storage cost compared with storing the full 32 or 64 bit values; (ii) the lowest few bits are more convenient for the purpose of indexing, e.g., in approximate nearest neighbor search (Indyk and Motwani, ; Shrivastava and Li, , ); (iii) we can transform the lowest few bits into a positional representation, allowing us to approximate the Jaccard similarity by the inner product of the hashed data, which is required by training large-scale linear models (Li et al., ). In this work, we will adopt this $b$-bit coding strategy in our private algorithm design.

Differential privacy (DP). Differential privacy (DP) provides a rigorous mathematical definition on the privacy of a randomized algorithm. Its formal definition is as follows.

###### Definition 2.1 (Differential privacy (Dwork et al., 2006b ) ) .

For a randomized algorithm $\mathcal{M}:\mathcal{U}\mapsto Range(\mathcal{M})$ and $\epsilon,\delta\geq 0$, if for any two neighboring data $u$ and $u^{\prime}$, it holds that

$$ $Pr[\mathcal{M}(u)\in Z]\leq e^{\epsilon}Pr[\mathcal{M}(u^{\prime})\in Z]+\delta$ (3) $$

for $\forall Z\subset Range(\mathcal{M})$,
then algorithm $\mathcal{M}$ is said to satisfy $(\epsilon,\delta)$-differentially privacy. If $\delta=0$, $\mathcal{M}$ is called $\epsilon$-differentially private.

Intuitively, DP requires that the distributions of the outputs before and after a small change in the data are similar such that an adversary cannot detect the change based on the outputs with high confidence. Smaller $\epsilon$ and $\delta$ implies stronger privacy. The parameter $\delta$ is usually interpreted as the “failure probability” allowed for the $\epsilon$-DP guarantee to be violated. In our work, we follow the standard definition in the DP literature of “neighboring” for binary data vectors, e.g., Dwork et al. (); Kenthapadi et al. (); Xu et al. (); Dwork and Roth (); Smith et al. (); Stausholm (); Dickens et al. (); Zhao et al. (); Li and Li (), that two data vectors are adjacent if they differ in one element. The formal statement is as below.

###### Definition 2.2 (Neighboring data) .

$\bm{u},\bm{u}^{\prime}\in\{0,1\}^{D}$ are neighboring data vectors if they only differ in one element, i.e., $u_{i}\neq u_{i}^{\prime}$ for one $i\in[D]$ and $u_{j}=u_{j}^{\prime}$ for $j\neq i$.

###### Definition 2.1 (Differential privacy (Dwork et al., 2006b ) ) .

###### Definition 2.2 (Neighboring data) .

## 3 Hashing for Jaccard Similarity with Differential Privacy (DP)

As discussed earlier, one permutation hashing (OPH) (Li et al., ) is a popular and highly efficient hashing algorithm for the Jaccard similarity. In this section, we present our main algorithms called DP-OPH based on privatizing the $b$-bit hash values from OPH. In addition, we compare it with a differentially private MinHash alternative named DP-MH.

### 3.1 One Permutation Hashing (OPH)

Figure: Algorithm 2 One Permutation Hashing (OPH)

As outlined in Algorithm [2](#alg2), the procedure of OPH is simple: we first use a permutation $\pi$ (same for all data vectors) to randomly split the feature dimensions $[D]$ into $K$ bins $\mathcal{B}_{1},...,\mathcal{B}_{K}$ with equal length $d=D/K$ (assuming integer division holds). Then, for each bin $\mathcal{B}_{k}$, we set the minimal permuted index of “1” as the $k$-th OPH hash value. If $\mathcal{B}_{k}$ is empty (i.e., it does not contain any “1”), we record an “$E$” representing an empty bin. Li et al. () showed that we can construct statistically unbiased Jaccard estimators by ignoring the empty bins (i.e., subtracting $K$ by the number of “jointly” empty bins). However, since empty bins are different for every distinct data vector, the vanilla OPH hash values do not form a metric space (i.e., do not satisfy the triangle inequality). This limits the application of this naive estimator.

Figure: Algorithm 3 Densification for OPH, two options: fixed and re-randomized

Densification for OPH. To tackle the issue caused by empty bins, a series of works have been conducted to densify the OPH (Shrivastava and Li, , ; Shrivastava, ; Li et al., ; Jia et al., ). The general idea is to “borrow” the data/hash from non-empty bins, with some careful design. In Algorithm [3](#alg3), we present two recent representatives of OPH densification methods: “fixed densification” (Shrivastava, ) and “ re-randomized densification” (Li et al., ). We call these two variants OPH-fix and OPH-re, respectively. Given an OPH hash vector from Algorithm [2](#alg2) (possibly containing “$E$”s), we denote the set of non-empty bins $NonEmptyBin=\{k\in[K]:h_{k}(\bm{u})\neq E\}$. The densification procedure scans over $k=1,...,K$. For each $k$ with $h_{k}(\bm{u})=E$, we do the following.

- 1.
Uniformly randomly pick a bin $k^{\prime}\in NonEmptyBin$ that is non-empty.
- 2.
(a)
OPH-fix: we directly copy the $k^{\prime}$-th hash value: $h_{k}(\bm{u})\leftarrow h_{k^{\prime}}(\bm{u})$.
(b)
OPH-re: we apply an additional minwise hashing to bin $\mathcal{B}_{k^{\prime}}$ using the “partial permutation” of $\mathcal{B}_{k}$ to obtain the hash for $h_{k}(\bm{u})$.

More precisely, for re-randomized densification, in Algorithm [3](#alg3), $MapToIndex$ defines the “partial permutation” of bin $\mathcal{B}_{k}$, where the function $SortedIndex$ returns the original index of a sorted array. For example, let $D=16$, $K=4$, and $d=D/K=4$ and suppose the indices in each bin are in ascending order, and $\mathcal{B}_{2}=[1,5,13,15]$ is empty. Suppose $\pi(13)=5,\pi(5)=6,\pi(1)=7,\pi(15)=8$. In this case, $\pi(\mathcal{B}_{2})=[7,6,5,8]$, so $SortedIndex(\pi(\mathcal{B}_{2}))=[3,2,1,4]$. Assume $k^{\prime}=3$ is picked and $\pi(\mathcal{B}_{3})=[9,12,10,11]$. At line 7 we have $MapToIndex=[11,10,9,12]$ and at line 8, $\pi^{(2)}$ is a mapping $[9,12,10,11]\mapsto[11,10,9,12]$, which effectively defines another within-bin permutation of $\pi(\mathcal{B}_{3})$ using the partial ordering of $\pi(\mathcal{B}_{2})$. Finally, we set $h_{k}(\bm{u})$ as the minimal index of “1” among the additionally permuted elements in bin $\mathcal{B}_{k^{\prime}}$.

We remark that in the above step 1, for any empty bin $k$, the “sequence” for non-empty bin lookup should be the same for any data vector. In practice, this can be achieved by simply seeding a random permutation of $[K]$ for each $k$. For instance, for $k=1$ (when the first bin is empty), we always search in the order $[3,1,2,4]$ until one non-empty bin is found, for all the data vectors.

It is shown that for both variants, the Jaccard estimator of the same form as ([2](#S2.E2)) is unbiased. In Li et al. (), the authors proved that re-randomized densification always achieves a smaller Jaccard estimation variance than that of fixed densification, and the improvement is especially significant when the data is sparse. Similar to $b$-bit minwise hashing, we can also keep the lowest $b$ bits of the OPH hash values to use them conveniently in search and learning applications.

### 3.2 Differential Private One Permutation Hashing (DP-OPH)

Figure: Algorithm 4 Differentially Private Densified One Permutation Hashing (DP-OPH-fix, DP-OPH-re)

DP-OPH with densification. To privatize densified OPH, in Algorithm [4](#alg4), we first take the lowest $b$ bits of the hash values. Since the output space is finite with cardinality $2^{b}$, we apply the standard randomized response technique (Warner, ; Dwork and Roth, ; Wang et al., ) to flip the bits to achieve DP. After running Algorithm [3](#alg3), suppose a densified OPH hash value $h_{k}(\bm{u})=j$ with some $j\in 0,...,2^{b}-1$. With some $\epsilon^{\prime}>0$ that will be specified later, we output $\tilde{h}_{k}(\bm{u})=j$ with probability $\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+2^{b}-1}$, and $\tilde{h}_{k}(\bm{u})=i$ for $i\neq j$ with probability $\frac{1}{e^{\epsilon^{\prime}}+2^{b}-1}$. It is easy to verify that, for a neighboring data $\bm{u}^{\prime}$, when $h_{k}(\bm{u}^{\prime})=j$, for $\forall i\in 0,...,2^{b}-1$, we have $\frac{P(\tilde{h}_{k}(\bm{u})=i)}{P(\tilde{h}_{k}(\bm{u}^{\prime})=i)}=1$; when $h_{k}(\bm{u}^{\prime})\neq j$, we have $e^{-\epsilon^{\prime}}\leq\frac{P(\tilde{h}_{k}(\bm{u})=i)}{P(\tilde{h}_{k}(
\bm{u}^{\prime})=i)}\leq e^{\epsilon^{\prime}}$. Therefore, for a single hash value, this bit flipping method satisfies $\epsilon^{\prime}$-DP.

It remains to determine $\epsilon^{\prime}$. Naively, since the perturbations (flipping) of the hash values are independent, by the composition property of DP (Dwork et al., ), we know that simply setting $\epsilon^{\prime}=\epsilon/K$ for all $K$ MinHash values would achieve overall $\epsilon$-DP (for the hashed vector). However, since $K$ is usually around hundreds, a very large $\epsilon$ value is required for this strategy to be useful. To this end, we can trade a small $\delta$ in the DP definition for a significantly reduced $\epsilon$. The key is to note that, not all the $K$ hashed bits will change after we switch from $\bm{u}$ to its neighbor $\bm{u}^{\prime}$. Assume each data vector contains at least $f$ non-zeros, which is realistic since many data in practice have both high dimensionality $D$ as well as many non-zero elements. Intuitively, when the data is not too sparse, $\bm{u}$ and $\bm{u}^{\prime}$ tend to be similar (since they only differ in one element). Thus, the number of different hash values from Algorithm [3](#alg3), $X=\sum_{k=1}^{K}\mathbbm{1}\{h_{k}(\bm{u})\neq h_{k}(\bm{u}^{\prime})\}$, can be upper bounded by some $N$ with high probability $1-\delta$. In the proof, this allows us to set $\epsilon^{\prime}=\epsilon/N$ in the flipping probabilities and count $\delta$ as the failure probability in $(\epsilon,\delta)$-DP. In Lemma [3.3](#S3.Thmtheorem3), we derive the precise probability distribution of $X$. Based on this result, in Algorithm [4](#alg4), we set $N=F_{fix}^{-1}(1-\delta;D,f,K)$ for DP-OPH-fix, $N=F_{re}^{-1}(1-\delta;D,f,K)$ for DP-OPH-re, where $F_{fix}(x)=P(X\leq x)$ is the cumulative mass function (CMF) of $X$ with OPH-fix (([4](#S3.E4)) + ([5](#S3.E5))), and $F_{re}$ is the cumulative mass function of $X$ with OPH-re (([4](#S3.E4)) + ([6](#S3.E6))). To prove Lemma [3.3](#S3.Thmtheorem3), we need the following two lemmas.

###### Lemma 3.1 ( Li et al. ( 2012 ) ) .

Let $f=|\{i:u_{i}=1\}|$, and $I_{emp,k}$ be the indicator function that the $k$-th bin is empty, and $N_{emp}=\sum_{k=1}^{K}I_{emp,k}$. Suppose $mod(D,K)=0$. We have

$$ $\displaystyle P\left(N_{emp}=j\right)$ $\displaystyle=\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}.$ $$

###### Lemma 3.2 ( Li et al. ( 2019 ) ) .

Conditional on the event that $m$ bins are non-empty, let $\tilde{f}$ be the number of non-zero elements in a non-empty bin. Denote $d=D/K$. The conditional probability distribution of $\tilde{f}$ is given by

$$ $\displaystyle P\left(\tilde{f}=j\big{|}m\right)$ $\displaystyle=\frac{{d\choose j}H(m-1,f-j|d)}{H(m,f|d)},\quad j=\max\{1,f-(m-1 )d\},...,\min\{d,f-m+1\},$ $$

where $H(\cdot)$ follows the recursion: for any $0<k\leq K$ and $0\leq n\leq f$,

$$ $\displaystyle H(k,n|d)=\sum_{i=\max\{1,n-(k-1)d\}}^{\min\{d,n-k+1\}}{d\choose i }H(k-1,n-i|d),\quad H(1,n|d)={d\choose n}.$ $$

The distribution of $X=\sum_{k=1}^{K}\mathbbm{1}\{h_{k}(\bm{u})\neq h_{k}(\bm{u}^{\prime})\}$ is given as below.

###### Lemma 3.3 .

Consider $\bm{u}\in\{0,1\}^{D}$, and denote $f=|\{i:u_{i}=1\}|$. Let $\bm{u}^{\prime}$ be a neighbor of $\bm{u}$. Denote $X=\sum_{k=1}^{K}\mathbbm{1}\{h_{k}(\bm{u})\neq h_{k}(\bm{u}^{\prime})\}$ where the hash values are generated by Algorithm [3](#alg3). Denote $d=D/K$. We have, for $x=0,...,K-\lceil f/d\rceil$,

$$ $\displaystyle P\left(X=x\right)=\sum_{j=\max(0,K-f)}^{K-\lceil f/d\rceil}\sum_ {z=1}^{\min(f,d)}\tilde{P}(x|z,j)P\left(\tilde{f}=z|K-j\right)P\left(N_{emp}=j \right),$ (4) $$

where $P\left(\tilde{f}=z|K-j\right)$ is given in Lemma [3.2](#S3.Thmtheorem2) and $P\left(N_{emp}=j\right)$ is from Lemma [3.1](#S3.Thmtheorem1). Moreover,

$$ For OPH-fix: $\displaystyle\tilde{P}(x|z,j)=\mathbbm{1}\{x=0\}\left(1-P_{\neq}\right)+ \mathbbm{1}\{x>0\}P_{\neq}\cdot g_{bino}\left(x-1;\frac{1}{K-j},j\right),$ (5) For OPH-re: $\displaystyle\tilde{P}(x|z,j)=\left(1-P_{\neq}\right)\cdot g_{bino}\left(x; \frac{P_{\neq}}{K-j},j\right)+P_{\neq}\cdot g_{bino}\left(x-1;\frac{P_{\neq}}{ K-j},j\right),$ (6) $$

where $g_{bino}(x;p,n)$ is the probability mass function of $Binomial(p,n)$ with $n$ trials and success rate $p$, and $P_{\neq}(z,b)=\left(1-\frac{1}{2^{b}}\right)\frac{1}{z}$.

###### Proof.

Without loss of generality, suppose $\bm{u}$ and $\bm{u}^{\prime}$ differ in the $i$-th dimension, and by the symmetry of DP, we can assume that $u_{i}=1$ and $u_{i}^{\prime}=0$. We know that $i$ is assigned to the $\lceil mod(\pi(i),d)\rceil$-th bin. Among the $K$ hash values, this change will affect all the bins that use the data/hash of the $k^{*}=\lceil mod(\pi(i),d)\rceil$-th bin (after permutation), both in the first scan (if it is non-empty) and in the densification process. Let $N_{emp}$ be the number of empty bins in $h(\bm{u})$, and $\tilde{f}$ be the number of non-zero elements in the $k^{*}$-th bin. We have, for $x=0,...,K-\lceil f/d\rceil$,

$$ $\displaystyle P\left(X=x\right)$ $\displaystyle=\sum_{j=\max(0,K-f)}^{K-\lceil f/d\rceil}\sum_{z=1}^{\min(f,d)}P \left(X=x\Big{|}\tilde{f}=z,N_{emp}=j\right)P\left(\tilde{f}=z,N_{emp}=j\right)$ $\displaystyle=\sum_{j=\max(0,K-f)}^{K-\lceil f/d\rceil}\sum_{z=1}^{\min(f,d)}P \left(X=x\Big{|}\tilde{f}=z,N_{emp}=j\right)P\left(\tilde{f}=z|K-j\right)P \left(N_{emp}=j\right),$ $$

where $P\left(\tilde{f}=z|K-j\right)$ is given in Lemma [3.2](#S3.Thmtheorem2) and $P\left(N_{emp}=j\right)$ can be calculated by Lemma [3.1](#S3.Thmtheorem1). To compute the first conditional probability, we need to compute the number of times the $k^{*}$-th bin is picked to generate hash values, and the hash values are different for $\bm{u}$ and $\bm{u}^{\prime}$. Conditional on $\{\tilde{f}=z,N_{emp}=j\}$, denote $\Omega=\{k:\mathcal{B}_{k}\ \text{is\ empty}\}$, and let $R_{k}$ be the non-empty bin used for the $k$-th hash value $h_{k}(\bm{u})$, which takes value in $[K]\setminus\Omega$. We know that $|\Omega|=j$. We can write

$$ $\displaystyle X=\mathbbm{1}\{h_{k^{*}}(\bm{u})\neq h_{k^{*}}(\bm{u}^{\prime}) \}+\sum_{k\in\Omega}\mathbbm{1}\{R_{k}=k^{*},h_{k}(\bm{u})\neq h_{k}(\bm{u}^{ \prime})\}.$ $$

Here we separate out the first term because the $k^{*}$-th hash always uses the $k^{*}$-bin. Note that the densification bin selection is uniform, and the bin selection is independent of the permutation for hashing. For the fixed densification, since the hash value $h_{k^{*}}(\bm{u})$ is generated and used for all hash values that use $\mathcal{B}_{k^{*}}$, we have

$$ $\displaystyle P\left(X=x\Big{|}\tilde{f}=z,N_{emp}j\right)=\mathbbm{1}\{x=0\} \left(1-P_{\neq}\right)+\mathbbm{1}\{x>0\}P_{\neq}\cdot g_{bino}\left(x-1; \frac{1}{K-j},j\right),$ $$

where $g_{bino}(x;p,n)$ is the probability mass function of the binomial distribution with $n$ trials and success rate $p$, and $P_{\neq}=P(h_{k^{*}}(\bm{u})\neq h_{k^{*}}(\bm{u}^{\prime}))=\left(1-\frac{1}{
2^{b}}\right)\frac{1}{z}$. Based on the same reasoning, for re-randomized densification, we have

$$ $\displaystyle P\left(X=x\Big{|}\tilde{f}=z,N_{emp}j\right)=\left(1-P_{\neq} \right)\cdot g_{bino}\left(x;\frac{P_{\neq}}{K-j},j\right)+P_{\neq}\cdot g_{ bino}\left(x-1;\frac{P_{\neq}}{K-j},j\right).$ $$

Combining all the parts completes the proof.
∎

The privacy guarantee of DP-OPH with densification is provided as below.

###### Theorem 3.4 .

Both DP-OPH-fix and DP-OPH-re in Algorithm [4](#alg4) achieve $(\epsilon,\delta)$-DP.

###### Proof.

Let $\bm{u}$ and $\bm{u}^{\prime}$ be neighbors only differing in one element. Denote $S=\{k\in[K]:h_{k}(\bm{u})\neq h_{k}(\bm{u}^{\prime})\}$ and $S^{c}=[K]\setminus S$. As discussed before, we can verify that for $k\in S_{c}$, we have $\frac{P(\tilde{h}_{k}(\bm{u})=i)}{P(\tilde{h}_{k}(\bm{u}^{\prime})=i)}=1$ for any $i=0,...,2^{b}-1$. For $k\in S$, $e^{-\epsilon^{\prime}}\leq\frac{P(\tilde{h}_{k}(\bm{u})=i)}{P(\tilde{h}_{k}(
\bm{u}^{\prime})=i)}\leq e^{\epsilon^{\prime}}$ holds for any $i=0,...,2^{b}-1$. Thus, for any $Z\in\{0,...,2^{b}-1\}^{K}$, the absolute privacy loss can be bounded by

$$ $\displaystyle\left|\log\frac{P(\tilde{h}(\bm{u})=Z)}{P(\tilde{h}(\bm{u}^{ \prime})=Z)}\right|=\left|\log\prod_{k\in S}\frac{P(\tilde{h}_{k}(\bm{u})=i)}{ P(\tilde{h}_{k}(\bm{u}^{\prime})=i)}\right|\leq|S|\epsilon^{\prime}=|S|\frac{ \epsilon}{N}.$ (7) $$

By Lemma [3.3](#S3.Thmtheorem3), we know that with probability at least $1-\delta$, $|S|\leq F_{fix}^{-1}(1-\delta)=N$ for DP-OPH-fix, and $|S|\leq F_{re}^{-1}(1-\delta)=N$ for DP-OPH-re, respectively. Hence, ([7](#S3.E7)) is upper bounded by $\epsilon$ with probability $1-\delta$. This proves the $(\epsilon,\delta)$-DP.
∎

DP-OPH without densification. From the practical perspective, we may also privatize the OPH without densification (i.e., add DP to the output of Algorithm [2](#alg2)). The first step is to take the lowest $b$ bits of every non-empty hash and get $K$ hash values from $\{0,...,2^{b}-1\}\cup\{E\}$. Then, for non-empty bins, we keep the hash value with probability $\frac{e^{\epsilon}}{e^{\epsilon}+2^{b}-1}$, and randomly flip it otherwise. For empty bins (i.e., $h_{k}(\bm{u})=E$), we simply assign a random value in $\{0,...,2^{b}-1\}$ to $\tilde{h}_{k}(\bm{u})$. The formal procedure of this so-called DP-OPH-rand method is summarized in Algorithm [5](#alg5).

Figure: Algorithm 5 Differentially Private One Permutation Hashing with Random Bits (DP-OPH-rand)

###### Theorem 3.5 .

Algorithm [5](#alg5) achieves $\epsilon$-DP.

###### Proof.

The proof is similar to the proof of Theorem [3.4](#S3.Thmtheorem4). Since the original hash vector $h(\bm{u})$ is not densified, there only exists exactly one hash value such that $h_{k}(\bm{u})\neq h_{k}(\bm{u})$ may happen for $\bm{u}^{\prime}$ that differs in one element from $\bm{u}$. W.l.o.g., assume $u_{i}=1$ and $u_{i}^{\prime}=0$, and $i\in\mathcal{B}_{k}$. If bin $k$ is non-empty for both $\bm{u}$ and $\bm{u}^{\prime}$ (after permutation), then for any $Z\in\{0,...,2^{b}-1\}^{K}$, $\left|\log\frac{P(\tilde{h}(\bm{u})=Z)}{P(\tilde{h}(\bm{u}^{\prime})=Z)}\right
|\leq\epsilon$ according to our analysis in Theorem [3.4](#S3.Thmtheorem4) (the probability of hash in $[K]\setminus\{k\}$ cancels out). If bin $k$ is empty for $\bm{u}^{\prime}$, since $1\leq\frac{e^{\epsilon}}{e^{\epsilon}+2^{b}-1}/\frac{1}{2^{b}}\leq e^{\epsilon}$ and $e^{-\epsilon}\leq\frac{1}{2^{b}}/\frac{1}{e^{\epsilon}+2^{b}-1}\leq 1$, we also have $\left|\log\frac{P(\tilde{h}(\bm{u})=Z)}{P(\tilde{h}(\bm{u}^{\prime})=Z)}\right
|\leq\epsilon$. Therefore, the algorithm is $\epsilon$-DP.
∎

Compared with Algorithm [4](#alg4), DP-OPH-rand has smaller bit flipping probability (effectively, $N\equiv 1$ in Algorithm [4](#alg4)). This demonstrates the essential benefit of “binning” in OPH, since the change in one data coordinate will only affect one hash value (if densification is not applied). As a consequence, the non-empty hash values are less perturbed in DP-OPH-rand than in DP-OPH-fix or DP-OPH-re. However, this comes with an extra cost as we have to assign random bits to empty bins, which do not provide useful information about the data. Moreover, this extra cost does not diminish as $\epsilon$ increases, because the number of empty bins only depends on the data and $K$. Our experiments in Section [4](#S4) will provide more intuition on properly balancing this trade-off in practice.

###### Lemma 3.1 ( Li et al. ( 2012 ) ) .

###### Lemma 3.2 ( Li et al. ( 2019 ) ) .

###### Lemma 3.3 .

###### Proof.

###### Theorem 3.4 .

###### Proof.

###### Theorem 3.5 .

###### Proof.

### 3.3 Differential Private MinHash (DP-MH)

Figure: Algorithm 6 Differentially Private Minwise hashing (DP-MH)

While we have presented our main contributions on the DP-OPH algorithms, we also discuss the DP MinHash (DP-MH) method (Algorithm [6](#alg6)) as a baseline comparison. The general mechanism of DP-MH is the same as densified DP-OPH . The main difference between Algorithm [6](#alg6) and Algorithm [4](#alg4) is in the calculation of $N$. In Algorithm [6](#alg6), we set $N=F_{bino}^{-1}(1-\delta;\frac{1}{f},K)$ where $F_{bino}(x;p,n)$ is the cumulative mass function of $Binomial(p,n)$ with $n$ trials and success probability $p$.

###### Theorem 3.6 .

Algorithm [6](#alg6) is $(\epsilon,\delta)$-DP.

###### Proof.

We use the same proof strategy for Theorem [3.4](#S3.Thmtheorem4). To compute the high probability bound on the number of difference hashes $X=\sum_{k=1}^{K}\mathbbm{1}\{h_{k}(\bm{u})\neq h_{k}(\bm{u}^{\prime})\}$ for two neighboring data vectors $\bm{u}$ and $\bm{u}^{\prime}$, note that in MinHash, $\mathbbm{1}\{h_{k}(\bm{u})\neq h_{k}(\bm{u}^{\prime})\}$ are independent Bernoulli random variables with success rate $1/f$. Thus, $X$ follows $Binomial(\frac{1}{f},K)$. With probability $1-\delta$, $X\leq F_{bino}^{-1}(1-\delta;\frac{1}{f},K)=N$. With this key quantity, the remaining part of the proof follows.
∎

In a related work, Aumüller et al. () also proposed to apply randomized response to MinHash. However, the authors incorrectly used a tail bound for the binomial distribution (see their Lemma 1) which is only valid for small deviation. In DP, $\delta$ is often very small (e.g., $10^{-6}$), so the large deviation tail bound should be used which is looser than the one used therein(^1^11For $X$ following a Binomial distribution with mean $\mu$, Aumüller et al. () used the concentration inequality $P(X\geq(1+\xi)\mu)\leq\exp(-\frac{\xi^{2}\mu}{3})$, which only holds when $0\leq\xi\leq 1$. For large deviations (large $\xi$), the valid Binomial tail bound should be $P(X\geq(1+\xi)\mu)\leq\exp(-\frac{\xi^{2}\mu}{\xi+2})$.). That said, in their paper, the perturbation is underdetermined and their method does not satisfy DP rigorously. In Algorithm [6](#alg6), we fix this by using the exact probability mass function to compute the tail probability, which also avoids any loss due to the use of concentration bounds.

###### Theorem 3.6 .

###### Proof.

### 3.4 Comparison: Densified DP-OPH versus DP-MH

We compare $N$, the “privacy discount factor”, in DP-OPH-fix, DP-OPH-re (Algorithm [4](#alg4)) and DP-MH (Algorithm [6](#alg6)). Smaller $N$ implies a smaller bit flipping probability which benefits the utility. In Figure [1](#S3.F1), we plot $N$ vs. $f$, for $D=1024$, $K=64$, and $\delta=10^{-6}$. A similar comparison also holds for other $D,K$ combinations. From the figure, we observe that $N$ in DP-OPH is typically smaller than that in DP-MH. Moreover, we also see that $N$ for DP-OPH-re is consistently smaller than that for DP-OPH-fix. This illustrates that re-randomization in the densification process is an important step to ensure better privacy.

Figure: Figure 1: Comparison of the privacy discount factor $N$ for densified DP-OPH and DP-MH, against the number of non-zero elements in the data vector $f$. $D=1024,K=64,\delta=10^{-6}$.
Refer to caption: x1.png

We further compare the Jaccard estimation accuracy. For the two densified DP-OPH variants, DP-OPH-fix and DP-OPH-re, and the DP MinHash (DP-MH) methods, each full-precision (and unprivatized) hash value of $h(\bm{u})$ and $h(\bm{v})$ has collision probability equal to $P(h(\bm{u})=h(\bm{v}))=J(\bm{u},\bm{v})$. Let $h^{(b)}(\bm{u})$ denote the $b$-bit hash values. Since we assume the lowest $b$ bits are uniformly assigned, we have $P(h^{(b)}(\bm{u})=h^{(b)}(\bm{v}))=J+(1-J)\frac{1}{B}$. Denote $p=\frac{\exp(\epsilon/N)}{\exp(\epsilon/N)+2^{b}-1}$. By simple probability calculation (Aumüller et al., ), the privatized $b$-bit hash values has collision probability

$$ $\displaystyle P(\tilde{h}(\bm{u})=\tilde{h}(\bm{v}))$ $\displaystyle=P(\tilde{h}(\bm{u})=\tilde{h}(\bm{v})|h^{(b)}(\bm{u})=h^{(b)}( \bm{v}))P(h^{(b)}(\bm{u})=h^{(b)}(\bm{v}))$ $\displaystyle\hskip 144.54pt+P(\tilde{h}(\bm{u})=\tilde{h}(\bm{v})|h^{(b)}(\bm {u})\neq h^{(b)}(\bm{v}))P(h^{(b)}(\bm{u})\neq h^{(b)}(\bm{v}))$ $\displaystyle=\left[p^{2}+\frac{(1-p)^{2}}{2^{b}-1}\right]\left(\frac{1}{2^{b} }+\frac{2^{b}-1}{2^{b}}J\right)+\left[\frac{2p(1-p)}{2^{b}-1}+\frac{2^{b}-2}{( 2^{b}-1)^{2}}(1-p)^{2}\right]\left(\frac{2^{b}-1}{2^{b}}-\frac{2^{b}-1}{2^{b}} J\right),$ $$

which implies $J=\frac{(2^{b}-1)(2^{b}P(\tilde{h}(u)=\tilde{h}(v))-1)}{(2^{b}p-1)^{2}}$. Therefore, let $\hat{J}=\frac{1}{K}\sum_{k=1}^{K}\mathbbm{1}\{\tilde{h}_{k}(u)=\tilde{h}_{k}(v)\}$, then an unbiased estimator of $J$ is

$$ $\displaystyle\hat{J}_{unbias}=\frac{(2^{b}-1)(2^{b}\hat{J}-1)}{(2^{b}p-1)^{2}}.$ (8) $$

To compare the mean squared error (MSE), we simulate two data vectors with $D=1024,K=64$, and $J=1/3$. In Figure [2](#S3.F2), we vary $f$, the number of non-zeros per data vector, and report the empirical MSE of the unbiased estimator ([8](#S3.E8)) for DP-OPH-fix, DP-OPH-re, and DP-MH, respectively. As we can see, the comparison is consistent with the comparison of $N$ in Figure [1](#S3.F1), that the proposed DP-OPH-re has the smallest MSE among the three competitors. This again justifies the advantage of DP-OPH-re. with re-randomized densification.

Figure: Figure 2: Empirical MSE comparison of the unbiased Jaccard estimator ([8](#S3.E8)) from DP-OPH-fix, DP-OPH-re and DP-MH. $D=1024,K=64,\delta=10^{-6}$.
Refer to caption: x4.png

## 4 Experiments

We conduct retrieval experiments to evaluate the proposed DP hashing methods on two public datasets: the MNIST (LeCun, ) hand-written digit dataset and the Webspam (Chang and Lin, ) dataset. Both datasets are binarized by setting the non-zero entries to 1. We use the train set as the database for retrieval candidates, and the test set as queries. For each query point, we set the ground truth (“gold-standard” ) neighbors as the top 50 data points in the database with the highest Jaccard similarity to the query. To search with DP-OPH and DP-MH, we generate the private hash values and estimate the Jaccard similarity between the query and the data points using the collision estimator in the same form as ([2](#S2.E2)). Then, we retrieve the data points with the highest estimated Jaccard similarity to the query. The evaluation metrics are precision and recall, defined as

$$ $\displaystyle\text{precision}@R=\frac{\text{\# of TPs in}\ R\ \text{retrieved points}}{R},\quad\text{recall}@R=\frac{\text{\# of TPs in}\ R\ \text{retrieved points}}{\text{\# of gold-standard neighbors}}.$ $$

For densified DP-OPH (Algorithm [4](#alg4)) and DP-MH (Algorithm [6](#alg6)), we ensure the lower bound $f$ on the number of non-zero elements by filtering the data points with at least $f$ non-zeros. For MNIST, we set $f=50$, which covers $99.9\%$ of the total sample points. For Webspam, we test $f=500$, which includes $90\%$ of the data points. We average the precision and recall metrics over all the query points. The reported results are averaged over 5 independent runs.

Figure: Figure 3: Precision@10 results on MNIST for DP-OPH variants and DP-MH, with different $K$. $\delta=10^{-6}$. First row: $b=1$. Second row: $b=2$.
Refer to caption: x7.png

Figure: Figure 4: Recall@500 results on MNIST for DP-OPH variants and DP-MH, with different $K$. $\delta=10^{-6}$. First row: $b=1$. Second row: $b=2$.
Refer to caption: x13.png

Results. In Figure [3](#S4.F3) and Figure [4](#S4.F4), we plot the precision and recall respectively on MNIST for 1-bit and 2-bit DP hashing methods. We see that:

- •
Consistent with Figure [1](#S3.F1), DP-OPH-re performs considerably better than DP-MH and DP-OPH-fix, for all $\epsilon$ levels.
- •
DP-OPH-rand achieves impressive search accuracy with small $\epsilon$ (e.g., $\epsilon<5$), but stops improving with $\epsilon$ afterward (due to the random bits for the empty bins), which demonstrates the trade-off discussed in Section [3.1](#S3.SS1). When $\epsilon$ gets larger (e.g., $\epsilon>15$), DP-OPH-rand is outperformed by DP-OPH-re.
- •
Increasing $b$ is relatively more beneficial for DP-OPH-rand as it can achieve higher search accuracy with small $\epsilon$. Also, larger $\epsilon$ is required for DP-OPH-re to bypass DP-OPH-rand.

The results on Webspam with $b=2$ are presented in Figure [5](#S4.F5). Again, DP-OPH-re achieves better performance than DP-MH and DP-OPH-fix for all $\epsilon$, especially when $\epsilon<20$. DP-OPH-rand performs the best with $\epsilon<10$. Yet, it may underperform when $\epsilon$ increases.

Figure: Figure 5: Precision@10 and recall@500 results on Webspam for 2-bit hash values. $\delta=10^{-6}$.
Refer to caption: x19.png

In summary, our experiments show that, the proposed DP-OPH-re with re-randomized densification is better than DP-MH and DP-OPH-fix with fixed densification for all $\epsilon$. When $\epsilon$ is small (e.g., $\epsilon<10$), the DP-OPH-rand variant might achieve the best practical utility. When $\epsilon$ is allowed to be larger, DP-OPH-re should be the top choice for hashing the Jaccard similarity.

## 5 Extension: Differentially Private Bin-wise Consistent Weighted Sampling (DP-BCWS) for Weighted Jaccard Similarity

Figure: Algorithm 7 Consistent Weighted Sampling (CWS)

In our main paper, we focused on DP hashing algorithms for the binary Jaccard similarity. Indeed, our algorithm can also be extended to hashing the weighted Jaccard similarity: (recall the definition)

$$ $\displaystyle J_{w}({\bm{u},\bm{v}})=\frac{\sum_{i=1}^{D}\min\{u_{i},v_{i}\}}{ \sum_{i=1}^{D}\max\{u_{i},v_{i}\}},$ (9) $$

for two non-negative data vectors $\bm{u},\bm{v}\in\mathbb{R}_{+}$. The standard hashing algorithm for ([9](#S5.E9)) is called Consistent Weighted Sampling (CWS) as summarized in Algorithm [7](#alg7) (Ioffe, ; Manasse et al., ; Li et al., , ). To generate one hash value, we need three length-$D$ random vectors $\bm{r}\sim Gamma(2,1)$, $\bm{c}\sim Gamma(2,1)$ and $\bm{\beta}\sim Uniform(0,1)$. We denote Algorithm [7](#alg7) as a function $CWS(\bm{u};\bm{r},\bm{c},\bm{\beta})$. Li et al. () proposed bin-wise CWS (BCWS) which exploits the same idea of binning as in OPH. The binning and densification procedure of BCWS is exactly the same as OPH (Algorithm [2](#alg2) and Algorithm [3](#alg3)), except that every time we apply CWS, instead of MinHash, to the data in the bins to generate hash values. Note that in CWS, the output contains two values: $i^{*}$ is a location index similar to the output of OPH, and $t^{*}$ is a real-value scalar. Prior studies (e.g., Li et al. ()) showed that the second element has minimal impact on the estimation accuracy in most practical cases (i.e., only counting the collision of the first element suffices). Therefore, in our study, we also only keep the first integer element as the hash output for subsequent learning tasks.

For weighted data vectors, we follow the prior DP literature on weighted sets (e.g., Xu et al. (); Smith et al. (); Dickens et al. (); Zhao et al. (); Li and Li ()) and define the neighboring data vectors as those who differ in one element. To privatize BCWS, there are also three possible ways depending on the densification option. Since the DP algorithm design for densified BCWS requires rigorous and non-trivial computations which might be an independent study, here we empirically test the ($b$-bit) DP-BCWS method with random bits for empty bins. The details are provided in Algorithm [8](#alg8). In general, we first randomly split the data entries into $K$ equal length bins, and apply CWS to the data $\bm{u}_{\mathcal{B}_{k}}$ in each non-empty bin $\mathcal{B}_{k}$ using the random numbers ($\bm{r}_{\mathcal{B}_{k}},\bm{c}_{\mathcal{B}_{k}},\bm{\beta}_{\mathcal{B}_{k}}$) to generated $K$ hash values (possibly including empty bins). After each hash is transformed into the $b$-bit representation, we uniformly randomly assign a hash value in $\{0,...,2^{b}-1\}$ to every empty bin.

Figure: Algorithm 8 Differential Private Bin-wise Consistent Weighted Sampling (DP-BCWS)

Using the same proof arguments as Theorem [3.5](#S3.Thmtheorem5), we have the following guarantee.

###### Theorem 5.1 .

Algorithm [8](#alg8) satisfies $\epsilon$-DP.

Empirical evaluation. In Figure [6](#S5.F6), we train an $l_{2}$-regularized logistic regression on the DailySports dataset(^2^22[https://archive.ics.uci.edu/ml/datasets/daily+and+sports+activities](https://archive.ics.uci.edu/ml/datasets/daily+and+sports+activities)). and report the test accuracy with various $b$ and $K$ values. The $l_{2}$ regularization parameter $\lambda$ is tuned over a fine grid from $10^{-4}$ to $10$. Similar to the results in the previous section, the performance of DP-BCWS becomes stable as long as $\epsilon>5$. Note that, linear logistic regression only gives $\approx 75\%$ accuracy on original DailySports dataset (without DP). With DP-BCWS, the accuracy can reach $\approx 98\%$ with $K=1024$ and $\epsilon=5$.

Figure: Figure 6: Test classification accuracy of DP-BCWS on DailySports dataset (Asuncion and Newman, ) with $l_{2}$-regularized logistic regression.
Refer to caption: x25.png

In Figure [7](#S5.F7), we train a neural network with two hidden layers of size 256 and 128 respectively on the MNIST dataset (LeCun, ). We use the ReLU activation function and the standard cross-entropy loss. We see that, in a reasonable privacy regime (e.g., $\epsilon<10$), DP-BCWS is able to achieve $\approx 95\%$ test accuracy with proper $K$ and $b$ combinations (one can choose the values depending on practical scenarios and needs). For example, with $b=4$ and $K=128$, DP-BCWS achieves $\approx 97\%$ accuracy at $\epsilon=8$.

Figure: Figure 7: Test classification accuracy of DP-BCWS on MNIST dataset (LeCun, ) with 2-hidden layer neural network.
Refer to caption: x28.png

In a very recent survey paper (Ponomareva et al., , page 33), the authors provided their three-tier taxonomy of the strength of privacy protection, according to the $\epsilon$ values: $\epsilon\leq 1$ for “Tier 1: Strong formal privacy guarantees”, $\epsilon\leq 10$ for “Tier 2: Realistic privacy guarantees”, and $\epsilon>10$ for “Tier 3: Weak to no formal privacy guarantees”. Hence, our proposed algorithms are able to achieve good utility while providing strong realistic privacy protections.

###### Theorem 5.1 .

## 6 Conclusion

Industrial applications often encounter massive high-dimensional binary (0/1) data. The method of “one permutation hashing” (OPH), which improves the standard minwise hashing (MinHash), is a common hashing technique for efficiently computing the binary Jaccard similarity. For example, it is a standard practice to use MinHash or OPH for building hash tables to enable sublinear-time approximate near neighbor (ANN) search. In this paper, we propose differentially private one permutation hashing (DP-OPH). We develop three variants of DP-OPH depending on the densification procedure of OPH, and provide detailed derivation and privacy analysis of our algorithms. We analytically demonstrate the advantage of the proposed DP-OPH over DP-MH (DP for MinHash). Experiments on retrieval and classification tasks justify the effectiveness of the proposed DP-OPH, and provide guidance on the appropriate choice of the DP-OPH variant in different scenarios.

Our idea is extended to non-binary data and the weighted Jaccard similarity. We propose the DP-BCWS algorithm for non-binary data and empirically demonstrate its superb performance in utility for classification tasks with logistic regression models as well as neural nets. For example, we observe DP-BCWS achieves a good utility at $\epsilon<4\sim 8$. Given the high efficiency of the OPH method and its strong performance in privacy protection, we expect DP-OPH as well as DP-BCWS will be a useful large-scale hashing tool with privacy protection.

In a recent work, Li and Li () utilized (smoothed) local sensitivity to develop DP and iDP (individual DP) algorithms for the family of random projections (RP) and sign random projections (SignRP), with a series of algorithms including DP-OPORP, DP-SignOPORP, iDP-SignRP. Here “OPORP” (Li and Li, ) stands for “one permutation + one random projection” which is an improved variant of the count-sketch. For our future work, we will seek novel new constructions to obtain the analogous notion of local sensitivity to improve DP-OPH.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: * I think the standard setup of $\delta$ in DP theory/practice is to make it "cryptographically" small (smaller than inverse data set size, at least). It seems you ran experiments within the regime that $\delta \approx 10^{-6}$. What happens if you scale it further?
* Can you comment on your definition of "adjacent inputs" in defining privacy? In other words, how to interpret the implication of protecting a single bit in the feature vector?
* Could you clarify the interplay between $eps,b,K$ and the variance of your hashing scheme? In particular, I think the quality of the DP-OPH would degrade significantly once $b$ goes moderately large. On the other hand, setting a smaller $b$ makes the hashing itself less accurate. Can you compare your results with non-private algorithms? I apologize if these are written in the text (and would appreciate it if you can provide a pointer)
* What is your definition of "precision" in the experiment? Also, why not include a non-private algorithm for comparison?
soundness: 2
strengths: * Designing differentially private sketching/hashing schemes is a well-motived and important problem in differential privacy and massive data processing. This paper studies one of the most fundamental problems in this direction.
* The algorithms are clearly explained and easy to follow.
summary: This paper studies the differentially private hashing and sketching, for the task of computing Jaccard similarity index. It starts by reviewing several classical, non-private hashing schemes for this task, including MinHash and One Permutation Hashing (OPH) from prior works.

It then designed new privatized versions of these hash schemes, including DP-OPH-re, DP-OPH-fix, DP-OPH-rand, etc. The paper proved that these algorithms satisfy either pure-DP or approximate-DP, and conducted a number of experiments comparing all these methods. The general conclusion seems to be that DP-OPH-re is the most effective approach.
weaknesses: * The main privatization technique used in this paper seems to be the randomized response mechanism. It is hard to believe that this can be effective.
* To privatize the OPH-re/fix schemes, this paper proposes to consider the relaxation of approximate privacy to avoid paying a huge price on "epsilon". I have some concerns on the choice of $\delta$ here.
* The algorithms proposed in this paper try to protect the privacy of a single bit in a binary feature vector $u\in \{0, 1\}^D$. In a more realistic setting, though, I would imagine $u$ being the feature vector of a client, and it must be protected as a whole ---- I understand this sounds very hard. But it needs to be justified to choose $u_i$
* The theoretical discussion in the introduction is almost impossible to follow -- I would suggest emphasizing the asymptotic behavior and deferring equations to the appendix when possible.
* Some issues with the experiments need to be clarified (see below)

---

confidence: 2
contribution: 2
initial_rating: 3
presentation: 1
questions: The description of `OPH-re` is confusing to me. I read it several times and I still don't understand what the method is doing. In particular, I did not get what $SortedIndex$ and $MapToIndex$ mean and what $\pi^{(k)} : \pi(\mathcal{B}_{k'}) \mapsto MapToIndex$ means. It might help to work through some example to explain the algorithm.

In `DP-OPH-rand` (Algorithm 5), is there some typo on Line 4 in that should the $\epsilon$ be $\epsilon'$ ?

Is it possible to simplify Theorem 3.6 in some way to highlight the main take-away as opposed to have detailed calculations within the theorem statement that take half a page to even state?
soundness: 2
strengths: The paper introduces DP variants of `MinHash` sketching technique and provides a detailed analysis.
summary: This paper studies the problem of similarity search based on the measure of Jaccard similarity, under the setting of differential privacy.

Jaccard similarity between two "documents" are defined as follows:
* Documents are represented as binary vectors $\{0, 1\}^D$, e.g. these can be the indicator vectors of the bag of words.
* $J(\mathbf{u}, \mathbf{v}) := \frac{\sum_{i=1}^D u\_i v\_i}{\sum_{i=1}^D \max\\{u\_i, v\_i\\}}$ measures the ratio of the size of the intersection and the union of the two documents.

Given a collection of $n$ documents, $\mathbf{u}^{(1)}, \ldots, \mathbf{u}^{(n)}$, and a query document $\mathbf{v}$, we would like to recover the top documents $\mathbf{u}^{(i)}$ that have highest value of $J(\mathbf{u}^{(i)}, \mathbf{v})$.

The `MinHash` is a celebrated techique to construct a sketch of the given documents in order to efficiently estimate the Jaccard similarity against any given query document.

The goal in the paper is to construct differentially private versions of this sketching technique, where the notion of differential privacy holds against adding / removing one word from any given document.

The paper considers a $b$-bit version of `MinHash`, as well as methods involving "re-randomization" (there were introduced in prior work). These sketches are made differentially private by applying the randomized response mechanism.

The privacy analysis is performed that gives tighter bounds than basic composition, and some experimental results are provided on some practical datasets (the Leukemia gene expression dataset, and Webspam dataset), showing that the DP versions of the `MinHash` variants with re-randomization achieve better precision.
weaknesses: I felt the presentation in the paper is quite poor. I had to re-read several parts of the paper, and I still don't fully understand many of the details. (See some of my questions below.)

Presentation aspects aside, I am also confused about the motivation or potential application of these methods.
In the experiments, the precision values are reported, by which I think means that the DP hashes to recover the documents with most similarity. The evaluation of precision itself is not a private operation though, as it requires comparing against the true Jaccard similarity.
I understand that this is done just to demonstrate the utility of the approach, so it is okay that computing precision is non-private.
But how do we expect to use these DP methods in any case? Sure, we can compute the approximate Jaccard similarity of a query against documents in a database, but then if we actually retrieve the most similar document and look at its contents then it is not private anymore.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: (See Weaknesses above.)
soundness: 2
strengths: Private sketching is a natural problem, and the genomics example is well-motivated. Studying private versions of oph and minhash is also a natural approach, so even somewhat independently of whether they produce good algorithms or not, it's useful to have a study written down.
summary: This paper introduces and analyzes a few algorithms for differentially private binary sketches. The proposed setting features binary databases of size $D$, and the goal is to compute Jaccard similarity between databases privately using sketches of size $\ll D$. The paper's proposed algorithms are primarily variants of one permutation hashing. One variant does not use densification (rand), one uses fixed densification (fix), and one uses re-randomized densification (re). The paper also introduces a private baseline based on minhash and provides both formal and empirical utility results demonstrating that, roughly, re dominates fix dominates minhash. Finally, empirical results show that rand in turn dominates re unless $\epsilon \approx 10$ or larger.
weaknesses: I think there is a potentially decent but smaller version of the paper contained in the current submission. Some specific comments:

1) I found the empirical results in Figures 3 and 4 surprising. After all the effort to set up and analyze fix and re, the simpler (and pure DP) rand clearly obtains the highest precision outside of extremely large values $\epsilon > 10$. Even when $\epsilon$ is large, the gap between rand and re is small. Given the effort the authors have expended on fix and re, I think it is valid to include them *somewhere* in the paper, but I suggest that they make more sense discussed in the Appendix as natural solutions that turn out to be less useful. Perhaps the authors think it's valuable to include fix and re because they have formal utility results that can be compared to minhash? If so, I understand this argument, but I still think the gap in performance is large enough that most or all of the focus should be on rand.

2) The lower bound $f$ required for fix and re is another disadvantage relative to rand. Also, how does "filtering" for $f$ (Line 418) affect the privacy guarantee -- what does the algorithm do if given a data points that fails $f$?

3) The introduction highlights that, unlike some past work, this approach does not assume private hash function randomness. I get that this is more flexible, but I don't understand why it's so meaningful. These algorithms still require that the bit flip randomness is kept private -- why is the hash function assumption so different?

4) A utility analysis for rand would help complete the paper structure suggested above. Have the authors attempted this, or do they have reason to believe it's hard?

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: [Q1] The authors could consider to provide more discussions, including but not limited to the limitation and potential applications of the proposed schemes.

[Q2] This paper could benefit from language improvements.
soundness: 2
strengths: [S1] The motivation of this paper is clear, which is to protect the privacy of one permutation hashing (OPH) to meet differential private definition.

[S2] This paper is easy to read with necessary introduction of background and preliminaries.

[S3] This paper provides extensive theoretical analysis with formalized proof. This paper also provides fair experiments with clear results.
summary: This paper explores differentially private one permutation hashing (DP-OPH) methods and develop three variants based on the densification procedure of OPH.  This paper conduct privacy and utility analyses for these algorithms and demonstrate that DP-OPH outperforms the DP MinHash alternative previously suggested for hashing Jaccard similarity across various privacy settings.
weaknesses: [W1] The technical depth and contribution are limited. This paper introduces randomized response technique to randomize output, which is a common idea that has been studied in various previous works. Although this combination successfully outputs a differential private OPH, as claimed by the authors, the technical challenge and depth are not clear shown to highlight contribution. 

[W2] The assumption “each data vector contains at least f non-zeros” in Sec 3.2 remains to be discussed more seriously. The number of non-zeros should obey some probability distribution. Although the probability might be small enough to be negligible if the f is set properly, one should quantificationally capture the probability or provide necessary reference to make the assumption more rigorous. In addition, to lead following contribution, the authors claim K is usually around hundreds in Sec 3.2, which also should be provided with a reference to support the claim.

[W3] The language level is sub-standard, which requires further polishment. Some conceptual information is missing. For example, the definition and procedure of SortedIndex and MapToIndex in Alg.3 are not introduced, making readers confused about the procedure of Alg.3.

Meta-review: This paper studies an important problem in privacy-preserving hashing and sketching.
The reviewers are in agreement that the paper does not meet the bar for publication at ICLR, and that the presentation would need to be significantly improved before the paper is ready for publication.
We encourage the author(s) to incorporate the feedback from the reviewers regarding the presentation and experimental evaluation before re-submitting this work.

Decision: Reject