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

Finding special items, like heavy hitters, top-k items, and persistent items, has always been a hot issue in data stream processing. 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 in data streams to reveal the close correlations between the primary and secondary dimensions. Here, both the primary and secondary dimensions are selected according to specific mining purposes. Based on the special 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 theoretically and conduct extensive experiments on four publicly available data sets. Our experimental results show that DUET can achieve 3.5 higher throughput and three orders of magnitude lower average relative error compared with prior algorithms.