📊 statistics

MaxSketch: Robust Distinct Counting in Streams via Random Projections

This paper introduces MaxSketch, a random projection-based algorithm that leverages geometric structure in learned representations to achieve near-optimal logarithmic memory complexity for robustly estimating distinct counts in noisy, high-dimensional data streams, overcoming the limitations of classical sketches and prior worst-case bounds.

Original authors: Nikos Tsikouras, Constantine Caramanis, Christos Tzamos

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nikos Tsikouras, Constantine Caramanis, Christos Tzamos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are standing at a busy intersection with a camera, trying to count how many unique people walk by.

In the old days of computer science, counting was easy if everyone wore a uniform ID badge. If "Alice" walked by, her badge said "Alice." If she walked by again, the badge still said "Alice." The computer just needed to check if it had seen that exact badge before. This is how classic counting tools work: they rely on exact matches.

But in the real world, people don't wear ID badges. They wear different clothes, stand in different lights, and hold different poses. If Alice walks by in a red coat and later in a blue jacket, a simple computer might think, "That's a new person!" and count her twice. This is the problem of noisy, high-dimensional data: the same object looks different every time you see it.

The Old Way vs. The New Problem

Previous attempts to solve this tried to group similar-looking things together (clustering). But this is like trying to count people by keeping a photo of every single person you've ever seen. If you see 10,000 people, you need to remember 10,000 photos. This takes up too much memory, especially if you are processing a massive stream of data in real-time.

Another approach tried to say, "If two photos are close enough, they are the same person." But mathematically, this turns out to be incredibly hard. In the worst-case scenario, you would need a huge amount of memory (proportional to the square root of the total number of people) to get an accurate count. That's like needing a library the size of a city just to count the crowd in a stadium.

The Solution: MaxSketch

The authors of this paper introduce a new method called MaxSketch. They realized that modern AI (specifically deep learning) already does a great job of organizing data. When you train an AI to recognize faces or objects, it naturally learns to put "Alice" in one tight cluster and "Bob" in another, far-away cluster. Even if Alice changes her coat, her "digital fingerprint" stays close to her original spot.

MaxSketch uses this natural clustering to count without needing to remember every single photo.

The Analogy: The "Wind Tunnel"

Imagine you have a giant wind tunnel with many fans blowing from different random directions.

The Setup: You have a stream of people (data points) walking through the tunnel.
The Test: For each fan direction, you ask: "Who is the person standing furthest in the direction of this wind?"
The Magic: If 100 photos of Alice walk through, she will be the "furthest" person for a specific fan direction only once. The other 99 times, she is still there, but she doesn't change the answer because she's already the maximum. The wind tunnel effectively ignores the repetition and only cares about the presence of the unique group.
The Count: By averaging the results of thousands of these random wind directions, the computer can estimate how many distinct "clusters" (unique people) are in the stream.

Why It Works

The paper proves that if the data is "well-behaved" (meaning the AI has successfully grouped similar things together and kept different things far apart), this method is incredibly efficient.

Memory: Instead of needing a library the size of a city, MaxSketch only needs a tiny notebook (logarithmic memory). It's like counting a crowd by taking a few quick snapshots of the wind direction rather than photographing every single person.
Accuracy: It can estimate the number of unique people with very high precision (within a tiny margin of error).
Robustness: It works even if the "Alice" in the red coat looks slightly different from the "Alice" in the blue jacket, as long as they are still recognized as being in the same general "neighborhood" of the AI's memory.

What They Tested

The researchers tested this on:

MNIST (Handwritten Digits): Where the "clusters" are very clear (a '3' always looks like a '3'). Here, MaxSketch was perfect, even when counting sequences much longer than it was trained on.
CIFAR-10 (Small Color Images): Where things are messier. It still worked well, especially if the AI was already trained to recognize the objects.
Real Face Data: Using real photos of people from the wild. Even though the data wasn't perfect, MaxSketch gave a very good estimate of how many unique people were in a stream of thousands of photos, outperforming previous methods designed for messy data.

The Bottom Line

MaxSketch is a clever trick that turns a hard counting problem into a simple "maximum finding" problem. By leveraging the fact that modern AI naturally groups similar things together, it can count unique items in a massive, noisy stream using very little memory. It bridges the gap between old-school counting algorithms and modern AI, showing that if your data is organized nicely, you don't need to remember everything to know how many unique things are there.

Technical Summary: MaxSketch: Robust Distinct Counting in Streams via Random Projections

Problem Statement

The classical problem of estimating the number of distinct elements in a data stream is well-understood when repeated occurrences of an element are represented by identical keys (e.g., exact string matches). Algorithms like HyperLogLog achieve this with logarithmic memory by relying on consistent hash values. However, in modern data modalities (e.g., computer vision, natural language), observations are high-dimensional and noisy. Repeated instances of the same underlying object (e.g., different images of the same person) are only approximately similar, not identical.

