Name
Abstract | ||
|---|---|---|
In an asynchronous data stream, the data items may be out of order with respect to their original timestamps. This paper gives
a space-efficient data structure to maintain such a data stream so that it can approximate the frequent item set over a sliding
time window with sufficient accuracy. Prior to our work, Cormode et al. [3] have the best solution, with space complexity
O(\frac1e</font
> logW log(\frace</font
>BlogW) min{logW, \frac1e</font
>}logU)O(\frac{1}{\varepsilon} \log W \log (\frac{\varepsilon B}{\log W}) \min\{\log W, \frac{1}{\varepsilon}\}\log U), where ε is the given error bound, W and B are parameters of the sliding window, and U is the number of all possible item names. Our solution reduces the space to
O(\frac1e</font
> logW log(\frace</font
>BlogW))O(\frac{1}{\varepsilon} \log W \log (\frac{\varepsilon B}{\log W})). We also unify the study of synchronous and asynchronous data stream by quantifying the delay of the data items. When the
delay is zero, our solution matches the space complexity of the best solution to the synchronous data streams [8].
|
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-12450-1_5 | Workshop on Approximation and Online Algorithms |
Keywords | Field | DocType |
space-efficient data structure,frequent item,synchronous data stream,data item,best solution,asynchronous data stream,possible item name,varepsilon b,data stream,space complexity,out of order,data structure,sliding window | Asynchronous communication,Data structure,Combinatorics,Data stream mining,Sliding window protocol,Data stream,Computer science,Out-of-order execution | Conference |
Volume | ISSN | ISBN |
5893 | 0302-9743 | 3-642-12449-6 |
Citations | PageRank | References |
1 | 0.35 | 15 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ho-Leung Chan | 1 | 471 | 25.23 |
| Tak-Wah Lam | 2 | 1860 | 164.96 |
| Lap-Kei Lee | 3 | 406 | 21.59 |
| Hing-Fung Ting | 4 | 107 | 8.17 |