Sublime: A New Sketch Algorithm Rethinks How Big Data Systems Track Endless, Skewed Data Streams

ScienceTrace Feature

Every time you scroll a video feed, tap a card reader, or send a packet across the internet, some system somewhere has to notice — instantly and without storing every single event forever. That quiet counting problem sits at the core of what people casually call "Big Data," and in June 2026 a team of computer scientists gave it a genuine upgrade. Their paper, Sublime: Sublinear Error & Space for Unbounded Skewed Streams, was accepted to ACM SIGMOD 2026, published in the Proceedings of the ACM on Management of Data, and received a Best Paper Honorable Mention. It tackles a structure that almost every large-scale data system quietly depends on: the frequency-estimation sketch.

The Problem Hiding Inside Every Big Data System

Imagine trying to count how many times each of a billion different items — search queries, IP addresses, product IDs, sensor readings — appears in a stream that never stops. Keeping an exact tally for every item would require a lookup table with as many entries as there are distinct items, which for real internet-scale traffic can mean gigabytes of memory just for bookkeeping. That is often more memory than a system can spare while still processing millions of events per second.

Computer scientists solved a version of this problem decades ago by trading a small, controlled amount of accuracy for a huge savings in memory. Instead of one counter per item, a "sketch" uses a much smaller array of counters shared across many items through hashing. The best-known example, the Count-Min Sketch, works by hashing each incoming item into several rows of a compact table and incrementing one counter per row:

Insert(x): for j = 1..d: CM[j, h_j(x)] += 1

To estimate how often an item has appeared, the sketch takes the smallest of its counters, since collisions can only ever push a count up, never down:

f̂(x) = min_{j=1..d} CM[j, h_j(x)]

With a table width of roughly w = ⌈e/ε⌉ and depth d = ⌈ln(1/δ)⌉, the classic guarantee is that the estimate never undershoots the true count and, with probability at least 1-δ, overshoots by no more than εN, where N is the total number of items seen. This bound, from Cormode and Muthukrishnan's original 2005 paper, is the workhorse behind network routers, database query planners, and streaming-analytics platforms in production today.

Two Cracks the Field Had Learned to Live With

The Sublime paper's contribution starts by naming two weaknesses that engineers have quietly tolerated in Count-Min-style sketches for twenty years.

The first is memory waste under skew. Real-world data is almost never uniform — a small number of items (a viral video, a popular product, a malicious IP address) account for a hugely disproportionate share of traffic, a pattern often modeled with a Zipf distribution. Classic sketches allocate every counter the same fixed width, sized for the worst case. That means millions of counters that will only ever hold small numbers are reserving bits they will never use, purely so the rare "heavy hitter" counters have enough room to grow.

The second weakness is more subtle: accuracy decays as the stream keeps running. Because a sketch has a fixed number of counters, the error term εN grows in lockstep with N, the total volume of the stream. A sketch tuned to be accurate after a million events becomes proportionally less trustworthy after a billion, unless an engineer periodically resizes or resets it — an operational headache for systems, like fraud detection or long-running analytics dashboards, that are never supposed to stop.

What Sublime Actually Changes

Rather than proposing a brand-new sketch from scratch, the authors — Navid Eslami and Niv Dayan at the University of Toronto, working with Ioana Bercea and Rasmus Pagh in Denmark — built a general framework that can wrap around existing sketches, including Count-Min Sketch, Count Sketch, and the older Misra-Gries algorithm, and correct both weaknesses at once.

Sublime's first idea is variable-length counters. Instead of committing every counter to a fixed number of bits up front, each counter starts small and is only extended, within the same CPU cache line, if and when it actually overflows. Because the vast majority of counters in a skewed stream never come close to overflowing, this alone recovers a large amount of memory that classic sketches spend defensively.

The second idea is an expandable counter array. Rather than fixing the sketch's dimensions once at start-up, Sublime grows the number of counters over time, at a configurable rate, as more of the stream is observed. Spreading the same items across a slowly widening table keeps collisions — and therefore error — from accumulating the way they do in a fixed-size sketch. The result, the authors show, is a sketch whose error and memory footprint both grow sublinearly with the length of the stream, instead of tracking it directly, and they additionally prove a matching lower bound showing that no length-adaptive sketch can do fundamentally better. In their evaluation, wrapping Sublime around existing sketches like Count-Min and Count Sketch improved both memory use and estimation accuracy compared with the unmodified, fixed-size originals, particularly on realistically skewed workloads.

