Better burst detection

Xin Zhang, Dennis Shasha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 22nd International Conference on Data Engineering, ICDE '06
Pages146
Number of pages1
DOIs
StatePublished - 2006
Event22nd International Conference on Data Engineering, ICDE '06 - Atlanta, GA, United States
Duration: Apr 3 2006Apr 7 2006

Publication series

NameProceedings - International Conference on Data Engineering
Volume2006
ISSN (Print)1084-4627

Other

Other22nd International Conference on Data Engineering, ICDE '06
Country/TerritoryUnited States
CityAtlanta, GA
Period4/3/064/7/06

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems

Fingerprint

Dive into the research topics of 'Better burst detection'. Together they form a unique fingerprint.

Cite this