One-sentence Summary

The University of Edinburgh introduces Stable-Sketch, a versatile sketch for web-scale data stream processing that exploits multidimensional information including item statistics and a novel bucket stability metric to drive stochastic replacement decisions, enabling substantially more accurate and faster detection of heavy hitters, heavy changers, and persistent items under tight memory budgets than state-of-the-art sketches, with further throughput gains from SIMD instructions and a P4 implementation demonstrating real-world deployment viability.

Key Contributions

• Bucket stability is introduced as a metric for quantifying recorded item variation and is shown to help identify relevant item types such as heavy hitters, heavy changers, and persistent items.

• Stable-Sketch is proposed as a sketch-based structure that combines item statistics with bucket stability and applies stochastic replacement decisions to improve detection accuracy under tight memory budgets.

• Theoretical error bounds and extensive experiments establish that Stable-Sketch achieves higher detection accuracy and faster processing than state-of-the-art sketches, while SIMD and P4 implementations support high-throughput deployment.

Introduction

Measurements of web-centric streams are essential for user behavior analysis, traffic analysis, intrusion detection, and web personalization, but per-item tracking is impractical at high rates, so sketches are used to approximate heavy hitters, heavy changers, and persistent items within small memory. Prior schemes often use one-dimensional item features to decide when to replace stored items, which hurts accuracy under tight L1 cache budgets, skewed distributions, frequent hash collisions, pointer or DRAM overhead, and delicate parameter tuning, and they can be hard to deploy on fast hardware platforms. The authors leverage bucket stability, a multi-dimensional signal reflecting how often a bucket changes, and item information to define Stable-Sketch, a versatile sketch that uses replacement probabilities based on both signals. They present theoretical error bounds, SIMD acceleration, experiments across detection tasks, and a P4 prototype to show that it offers high accuracy, compact memory, fast updates, and practical deployment.

Method

The authors leverage a flat sketch architecture to address the core reliability problem in compact streaming detection: replacement policies that rely only on a single counter, such as frequency or persistence, can mistakenly evict useful heavy or persistent items. Their key insight is that buckets with higher persistence of recorded items are more likely to contain genuinely important data. They formalize this idea as bucket stability, where the stability of a bucket increases when an arriving item maps to that bucket but fails to change the recorded key, and decreases when the recorded key is actually replaced, with a floor at zero. Since heavy items are expected to dominate their mapped buckets over time, buckets tracking heavy items should exhibit higher stability. Refer to the figure below:

This observation motivates a multidimensional replacement decision that combines item relevance information with bucket stability, making it progressively harder for non-heavy items to displace potential heavy items under tight memory budgets.

The data structure of Stable-Sketch is a flat array with $m$m rows and $u$u columns. Each row is associated with a different pairwise independent hash function $h_1, \ldots, h_m$h1​,…,hm​, and $B(i,j)$B(i,j) denotes the bucket in row $i$i and column $j$j. Each bucket stores three fields: a key field $B(i,j).K$B(i,j).K, a value counter $B(i,j).V$B(i,j).V, and a stability counter $B(i,j).S$B(i,j).S. The key field can store the full item key for invertibility, or a fingerprint in a memory constrained variant. The value counter stores the task specific statistic, such as frequency or persistence, while the stability counter summarizes how consistently the same item occupies the bucket. Refer to the framework diagram:

Stable-Sketch performs two main operations, update and query. During an update, an arriving item $f$f is hashed through rows sequentially. If the mapped bucket is empty, the item is inserted and the bucket is initialized as $B(1,h_1(f)).K = f$B(1,h1​(f)).K=f, $B(1,h_1(f)).V = 1$B(1,h1​(f)).V=1, and $B(1,h_1(f)).S = 1$B(1,h1​(f)).S=1. If the mapped bucket already stores $f$f, both $V$V and $S$S are incremented. If the item finds no available bucket, the update enters a probabilistic decay phase. The sketch selects the bucket with the smallest value counter among the $m$m hashed buckets, denoted as $B(R,M)$B(R,M). It then computes a replacement probability

