Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window

Algorithms

Hing-Fung Ting¹  Lap-Kei Lee²  Ho-Leung Chan¹ 

[1] Department of Computer Science, University of Hong Kong, Pokfulam, Hong Kong, China; E-Mails:;MADALGO (Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation), Department of Computer Science, Aarhus University, Aarhus C DK-8000, Denmark; E-Mail:

关键词: asynchronous data streams;    frequent items;    sliding window;    space complexity;   

DOI  :  10.3390/a4030200

来源: mdpi

【 摘 要 】

In an asynchronous data stream, the data items may be out of order with respect to their original timestamps. This paper studies the space complexity required by a data structure to maintain such a data stream so that it can approximate the set of frequent items over a sliding time window with sufficient accuracy. Prior to our work, the best solution is given by Cormode et al. [1], who gave anspace.

【 授权许可】

CC BY   
© 2011 by the authors; licensee MDPI, Basel, Switzerland.