Name
Abstract | ||
|---|---|---|
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. Hi, who gave an 0 (1/epsilon log W log (cB/logw) min{log W, 1/epsilon log vertical bar U vertical bar) 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(1/epsilon log W log(cB/10 gBw) log log VV) space. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.3390/a4030200 | ALGORITHMS |
Keywords | Field | DocType |
asynchronous data streams, frequent items, sliding window, space complexity | Log-log plot,Asynchronous communication,Data structure,Mathematical optimization,Sliding window protocol,Data stream,Algorithm,Real-time computing,Timestamp,Out-of-order execution,Mathematics | Journal |
Volume | Issue | Citations |
4 | 3 | 3 |
PageRank | References | Authors |
0.39 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hing-Fung Ting | 1 | 76 | 11.69 |
| Lap-Kei Lee | 2 | 406 | 21.59 |
| Ho-Leung Chan | 3 | 471 | 25.23 |
| Tak-Wah Lam | 4 | 1860 | 164.96 |