Why "Sublinear" Is the Word That Matters

The term sublinear sounds like jargon, but it captures the entire point of this branch of computer science. If you wanted to answer "how many times did X appear?" perfectly, for every possible X, in a stream of N events drawn from a universe of U distinct items, the honest cost is:

Memory(exact) = Θ(U · log N)

bits — one counter, sized for the largest possible count, for every item that could ever show up. A sketch's entire purpose is to make that cost independent of U, replacing it with a much smaller budget in exchange for a bounded, quantifiable amount of error. What Sublime adds is making that budget adapt gracefully as N itself keeps growing forever, instead of forcing an engineer to guess a stream's eventual size in advance, over-provision for it, and pay for that guess in memory from the very first event.

Standing on Forty Years of Streaming Algorithms

None of this appears out of nowhere. The lineage runs from Misra and Gries' 1982 algorithm for finding frequently repeated elements with minimal memory, through Charikar, Chen, and Farach-Colton's Count Sketch in the early 2000s, to Cormode and Muthukrishnan's Count-Min Sketch in 2005 — work that Muthukrishnan later framed as part of the broader field of streaming algorithms, built around a simple discipline: touch each piece of data once, keep only a small summary, and never look back. Sublime's contribution fits squarely in that tradition, treating decades-old sketches not as fixed artifacts but as a starting point that a smarter memory layout can still meaningfully improve.

Where This Actually Gets Used

Frequency-estimation sketches are unglamorous compared to headline-grabbing AI models, but they are everywhere underneath the surface of modern infrastructure. Network operators use them to spot the small number of IP addresses responsible for a denial-of-service flood, without logging every packet that crosses a router. Database engines use them to estimate how many rows will match a query before running it, so the optimizer can choose a fast execution plan. Streaming-analytics and recommendation platforms use them to identify trending items in real time across billions of events per day, and cybersecurity systems use them to flag anomalous spikes in traffic that might indicate an attack. In every one of these settings, a sketch that keeps working reliably after a billion events instead of quietly degrading — using less memory to do it — is a direct, practical improvement rather than an abstract theoretical one.

The authors have released a reference implementation of Sublime as open-source software, allowing systems researchers and engineers to test the framework against Count-Min Sketch, Count Sketch, and Misra-Gries directly on their own workloads rather than taking the paper's benchmarks on faith.

The ScienceTrace Perspective

It is tempting to think Big Data's frontier is only about bigger models and faster chips. Sublime is a reminder that some of the most consequential progress in data science still happens at the level of how a single counter is stored in memory — unglamorous, mathematically rigorous work that nonetheless touches nearly every large-scale system running today. A sketch that adapts its own memory footprint as a stream grows, rather than being handed a fixed budget and hoping it lasts, is a small idea with an outsized reach.

The hardest problems in Big Data are rarely about having more data. They are about remembering the right amount of it, forever, without running out of room.

As data streams keep growing — from IoT sensors, financial transactions, scientific instruments, and global network traffic — the sketches quietly counting them in the background will need to keep growing smarter too. Sublime suggests that even a fifty-year-old counting problem still has meaningful headroom left.

References

[1] Eslami, N., Bercea, I. O., Pagh, R., & Dayan, N. (2026). "Sublime: Sublinear Error & Space for Unbounded Skewed Streams." Proceedings of the ACM on Management of Data (PACMMOD), 4(3), Article 239. https://doi.org/10.1145/3802116

[2] Cormode, G., & Muthukrishnan, S. (2005). "An Improved Data Stream Summary: The Count-Min Sketch and its Applications." Journal of Algorithms, 55(1), 58–75.

[3] Charikar, M., Chen, K., & Farach-Colton, M. (2004). "Finding Frequent Items in Data Streams." Theoretical Computer Science, 312(1), 3–15.

[4] Misra, J., & Gries, D. (1982). "Finding Repeated Elements." Science of Computer Programming, 2(2), 143–152.

[5] Muthukrishnan, S. (2005). "Data Streams: Algorithms and Applications." Foundations and Trends in Theoretical Computer Science, 1(2), 117–236.