Approximating frequent items in asynchronous data stream over a sliding window (Q1736485)

Summary: 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 \textit{G. Cormode} [``Time-decaying aggregates in out-of-order streams'', in: Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems, PODS'08. New York, NY. 89--98 (2008; \url{doi:10.1145/1376916.1376930})], who gave an \(O\left(\frac{1}{\epsilon} \log W \log\left(\frac{\epsilon B}{\log W}\right) \min \left\{\log W, \frac{1}{\epsilon} \right\} \log | U|\right)\)-space data structure that can approximate the frequent items within an \(\epsilon\) 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\left(\frac{1}{\epsilon} \log W \log\left(\frac{\epsilon B}{\log W}\right) \log \log W\right)\) space.