TY - GEN
T1 - Finding critical thresholds for defining bursts
AU - Lahiri, Bibudh
AU - Akrotirianakis, Ioannis
AU - Moerchen, Fabian
PY - 2011
Y1 - 2011
N2 - A burst, i.e., an unusally high frequency of an event in a time-window, is interesting in monitoring systems as it often indicates abnormality. While the detection of bursts is well addressed, the question of what "critical" thresholds, on the number of events as well as on the window size, make a window "unusally bursty" remains a relevant one. The range of possible values for either threshold can be very large. We formulate finding the combination of critical thresholds as a 2D search problem and design efficient deterministic and randomized divide-and-conquer heuristics. For both, we show that under some weak assumptions, the computational overhead in the worst case is logarithmic in the sizes of the ranges. Our simulations show that on average, the randomized heuristic beats its deteministic counterpart in practice.
AB - A burst, i.e., an unusally high frequency of an event in a time-window, is interesting in monitoring systems as it often indicates abnormality. While the detection of bursts is well addressed, the question of what "critical" thresholds, on the number of events as well as on the window size, make a window "unusally bursty" remains a relevant one. The range of possible values for either threshold can be very large. We formulate finding the combination of critical thresholds as a 2D search problem and design efficient deterministic and randomized divide-and-conquer heuristics. For both, we show that under some weak assumptions, the computational overhead in the worst case is logarithmic in the sizes of the ranges. Our simulations show that on average, the randomized heuristic beats its deteministic counterpart in practice.
KW - Analytics for temporal data
KW - Massive data analytics
UR - https://www.scopus.com/pages/publications/80052336561
UR - https://www.scopus.com/inward/citedby.url?scp=80052336561&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-23544-3_37
DO - 10.1007/978-3-642-23544-3_37
M3 - Conference contribution
AN - SCOPUS:80052336561
SN - 9783642235436
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 484
EP - 495
BT - Data Warehousing and Knowledge Discovery - 13th International Conference, DaWaK 2011, Proceedings
T2 - 13th International Conference on Data Warehousing and Knowledge Discovery, DaWaK 2011
Y2 - 29 August 2011 through 2 September 2011
ER -