Densification Strategies for One Permutation Hashing

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 226 papers57 conceptsfrozen 2026-10-04

In large-scale machine learning, comparing the similarity of two massive data vectors is a fundamental but expensive operation. Whether for duplicate detection, recommendation systems, or nearest-neighbor search, we often rely on the Jaccard similarity—the ratio of the intersection of two sets to their union.

The gold standard for estimating this similarity is Minwise Hashing (MinHash). However, traditional MinHash requires hundreds of independent permutations of the feature space to produce a single signature, creating a massive computational bottleneck. Researchers like Ping Li and Anshumali Shrivastava have pioneered a more efficient alternative called One Permutation Hashing (OPH). While OPH is significantly faster, it introduces a unique challenge: the "empty bin" problem in sparse data.

The Efficiency of Binning

Traditional MinHash works by applying $k$ random permutations to a feature set and storing the minimum index for each. If you want a signature of length $k=200$, you must perform 200 permutations. One Permutation Hashing for Efficient Search and Learning by Ping Li et al. changes this by using a single permutation.

The intuition is simple: instead of permuting the whole space 200 times, we permute it once and partition the resulting space into 200 discrete "bins." We then look for the minimum value within each bin. This reduces the processing time from $O(dk)$ to $O(d+k)$, where $d$ is the number of non-zero features. As shown in b-Bit Minwise Hashing in Practice, this efficiency is critical for training high-accuracy classifiers on hundreds of gigabytes of data.

The Empty Bin Problem

The efficiency of OPH comes with a catch. In high-dimensional, sparse datasets—common in natural language processing or web search—a data vector might only have a few non-zero entries. When we partition the permuted space into many bins, many of those bins will inevitably be empty.

An empty bin provides no "minimum value," which breaks the signature. If we simply ignore these bins or fill them with zeros, we introduce artificial noise and lose the mathematical properties required to estimate Jaccard similarity accurately. As noted in GoldFinger: Fast & Approximate Jaccard for Efficient KNN Graph Constructions, high sparsity increases the impact of hash collisions, making the quality of similarity approximations highly sensitive to how these gaps are handled.

Densification: Filling the Gaps

To solve this, researchers developed densification strategies. The goal is to fill empty bins by "borrowing" values from non-empty bins in a way that is consistent across different data vectors.

In Optimal Densification for Fast and Accurate Minwise Hashing, Anshumali Shrivastava introduced a scheme that uses a 2-universal hash function to systematically reassign empty bins to non-empty ones. If bin $i$ is empty, the algorithm uses a hash function to look at bin $j$. If $j$ is also empty, it uses an "attempt counter" to jump to another bin until a value is found. This ensures that if two different sets both have an empty bin at the same position, they will look to the same non-empty bins to fill it, preserving the locality-sensitive properties of the hash.

Advanced Variations and Privacy

The evolution of densification has led to even more robust methods:

  • Circulant Permutations: Ping Li and Xiaoyun Li proposed C-OPH, which uses circulant shifts to fill empty bins. By shifting the values from non-empty bins, they create a dense signature that achieves lower estimation variance than previous methods while using minimal memory.
  • Privacy-Preserving Densification: When data is sensitive, the structure of which bins are empty could leak information. Differentially Private One Permutation Hashing explores re-randomizing the copied values during densification to maintain utility without compromising privacy.
  • Handling Long-Tailed Data: In scenarios where some categories are extremely rare, such as in Meta Cross-Modal Hashing, densification logic can be extended via meta-learning to "borrow" knowledge from common classes to better represent the sparse "tail" of the distribution.

By turning the "bug" of empty bins into a feature of structured reassignment, densification allows OPH to provide the best of both worlds: the theoretical rigor of MinHash with the practical speed required for modern, large-scale sparse data applications.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 22 papers
  2. Version 1 · 2026-10-04 · 26 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_empty_bin_problem_22e86c9a,
  title = {empty bin problem},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/empty-bin-problem/rdr_22e86c9a5aa94bee82f74c074cb6af7b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_densification_strategies_for_one_permuta_22e86c9a_v1,
  title = {Densification Strategies for One Permutation Hashing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/densification-strategies-for-one-permutation-hashing/rdr_22e86c9a5aa94bee82f74c074cb6af7b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}