SketchBuilder: Learning-Augmented Proactive Sketch Construction for Heavy Hitter Detection in Data Streams

Heavy hitter detection is a fundamental problem in data stream processing with broad applications. State-of-the-art self-adjusting sketches adapt to skewed streams by repeatedly adjusting local memory structures at runtime. However, they largely overlook global sketch-level collisions that persistently map multiple heavy hitters to the same memory regions. Such collisions not only degrade estimation accuracy but also induce frequent structural readjustments, incurring substantial overhead and undermining overall efficiency. We present SketchBuilder, a learning-augmented framework that introduces a new paradigm by shifting from reactive adaptation to proactive sketch construction. By leveraging historical sketches to anticipate stream evolution, SketchBuilder jointly optimizes sketch construction along two coordinated dimensions via complementary modules: (1) a Dispatcher that refines global item mapping to proactively mitigate heavy hitter collisions, and (2) a Constructor that pre-allocates local memory layouts based on predicted demand. The proactive optimization enables SketchBuilder to construct collision-aware, workload-tailored sketches in advance, significantly reducing costly runtime adjustments while providing additional robustness to distribution shifts through a flexible scaling mechanism. Experiments on real-world traces demonstrate that SketchBuilder achieves an F?-score of 0.99 for top-k detection and 99.70% precision for threshold-t detection using only 100 KB of memory. Compared with SOTA work, it reduces average absolute error by up to 99.81%, improving both accuracy and efficiency.