# MaxSketch: Robust Distinct Counting in Streams via Random Projections

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 34 references that are in the map.
- First posted on arXiv 15 May 2026.

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

- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Momentum Contrast for Unsupervised Visual Representation Learning](https://mlsanity.com/paper/1911.05722/) (2019)
- [Bootstrap your own latent: A new approach to self-supervised Learning](https://mlsanity.com/paper/2006.07733/) (2020)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Prevalence of Neural Collapse during the terminal phase of deep learning training](https://mlsanity.com/paper/2008.08186/) (2020)
- [A Geometric Analysis of Neural Collapse with Unconstrained Features](https://mlsanity.com/paper/2105.02375/) (2021)
- [Neural Collapse Under MSE Loss: Proximity to and Dynamics on the Central Path](https://mlsanity.com/paper/2106.02073/) (2021)
- [On the Optimization Landscape of Neural Collapse under MSE Loss: Global Optimality with Unconstrained Features](https://mlsanity.com/paper/2203.01238/) (2022)
- [On the Limitations of Representing Functions on Sets](https://mlsanity.com/paper/1901.09006/) (2019)
- [CNN-based Density Estimation and Crowd Counting: A Survey](https://mlsanity.com/paper/2003.12783/) (2020)
- [On Deep Set Learning and the Choice of Aggregations](https://mlsanity.com/paper/1903.07348/) (2019)
- [Learning Aggregation Functions](https://mlsanity.com/paper/2012.08482/) (2020)
- [Generalised f-Mean Aggregation for Graph Neural Networks](https://mlsanity.com/paper/2306.13826/) (2023)
- [Distinct Sampling on Streaming Data with Near-Duplicates](https://mlsanity.com/paper/1810.12388/) (2018)

## Abstract (arXiv)

Estimating the number of distinct elements in a data stream is well understood when repeated elements are identical. In modern settings, however, observations are high-dimensional and noisy, so repeated instances of the same object are only approximately similar -- for example, different images of the same individual may vary significantly at the pixel level. Classical sketches such as HyperLogLog rely on consistent hash values for identical elements and break down in this regime. Recent work on robust distinct counting in general metric spaces achieves widetildeTheta(√n) memory, which is tight in the worst case. We show that substantially improved memory guarantees are possible under geometric structure common in learned representations. We introduce MaxSketch, a simple max-linear sketch built from random Gaussian projections, and prove that it succeeds in estimating the number of distinct latent objects. Concretely, we show that under this assumption m = widetildeO (log n / varepsilon2) random projections (and hence widetildeO (log n/varepsilon2) memory) suffice to recover the true distinct count within a (1+varepsilon) factor. Experiments on image streams confirm that MaxSketch accurately estimates distinct counts and generalizes beyond the training regime. Our results bridge classical streaming algorithms and modern representation learning, showing how geometric structure can fundamentally reduce the complexity of distinct counting.