In this "robust distinct counting" regime, classical sketches fail because they cannot distinguish between a new object and a noisy variation of an existing one. Recent work in general metric spaces has established a worst-case memory lower bound of $\tilde{\Omega}(\sqrt{n})$ for robust counting, which is exponentially worse than the $\tilde{O}(\log n)$ achievable in the exact setting. The central question addressed by this paper is whether the specific geometric structure found in modern learned representations—where observations of the same object form tight clusters and distinct objects correspond to well-separated directions—can bypass this $\sqrt{n}$ barrier.

Methodology: MaxSketch

The authors introduce MaxSketch, a simple, max-linear streaming sketch designed to exploit the geometric structure of learned embeddings.

Core Mechanism

Instead of summing or averaging projections (which scale with frequency and confuse distinctness with multiplicity), MaxSketch aggregates observations via maximum operations.

Random Projections: Given a stream of unit vectors $X = \langle \tilde{x}_1, \dots, \tilde{x}_n \rangle \subset S^{d-1}$ , the algorithm fixes $m$ independent random Gaussian vectors $w_1, \dots, w_m \sim \mathcal{N}(0, I_d)$ .
Max-Aggregation: For each projection $w_j$ , it computes the maximum inner product with any observation in the stream:
$M_j(X) = \max_{1 \le i \le n} \langle w_j, \tilde{x}_i \rangle$
Statistic: The final sketch is the average of these maxima:
$S(X) = \frac{1}{m} \sum_{j=1}^m M_j(X)$

Theoretical Foundation

The method relies on the assumption that the stream is $(\eta, \rho)$ -clusterable. This means:

Within-cluster alignment: Observations of the same object are directionally close to a latent center (controlled by $\eta$ ).
Cross-cluster separation: Latent centers of distinct objects have low inner products (controlled by $\rho$ ).

Under this assumption, the maximum projection of a set of vectors behaves like the maximum of independent Gaussians. The expectation of this maximum grows monotonically with the number of distinct latent directions (clusters). By analyzing the extreme-value statistics of Gaussian processes (using Slepian's inequality and concentration of Lipschitz functions), the authors prove that the gap in expected maxima between $k$ and $(1+\epsilon)k$ clusters is sufficient to distinguish them with high probability.

Key Contributions

MaxSketch Algorithm: A permutation-invariant, streaming-compatible sketch that operates directly on continuous embeddings. It discards multiplicity by construction, as additional repetitions of the same object do not increase the maximum projection value once the cluster's "peak" is reached.
Improved Memory Guarantees: The paper proves that under the natural clusterability assumption, MaxSketch achieves a $(1+\epsilon)$ -multiplicative approximation of the distinct count using $\tilde{O}(\log n / \epsilon^2)$ memory. This represents a substantial improvement over the $\tilde{\Omega}(\sqrt{n})$ lower bound known for general metric spaces without such structure.
Learning Reduction: The authors show that once the random projections are fixed, the dependence of the sketch on the input collapses to a single scalar statistic $S(X)$ that is monotone in the true count. Consequently, learning to predict the count reduces to fitting a one-dimensional monotone function (readout), which is sample-efficient and well-conditioned.
Fixed Sketch Existence: While theoretical guarantees initially assume fresh random projections for each stream, the paper proves that a single fixed set of projections suffices for a distribution of clusterable streams with high probability.

Experimental Results

The authors validate MaxSketch on three fronts:

MNIST: In a setting with low intra-class variability, MaxSketch (trained end-to-end with count-only supervision) achieves near-perfect accuracy and extrapolates to sequence lengths significantly longer than those seen during training. This confirms the theoretical prediction that when embeddings are well-clustered, the aggregation mechanism is robust.
CIFAR-10: In a setting with higher intra-class variability, end-to-end training from count supervision alone yields lower accuracy compared to using pretrained features. However, the model still captures the correct ordering of counts, suggesting that the difficulty lies in learning the clusterable geometry rather than the counting mechanism itself.
Real-World Face Streams: Using fixed pretrained embeddings (DeepFace) on merged face datasets (LFW, CelebA, Multi-PIE), MaxSketch is compared against Zhang's algorithm for robust distinct counting in general metric spaces. MaxSketch demonstrates superior robustness, maintaining high accuracy (e.g., $\ge 60\%$ within $\pm 50$ error) across a wide range of distinct counts (up to 5,100), whereas the baseline algorithm fails significantly due to the overlap in distance distributions that violates its strict geometric assumptions.

Significance and Claims

The paper claims to bridge the gap between classical streaming algorithms and modern representation learning. Its primary significance lies in demonstrating that geometric structure common in learned representations fundamentally reduces the complexity of distinct counting.

The authors argue that the $\sqrt{n}$ lower bound for robust counting is an artifact of worst-case metric spaces lacking structure. In the regime of modern deep learning, where "neural collapse" induces tight intra-class clusters and well-separated inter-class directions, the problem becomes tractable with polylogarithmic memory. MaxSketch serves as a theoretically grounded, analytically tractable solution that leverages this structure, offering a path to efficient distinct counting in noisy, high-dimensional data streams without requiring explicit clustering or identity supervision.