This probability design means that buckets with both high recorded value and high stability are less likely to be replaced. If a random trial fails, the new item is discarded. If it succeeds, the value counter of the selected bucket is decremented by one. If that counter reaches zero, the bucket adopts the new item, the value counter is reset to one, and the stability counter is reduced by one. Because the procedure uses decay rather than immediate eviction, the estimation error is one sided, affecting only underestimation. The query operation scans all buckets and returns items whose estimated value exceeds a configured threshold.

For heavy hitter detection, the update procedure can be understood through three representative cases. An item that finds an empty bucket is inserted immediately and the hash search terminates. An item that finds a bucket already containing its own key increments the corresponding value and stability counters. An item that collides in every row targets the bucket with the smallest value counter and applies the decay rule above. Refer to the update examples:

The same underlying structure can be adapted to other detection tasks. For heavy changer detection, the authors construct separate sketches over consecutive time epochs and compare per item frequency differences at query time. Items whose difference exceeds a threshold are reported as heavy changers. For persistent item detection, a flag bit is added to each bucket to ensure that persistence is incremented at most once per time window. The flag is reset at the beginning of each window, and if the selected bucket already has an active flag for the current window, the replacement attempt is rejected. This prevents duplicated persistence updates while preserving the stability driven protection mechanism.

The method is accompanied by a formal error guarantee. For any item $f$f with actual value $V(f)$V(f) and estimated value $\hat{V}(f)$V^(f), the design satisfies

which means Stable-Sketch does not overestimate item values. Under the assumption that a heavy item remains in its bucket after insertion, the authors further derive an underestimation bound of the form

where $S$S is the stability associated with the bucket recording $f$f, $\varphi$φ is the Euler-Mascheroni constant, and $N$N denotes the total number of entries across all items. This bound captures the role of stability in reducing underestimation risk.

For deployment efficiency, the update path can be accelerated with SIMD instructions. Instead of inspecting rows one by one, the implementation uses a strong hash primitive, MurmurHash3_x64_128, to compute a hash value and split it into $m$m parts corresponding to the rows. The newly arrived item key is then compared against keys recorded in multiple rows in parallel using a SIMD equality primitive, such as _mm256_cmpeq_epi64. This reduces the cost of locating the first available matching bucket from a sequential row scan to a parallel comparison step. Refer to the throughput comparison:

This optimization improves update throughput while preserving the semantic behavior that each item is tracked in the first available bucket. When the sketch grows beyond the fastest cache level, data retrieval from slower memory regions increases latency and can reduce throughput, so the speedup is strongest when the active working set remains cache friendly.

Experiment

The experiments evaluate Stable-Sketch on real traffic datasets for heavy hitter, heavy changer, and persistent item detection, comparing it with representative sketch-based baselines under varying memory budgets. Stable-Sketch consistently achieves higher detection accuracy and lower estimation error, while ablations and threshold studies confirm its robustness and the contribution of its design components. It also provides faster updates and queries than baseline methods, and its performance remains practical when accelerated with SIMD and deployed on a programmable switch.

Across three CAIDA traces, MV-Sketch wrong replacements of heavy items by non-heavy items drop sharply as memory size increases from 16KB to 256KB. Tight memory causes hundreds of thousands of erroneous replacement events, while larger memory reduces them to hundreds or fewer. CAIDA 2016 shows the largest wrong replacement count at 16KB, and CAIDA 2018 shows the smallest at 256KB. Memory pressure strongly increases erroneous heavy-item eviction in MV-Sketch. Higher memory budgets consistently reduce wrong replacement events across all three traces.

The experiment evaluates how memory size affects incorrect heavy-item replacements by non-heavy items in MV-Sketch across three CAIDA network traces. It validates that tight memory budgets cause frequent erroneous evictions of heavy items, while increasing available memory sharply reduces these replacement errors. Overall, the findings show that memory pressure is a dominant factor in MV-Sketch accuracy, with larger memory allocations consistently improving heavy-item retention.