Evolving Sketch: Time-Decaying Frequency Estimation for Evolving Streams

Frequency estimation approximates element occurrences using limited memory and is fundamental in data stream processing. Traditional probabilistic sketches provide spaceefficient solutions but treat all occurrences equally regardless of timing, causing suboptimal performance when recent observations matter more than history. To address this, emerging studies have refined sketches using time-decaying methods, such as continuous decay functions and sliding window techniques. However, existing approaches typically rely on fine-tuned parameters configured in advance (such as decay coefficients or window sizes), which is often unrealistic in large-scale deployment scenarios where data streams exhibit unpredictable behaviors and holistic parameters tuning becomes prohibitively expensive. Moreover, existing studies keep these parameters fixed throughout the entire system's lifetime, which can only decay element occurrences at fixed rates and may fail to capture long-term pattern evolution. This paper introduces Evolving Sketch, a novel time-decaying frequency estimation framework that dynamically adapts its decay parameters based on real-time application feedback. Evolving Sketch consists of two main components: a decay sketch that maintains frequency estimates using time-decaying mechanisms with numerical stability guarantees, and an adapter that implements a pluggable interface supporting multiple optimization strategies from gradient-based to bandit-based methods. Such a modular design allows applications to choose the adaptation strategies that best match their specific requirements and environmental characteristics, which is verified through extensive experiments in real-world application scenarios including cache eviction and e-commerce online product ranking maintenance (maintaining a $K$-sized ranked list under time-decayed frequencies). Compared to existing approaches, Evolving Sketch can at most reduce the cache miss ratios from 26.3% to 16.7% and substantially improve ranking quality, measured by DCG, by up to 21.8%.