# Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling

arXiv: https://arxiv.org/abs/2306.07674 · HTML: https://mlsanity.com/paper/2306.07674/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 110 references that are in the map.
- First posted on arXiv 13 Jun 2023.

## Builds on (most cited first, 24 of 24)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Federated Learning with Differential Privacy: Algorithms and Performance Analysis](https://mlsanity.com/paper/1911.00222/) (2019)
- [Learning Fine-grained Image Similarity with Deep Ranking](https://mlsanity.com/paper/1404.4661/) (2014)
- [cpSGD: Communication-efficient and differentially-private distributed SGD](https://mlsanity.com/paper/1805.10559/) (2018)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Distributed Hierarchical GPU Parameter Server for Massive Scale Deep Learning Ads Systems](https://mlsanity.com/paper/2003.05622/) (2020)
- [Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs](https://mlsanity.com/paper/1602.04844/) (2016)
- [OPORP: One Permutation + One Random Projection](https://mlsanity.com/paper/2302.03505/) (2023)
- [In Defense of MinHash Over SimHash](https://mlsanity.com/paper/1407.4416/) (2014)
- [Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring](https://mlsanity.com/paper/2004.05345/) (2020)
- [Differentially Private Linear Sketches: Efficient Implementations and Applications](https://mlsanity.com/paper/2205.09873/) (2022)
- [Coding for Random Projections](https://mlsanity.com/paper/1308.2218/) (2013)
- [Optimal Densification for Fast and Accurate Minwise Hashing](https://mlsanity.com/paper/1703.04664/) (2017)
- [Practical Hash Functions for Similarity Estimation and Dimensionality Reduction](https://mlsanity.com/paper/1711.08797/) (2017)
- [Improved Densification of One Permutation Hashing](https://mlsanity.com/paper/1406.4784/) (2014)
- [A Memory-Efficient Sketch Method for Estimating High Similarities in Streaming Sets](https://mlsanity.com/paper/1905.08977/) (2019)
- [Improved Differentially Private Euclidean Distance Approximation](https://mlsanity.com/paper/2203.11561/) (2022)
- [Differential Privacy with Random Projections and Sign Random Projections](https://mlsanity.com/paper/2306.01751/) (2023)
- [Parallel Index-Based Structural Graph Clustering and Its Approximation](https://mlsanity.com/paper/2012.11188/) (2020)
- [BagMinHash - Minwise Hashing Algorithm for Weighted Sets](https://mlsanity.com/paper/1802.03914/) (2018)
- [Differentially Private Sketches for Jaccard Similarity Estimation](https://mlsanity.com/paper/2008.08134/) (2020)
- [C-OPH: Improving the Accuracy of One Permutation Hashing (OPH) with Circulant Permutations](https://mlsanity.com/paper/2111.09544/) (2021)
- [Order-Invariant Cardinality Estimators Are Differentially Private](https://mlsanity.com/paper/2203.15400/) (2022)
- [Building K-Anonymous User Cohorts with Consecutive Consistent Weighted Sampling (CCWS)](https://mlsanity.com/paper/2304.13677/) (2023)

## Built on by (most cited first, 3 of 3)

- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [Provable Differentially Private Computation of the Cross-Attention Mechanism](https://mlsanity.com/paper/2407.14717/) (2024)
- [Pb-Hash: Partitioned b-bit Hashing](https://mlsanity.com/paper/2306.15944/) (2023)

## Abstract (arXiv)

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 random permutations. In comparison, the method of one permutation hashing (OPH), is an efficient alternative of MinHash which splits the data vectors into K bins and generates hash values within each bin. OPH is substantially more efficient and also more convenient to use. 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 demonstrate that DP-BCWS is able to achieve excellent utility at around ε = 5~ 10, where ε is the standard parameter in the language of (ε, δ)-DP.