1 September 2025 in IEEE Transactions on Network and Service Management
Skewed data streams are characterized by uneven distributions in which a small fraction of elements occur with much higher frequency than others. The detection of these high-frequency elements presents significant practical challenges, particularly under stringent memory constraints, as existing detection techniques have typically relied on predefined thresholds that require significant memory usage. However, this approach is highly inefficient since not all elements require equal storage space. To address these limitations, we introduce HeavyFinder (HF), a novel lightweight network measurement architecture designed to detect high-frequency elements in skewed data. HF employs a threshold-free update strategy that enables dynamic adaptation to variable data, thereby providing greater flexibility for tracking high-frequency elements without requiring fixed thresholds. Furthermore, an included memory-light strategy enables high accuracy for non-uniform distributions, even with limited memory allocation. Experimental results showed that HF significantly improved performance in four query tasks, producing an accuracy of 99.81% when identifying the top-k elements. The average absolute error (AAE) was also reduced to 10-4 using only 100KB of memory, which was significantly lower than that of conventional methods.
22 May 2026 in IEEE Transactions on Knowledge and Data Engineering
Efficient data stream processing, particularly for persistence estimation, is crucial in handling high-velocity data streams characterized by skewed distributions of item frequencies. Unlike more straightforward frequency metrics, persistence captures items' recurrence across multiple time windows, posing a significant challenge to existing single-structure sketches where high-persistence and low-persistence items collide. To address this, we introduce the Hypersistent Sketch, a unified framework for high-performance estimation built on two decoupled mechanisms: filtering and accelerating. The filtering component, a Cold Filter, directly addresses the skewed nature of data streams. It separates hot items from the majority of cold ones, which allows for differential treatment. The accelerating component, a Burst Filter, then optimizes the processing of hot items. It significantly improves throughput by preventing repeated insertions within a single window. We demonstrate its generality by applying it to various state-of-the-art sketches (e.g., On-Off, Waving, P-Sketch), showing it consistently enhances their original performance. We also deploy our framework on Redis platforms, demonstrating the framework’s broad applicability and scalability.