Efficient binary embedding of categorical data using BinSketch

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-pair similarity, and clustering when compared to working with the full dataset and other dimensionality reduction techniques.

Automated summary

This paper presents a dimensionality reduction algorithm for categorical datasets, which constructs low-dimensional binary sketches from high-dimensional categorical vectors and approximates the Hamming distance between any two original vectors. The approach is particularly useful for sparse datasets and has been rigorously analyzed and experimentally validated.