MaxSketch: Robust Distinct Counting in Streams via Random Projections
Nikos Tsikouras 1,2 Constantine Caramanis 2,3 Christos Tzamos 1,2 1 National and Kapodistrian University of Athens, Greece 2 Archimedes, Athena Research Center, Greece 3 The University of Texas at Austin, USA · 2026
Read MaxSketch: Robust Distinct Counting in Streams via Random Projections by Nikos Tsikouras 1,2 Constantine Caramanis 2,3 Christos Tzamos 1,2 1 National and Kapodistrian University of Athens, Greece 2 Archimedes, Athena Research Center, Greece 3 The University of Texas at Austin, USA (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-15571.txt.
Introduction
Nikos Tsikouras, Constantine Caramanis, and Christos Tzamos count distinct items in streams where repeats look only roughly alike. Think of varied photos of one person. Classic sketches fail since they need matching hashes for repeats. Broad metric-space methods need about square-root memory. Their MaxSketch uses random Gaussian projections. Under geometric structure common in learned representations, it needs only about logarithmic memory. Image-stream tests prove it counts well past its training regime.
Catalog record
| CREATOR | Nikos Tsikouras 1,2 Constantine Caramanis 2,3 Christos Tzamos 1,2 1 National and Kapodistrian University of Athens, Greece 2 Archimedes, Athena Research Center, Greece 3 The University of Texas at Austin, USA |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95181 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.15571
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
MaxSketch: Robust Distinct Counting in Streams via Random Projections Nikos Tsikouras 1,2 Constantine Caramanis 2,3 Christos Tzamos 1,2 1 National and Kapodistrian University of Athens, Greece 2 Archimedes, Athena Research Center, Greece 3 The University of Texas at Austin, USA Abstract 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 Θ ~ ( n ) \tilde{\Theta}(\sqrt{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 = O ~ ( log n / ε 2 ) m=\tilde{O}(\log n/\varepsilon^{2}) random projections (and hence O ~ ( log n / ε 2 ) \tilde{O}(\log n/\varepsilon^{2}) memory) suffice to recover the true distinct count within a ( 1 + ε ) (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. 1 Introduction Counting the number of distinct elements in a data stream is a classical algorithmic problem with deep connections to randomized algorithms, information theory, and large-scale data analysis. In its canonical form, the task is to estimate the number of unique keys in a stream using sublinear memory and a single pass over the data. A long line of work has shown that this is possible with striking efficiency: algorithms such as 5 ; 6 ; 7 achieve accurate estimates using only logarithmic memory by maintaining carefully designed randomized sketches of the stream. These classical results, however, rely on a crucial assumption: the same element is represented identically every time it appears. In modern data modalities, this assumption is fundamentally violated. To see this, consider the task of counting the number of distinct people passing through a busy intersection observed by a camera. Suppose Alice and Bob each pass through once, and later Alice passes through again. Although it is the same underlying individual, her second appearance may differ substantially at the pixel level, due to changes in lighting, viewpoint, or pose. As a result, the two observations of Alice may be nearly as different from each other as they are from observations of entirely different individuals. A natural approach is to embed each photo into a continuous feature space and apply distinct counting in that representation. However, this does not resolve the issue: repeated observations of the same underlying object are no longer identical, causing sketching methods to overcount, while clustering-based approaches require maintaining a number of representatives that grows with the number of distinct elements, undermining the sublinear memory guarantees of streaming algorithms. A recent line of work 2 ; 3 ; 30 has studied this robust distinct counting problem, where elements are considered equal if they are sufficiently close in some metric. While these results give algorithms with non-trivial guarantees, they also reveal that the problem is fundamentally harder than its classical counterpart: 30 establishes an \Omega(\sqrt{n}) memory lower bound in general metric spaces, exponentially far from the rates achievable under exact key equality. Modern representation learning, however, often induces a more useful geometric structure than the distance-based separation studied above: observations of the same object form tight clusters in embedding space, while different objects correspond to well-separated directions. This raises a central question: Closeness of representations in an arbitrary metric space is not strong enough to allow robust distinct counting with polylogarithmic memory ( {\Omega}(\sqrt{n}) lower bound in 30 ). Does clustered geometry with intra-class closeness and inter-class separation bypass this barrier? This question sits at the intersection of classical streaming algorithms and modern representation learning. On the one hand, the theory of distinct counting demonstrates that extreme-value statistics of random projections contain sufficient information about the number of unique elements 6 ; 18 . On the other hand, permutation-invariant architectures such as DeepSets 29 can in principle aggregate set-structured data, but provide no theoretical guarantees on recovering global combinatorial properties like distinct counts. In this work, we bridge this gap with a deliberately minimal max-linear sketch that is both analytically tractable and provably correct. 1.1 A geometric model for distinct objects We assume that each distinct object corresponds to an unknown latent direction in a high-dimensional space, and that each observation is a noisy but well-aligned version of its object’s direction. Different objects occupy well-separated directions, with low inner products between distinct centers. This is not an abstraction: the neural collapse phenomenon formalizes why this configuration emerges in the terminal phase of deep network training 22 ; 31 . Under this model, the number of distinct objects corresponds to the number of well-separated directions generating the stream. The challenge is to recover this number without explicitly clustering and without storing the embeddings. The \Omega(\sqrt{n}) lower bound of 30 is achieved by adversarial metric spaces with no geometric structure. Our setting is not a special case that sidesteps this lower bound; it is the regime that actually occurs in practice, and one that 30 explicitly leaves open. It is precisely this inner-product structure that enables Gaussian extreme-value statistics whose expectations separate different cardinalities, yielding polylogarithmic memory where the worst-case general-metric setting requires \tilde{\Omega}(\sqrt{n}) . 1.2 MaxSketch: a max-linear analogue of classical sketches Our key observation is that max aggregation discards multiplicity by construction: once a cluster has contributed a large projection value, additional repetitions of the same object leave the sketch unchanged. This contrasts sharply with sum or mean aggregation, which scale with frequency and therefore confuse distinctness with multiplicity. Given random Gaussian vectors w_{1},\dots,w_{m}\in\mathbb{R}^{d} , we compute M_{j}(X)=\max_{1\leq i\leq n}\langle w_{j},x_{i}\rangle where x_{1},\dots,x_{n}\in\mathbb{R}^{d} are observations generated from k underlying objects, and average these maxima across projections. The expectation of this statistic grows monotonically with the number of distinct latent directions — the key signal we wish to recover. This operation is permutation-invariant, streaming-compatible, and requires storing only m scalars. We call this representation MaxSketch. Unlike classical sketches such as HyperLogLog, MaxSketch operates directly on continuous embeddings and tolerates noise and approximate equality. Unlike general-purpose neural set models, MaxSketch is deliberately minimal and analytically tractable. 1.3 Theoretical guarantees Our main result shows that MaxSketch provably recovers the number of distinct objects up to multiplicative error. Informal Theorem 4.4 (Robust Distinct Count Estimation). Under a natural clusterability assumption, m=\tilde{O}(\log n/\varepsilon^{2}) random projections suffice to estimate the number of distinct objects in a stream of length n within a (1+\varepsilon) multiplicative error, with high probability. Compared to the \tilde{\Omega}(\sqrt{n}) memory required in general metric spaces 30 ; the improvement is enabled