TY - GEN
T1 - Better burst detection
AU - Zhang, Xin
AU - Shasha, Dennis
PY - 2006
Y1 - 2006
N2 - A burst is a large number of events occurring within a certain time window. Many data stream applications require the detection of bursts across a variety of window sizes. For example, stock traders may be interested in bursts having to do with institutional purchases or sales that are spread out over minutes or hours. In this paper, we present a new algorithmic framework for elastic burst detection [1]: a family of data structures that generalizes the Shifted Binary Tree, and a heuristic search algorithm to find an efficient structure given the input. We study how different inputs affect the desired structures and the probability to trigger a detailed search. Experiments on both synthetic and real world data show a factor of up to 35 times improvement compared with the Shifted Binary Tree over a wide variety of inputs, depending on the inputs.
AB - A burst is a large number of events occurring within a certain time window. Many data stream applications require the detection of bursts across a variety of window sizes. For example, stock traders may be interested in bursts having to do with institutional purchases or sales that are spread out over minutes or hours. In this paper, we present a new algorithmic framework for elastic burst detection [1]: a family of data structures that generalizes the Shifted Binary Tree, and a heuristic search algorithm to find an efficient structure given the input. We study how different inputs affect the desired structures and the probability to trigger a detailed search. Experiments on both synthetic and real world data show a factor of up to 35 times improvement compared with the Shifted Binary Tree over a wide variety of inputs, depending on the inputs.
UR - http://www.scopus.com/inward/record.url?scp=33749636117&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33749636117&partnerID=8YFLogxK
U2 - 10.1109/ICDE.2006.30
DO - 10.1109/ICDE.2006.30
M3 - Conference contribution
AN - SCOPUS:33749636117
SN - 0769525709
SN - 9780769525709
T3 - Proceedings - International Conference on Data Engineering
SP - 146
BT - Proceedings of the 22nd International Conference on Data Engineering, ICDE '06
T2 - 22nd International Conference on Data Engineering, ICDE '06
Y2 - 3 April 2006 through 7 April 2006
ER -