TY - GEN
T1 - Approximating frequent items in asynchronous data stream over a sliding window
AU - Chan, Ho Leung
AU - Lam, Tak Wah
AU - Lee, Lap Kei
AU - Ting, Hing Fung
PY - 2009
Y1 - 2009
N2 - 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( 1/ε log W log (ε B/log W) min{log W, 1/ε } 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( 1/ε log W log (ε 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].
AB - 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( 1/ε log W log (ε B/log W) min{log W, 1/ε } 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( 1/ε log W log (ε 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].
UR - http://www.scopus.com/inward/record.url?scp=78651251138&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-12450-1_5
DO - 10.1007/978-3-642-12450-1_5
M3 - Conference contribution
AN - SCOPUS:78651251138
SN - 3642124496
SN - 9783642124495
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 49
EP - 61
BT - Approximation and Online Algorithms - 7th International Workshop, WAOA 2009, Revised Papers
T2 - 7th Workshop on Approximation and Online Algorithms, WAOA 2009
Y2 - 10 September 2009 through 11 September 2009
ER -