%0 Journal Article %T Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window %A Hing-Fung Ting %A Lap-Kei Lee %A Ho-Leung Chan %A Tak-Wah Lam %J Algorithms %D 2011 %I MDPI AG %R 10.3390/a4030200 %X 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 an O ( 1/¦Å log W log ( ¦ÅB/ log W) min { log W, 1/¦Å}£¿ log |U|)- space data structure that can approximate the frequent items within an ¦Å error bound, where W and B are parameters of the sliding window, and U is the set of all possible item names. We gave a more space-efficient data structure that only requires O ( 1/¦Å log W log ( ¦ÅB/ logW)£¿ log log W) space. %K asynchronous data streams %K frequent items %K sliding window %K space complexity %U http://www.mdpi.com/1999-4893/4/3/200