Pb-Hash: Partitioned b-bit Hashing

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 BXk bits; and when used for large-scale learning, the model size would be 2B X 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 X m =B. Correspondingly, the model size becomes m X 2b X k, which can be substantially smaller than 2BX k.