Introduction
In the era of big data, processing high-speed streams requires identifying "special items"—such as heavy hitters or persistent elements—to gain actionable insights. While traditional methods focus on single-dimensional analysis (e.g., identifying high-traffic source IPs), real-world utility often depends on understanding correlations between dimensions. These correlated pairs are defined as quadratic elements $(x \triangleleft y)$, such as a specific source IP targeting a specific destination IP.
Existing solutions for Correlated Heavy Hitters (CHH) often struggle with a trade-off between computational overhead and accuracy. Specifically, many algorithms suffer from data loss during the "warm-up" period, where an item transitions from being "cold" (infrequent) to "hot" (frequent). DUET addresses these challenges through a dual-component architecture that optimizes both memory usage and processing speed.
System Architecture and Methodology
DUET is designed as a generic framework capable of handling various stream-mining tasks by swapping internal components. Its core innovation lies in the separation of "potential hot" items from established "hot" items.
The DFilter (Dual Filter)
The DFilter serves as the entry point for the data stream. It consists of a standard frequency sketch (e.g., Count-Min sketch) and a secondary filter. When a quadratic element $(x \triangleleft y)$ arrives, the sketch tracks the frequency of the primary item $x$. Simultaneously, the filter stores the quadratic element if $x$ is not yet considered "hot" but shows potential. This "waiting room" mechanism ensures that the early occurrences of a pair—which contribute to an item becoming hot—are not discarded.
The STable (Shared Table)
Once an item $x$ exceeds a predefined frequency threshold, it is promoted to the STable. To maximize memory efficiency, STable employs a row-sharing strategy. Rather than allocating static memory blocks to every hot item, multiple items that hash to the same row compete for a shared pool of cells. This design exploits the inherent skewness of data streams, where a small fraction of items accounts for the majority of traffic, allowing DUET to maintain high precision within a compact memory footprint.
Experimental Evaluation
The researchers evaluated DUET against state-of-the-art algorithms like MGCHH and CSSCHH using four diverse datasets: CAIDA1/CAIDA2 (network traffic), Reddit (subreddit hyperlinks), and Stack (Stack Overflow interactions).
Performance Metrics
- Throughput: DUET processed data significantly faster than competitors, reaching up to 3.5x higher throughput. Its streamlined logic allows for line-rate processing, which is essential for modern high-speed network routers.
- Accuracy: The framework demonstrated exceptional precision. Its Average Relative Error (ARE) was frequently three orders of magnitude lower than prior methods. Even under extreme memory constraints (as low as 100KB), DUET maintained near-perfect recall.
- Versatility: By adjusting internal flags, the same framework successfully identified both heavy hitters (frequency-based) and persistent items (time-interval based).
Conclusion and Future Directions
DUET represents a significant advancement in stream processing by effectively capturing multi-dimensional correlations without the typical memory or speed penalties. While the current framework excels in fixed-window analysis, future work may involve refining its application to sliding windows and exploring its performance in fully decentralized, large-scale distributed systems.
Summary updated