# Efficient Sketching Algorithm for Sparse Binary Data

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Oct 2019.

## Built on by (most cited first, 4 of 4)

- [Dimensionality Reduction for Categorical Data](https://mlsanity.com/paper/2112.00362/) (2021)
- [Learning Scalable Structural Representations for Link Prediction with Bloom Signatures](https://mlsanity.com/paper/2312.16784/) (2023)
- [QUINT: Node embedding using network hashing](https://mlsanity.com/paper/2109.04206/) (2021)
- [Efficient Binary Embedding of Categorical Data using BinSketch](https://mlsanity.com/paper/2111.07163/) (2021)

## Abstract (arXiv)

Recent advancement of the WWW, IOT, social network, e-commerce, etc. have generated a large volume of data. These datasets are mostly represented by high dimensional and sparse datasets. Many fundamental subroutines of common data analytic tasks such as clustering, classification, ranking, nearest neighbour search, etc. scale poorly with the dimension of the dataset. In this work, we address this problem and propose a sketching (alternatively, dimensionality reduction) algorithm -- binsketch (Binary Data Sketch) -- for sparse binary datasets. binsketch preserves the binary version of the dataset after sketching and maintains estimates for multiple similarity measures such as Jaccard, Cosine, Inner-Product similarities, and Hamming distance, on the same sketch. We present a theoretical analysis of our algorithm and complement it with extensive experimentation on several real-world datasets. We compare the performance of our algorithm with the state-of-the-art algorithms on the task of mean-square-error and ranking. Our proposed algorithm offers a comparable accuracy while suggesting a significant speedup in the dimensionality reduction time, with respect to the other candidate algorithms. Our proposal is simple, easy to implement, and therefore can be adopted in practice.