# Pb-Hash: Partitioned b-bit Hashing

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 65 references that are in the map.
- First posted on arXiv 28 Jun 2023.

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

- [Learning Fine-grained Image Similarity with Deep Ranking](https://mlsanity.com/paper/1404.4661/) (2014)
- [Compositional Embeddings Using Complementary Partitions for Memory-Efficient Recommendation Systems](https://mlsanity.com/paper/1909.02107/) (2019)
- [Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs](https://mlsanity.com/paper/1602.04844/) (2016)
- [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)
- [A Memory-Efficient Sketch Method for Estimating High Similarities in Streaming Sets](https://mlsanity.com/paper/1905.08977/) (2019)
- [BagMinHash - Minwise Hashing Algorithm for Weighted Sets](https://mlsanity.com/paper/1802.03914/) (2018)
- [Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling](https://mlsanity.com/paper/2306.07674/) (2023)
- [Building K-Anonymous User Cohorts with Consecutive Consistent Weighted Sampling (CCWS)](https://mlsanity.com/paper/2304.13677/) (2023)

## Abstract (arXiv)

Many hashing algorithms including minwise hashing (MinHash), one permutation hashing (OPH), and consistent weighted sampling (CWS) generate integers of B bits. With k hashes for each data vector, the storage would be B× k bits; and when used for large-scale learning, the model size would be 2B× k, which can be expensive. A standard strategy is to use only the lowest b bits out of the B bits and somewhat increase k, the number of hashes. In this study, we propose to re-use the hashes by partitioning the B bits into m chunks, e.g., b× m =B. Correspondingly, the model size becomes m× 2b × k, which can be substantially smaller than the original 2B× k. Our theoretical analysis reveals that by partitioning the hash values into m chunks, the accuracy would drop. In other words, using m chunks of B/m bits would not be as accurate as directly using B bits. This is due to the correlation from re-using the same hash. On the other hand, our analysis also shows that the accuracy would not drop much for (e.g.,) m=2~ 4. In some regions, Pb-Hash still works well even for m much larger than 4. We expect Pb-Hash would be a good addition to the family of hashing methods/applications and benefit industrial practitioners. We verify the effectiveness of Pb-Hash in machine learning tasks, for linear SVM models as well as deep learning models. Since the hashed data are essentially categorical (ID) features, we follow the standard practice of using embedding tables for each hash. With Pb-Hash, we need to design an effective strategy to combine m embeddings. Our study provides an empirical evaluation on four pooling schemes: concatenation, max pooling, mean pooling, and product pooling. There is no definite answer which pooling would be always better and we leave that for future study.