# Efficient Binary Embedding of Categorical Data using BinSketch

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 44 references that are in the map.
- First posted on arXiv 13 Nov 2021.

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

- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [Efficient Sketching Algorithm for Sparse Binary Data](https://mlsanity.com/paper/1910.04658/) (2019)
- [Efficient Compression Technique for Sparse Sets](https://mlsanity.com/paper/1708.04799/) (2017)

## Abstract (arXiv)

In this work, we present a dimensionality reduction algorithm, aka. sketching, for categorical datasets. Our proposed sketching algorithm Cabin constructs low-dimensional binary sketches from high-dimensional categorical vectors, and our distance estimation algorithm Cham computes a close approximation of the Hamming distance between any two original vectors only from their sketches. The minimum dimension of the sketches required by Cham to ensure a good estimation theoretically depends only on the sparsity of the data points - making it useful for many real-life scenarios involving sparse datasets. We present a rigorous theoretical analysis of our approach and supplement it with extensive experiments on several high-dimensional real-world data sets, including one with over a million dimensions. We show that the Cabin and Cham duo is a significantly fast and accurate approach for tasks such as RMSE, all-pairs similarity, and clustering when compared to working with the full dataset and other dimensionality reduction techniques.