Efficient Binary Embedding of Categorical Data using BinSketch
This work addresses efficient processing of high-dimensional categorical data, which is incremental as it builds on sketching techniques for sparse datasets.
The authors tackled the problem of dimensionality reduction for categorical data by proposing Cabin for binary sketching and Cham for distance estimation, achieving significantly faster and more accurate performance on tasks like RMSE and clustering compared to full datasets and other methods, with experiments on datasets up to over a million dimensions.
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.