DUET: A Generic Framework for Finding Special Quadratic Elements in Data Streams

Jiaqian Liu, Haipeng Dai, Rui Xia, Meng Li, Ran Ben Basat, Rui Li, Guihai Chen

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 DUET framework architecture, featuring the DFilter for early-stage tracking and the STable for persistent 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 DFilter mechanism: inserting a quadratic element while updating the primary item's frequency in the sketch.

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

Abstract

Finding special items, like heavy hitters, top-k, and persistent items, has always been a hot issue in data stream processing for web analysis. While data streams nowadays are usually high-dimensional, most prior works focus on special items according to a certain primary dimension and yield little insight into the correlations between dimensions. Therefore, we propose to find special quadratic elements to reveal close correlations. Based on the items mentioned above, we extend our problem to three applications related to heavy hitters, top-k, and persistent items, and design a generic framework DUET to process them. Besides, we analyze the error bound of our algorithm and conduct extensive experiments on four data sets. Our experimental results show that DUET can achieve 3.5 times higher throughput and three orders of magnitude lower average relative error compared with cutting-edge algorithms.
BibTeX
@inproceedings{liu2022duet,
  author = {Jiaqian Liu and Haipeng Dai and Rui Xia and Meng Li and Ran Ben Basat and Rui Li and Guihai Chen},
  title = {{DUET: A Generic Framework for Finding Special Quadratic Elements in Data Streams}},
  booktitle = {The Web Conference},
  year = {2022},
  doi = {10.1145/3485447.3512019},
}
Figure