Article

Efficient elastic burst detection in data streams

Authors:

Dennis ShashaAuthors Info & Claims

KDD '03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 336 - 345

https://doi.org/10.1145/956750.956789

Published: 24 August 2003 Publication History

Abstract

Burst detection is the activity of finding abnormal aggregates in data streams. Such aggregates are based on sliding windows over data streams. In some applications, we want to monitor many sliding window sizes simultaneously and to report those windows with aggregates significantly different from other periods. We will present a general data structure for detecting interesting aggregates over such elastic windows in near linear time. We present applications of the algorithm for detecting Gamma Ray Bursts in large-scale astrophysical data. Detection of periods with high volumes of trading activities and high stock price volatility is also demonstrated using real time Trade and Quote (TAQ) data from the New York Stock Exchange (NYSE). Our algorithm beats the direct computation approach by several orders of magnitude.

References

[1]

http://www.lanl.gov/milagro/,2003.

[2]

R. Agrawal, C. Faloutsos, and A. N. Swami. Efficient Similarity Search In Sequence Databases. In D. Lomet, editor, Proceedings of the 4th International Conference of Foundations of Data Organization and Algorithms (FODO), pages 69--84, Chicago, Illinois, 1993. Springer Verlag.

Digital Library

[3]

B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and issues in data stream systems. In Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3--5, Madison, Wisconsin, USA, pages 55--68. ACM, 2002.

Digital Library

[4]

D. Carney, U. Cetintemel, M. Cherniack, C. Convey, S. Lee, G. Seidman, M. Stonebraker, N. Tatbul, and S. B. Zdonik. Monitoring streams - a new class of data management applications. In VLDB 2002, Proceedings of 28th International Conference on Very Large Data Bases, August 20--23, 2002, Hong Kong, China, 2002.

Digital Library

[5]

K. Chakrabarti, M. N. Garofalakis, R. Rastogi, and K. Shim. Approximate query processing using wavelets. In VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10--14, 2000, Cairo, Egypt, pages 111--122, 2000.

Digital Library

[6]

K.-P. Chan and A. W.-C. Fu. Efficient time series matching by wavelets. In Proceedings of the 15th International Conference on Data Engineering, Sydney, Australia, pages 126--133, 1999.

Digital Library

[7]

M. Datar, A. Gionis, P. Indyk, and R. Motwani. Maintaining stream statistics over sliding windows. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6--8, 2002, San Francisco, CA, USA. ACM/SIAM, 2002, pages 635--644, 2002.

Digital Library

[8]

R. Atkins et. al. (The Milagro Collaboration). Evidence for TeV emission from GRB 970417a. In Ap. J. Lett. 533, L119, 2000.

[9]

A. J. Smith for the Milagro Collaboration. A search for bursts of tev gamma rays with milagro. In Proceedings of the 27th International Cosmic Ray Conference (ICRC 2001), 07--15 August 2001, Hamburg, Germany, 2001.

[10]

V. Ganti, J. Gehrke, and R. Ramakrishnan. Demon: Data evolution and monitoring. In Proceedings of the 16th International Conference on Data Engineering, San Diego, California, 2000.

[11]

J. Gehrke, F. Korn, and D. Srivastava. On computing correlated aggregates over continual data streams. In Proc. ACM SIGMOD International Conf. on Management of Data, 2001.

Digital Library

[12]

A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss. Surfing wavelets on streams: One-pass summaries for approximate aggregate queries. In VLDB 2001, pages 79--88. Morgan Kaufmann, 2001.

Digital Library

[13]

G. Hulten, L. Spencer, and P. Domingos. Mining time-changing data streams. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pages 97--106. ACM Press, 2001.

Digital Library

[14]

H. V. Jagadish, N. Koudas, and S. Muthukrishnan. Mining deviants in a time series database. In M. P. Atkinson, M. E. Orlowska, P. Valduriez, S. B. Zdonik, and M. L. Brodie, editors, VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7--10, 1999, Edinburgh, Scotland, UK, pages 102--113. Morgan Kaufmann, 1999.

Digital Library

[15]

E. Keogh, S. Lonardi, and B. Y. Chiu. Finding surprising patterns in a time series database in linear time and space. In the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, July 23--26, 2002. Edmonton, Alberta, Canada, pages 550--556, 2002.

Digital Library

[16]

J. Kleinberg. Bursty and hierarchical structure in streams. In the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, July 23--26, 2002. Edmonton, Alberta, Canada, pages 91--101, 2002.

Digital Library

[17]

Y. Matias, J. S. Vitter, and M. Wang. Wavelet-based histograms for selectivity estimation. In L. M. Haas and A. Tiwary, editors, SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, June 2--4, 1998, Seattle, Washington, USA, pages 448--459, 1998.

Digital Library

[18]

H. Samet. The quadtree and related hierarchical data structures. ACM Computing Surveys, 16(2):187--260, 1984.

Digital Library

[19]

C. Shahabi, X. Tian, and W. Zhao. Tsa-tree: A wavelet-based approach to improve the efficiency of multi-level surprise and trend queries on time-series data. In 12th International Conference on Scientific and Statistical Database Management (SSDBM'00), July 26--28, 2000, Berlin, Germany, pages 55--68, 2000.

Digital Library

[20]

J. S. Vitter and M. Wang. Approximate computation of multidimensional aggregates of sparse data using wavelets. In SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, June 1--3, 1999, Philadephia, Pennsylvania, USA, pages 193--204, 1999.

Digital Library

[21]

M. Wang, T. M. Madhyastha, N. H. Chan, S. Papadimitriou, and C. Faloutsos. Data mining meets performance evaluation: Fast algorithms for modeling bursty traffic. In ICDE 2002, 18th International Conference on Data Engineering, February 26-March 1, 2002, San Jose, California, 2002.

Digital Library

[22]

Y. Zhu and D. Shasha. Statstream: Statistical monitoring of thousands of data streams in real time. In VLDB 2002, Proceedings of 28th International Conference on Very Large Data Bases, August 20--23, 2002, Hong Kong, China, pages 358--369, 2002.

Digital Library

Cited By

Bhukar KKumar HMahindru RArora RNagar SAggarwal PParadkar ARoychoudhury APaiva AAbreu RStorey MAniche MNagappan N(2024)Dynamic Alert Suppression Policy for Noise Reduction in AIOpsProceedings of the 46th International Conference on Software Engineering: Software Engineering in Practice10.1145/3639477.3639752(178-188)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3639477.3639752
Tan EYan HZhao KMa XMa ZDu Y(2024)MVOPFAD: Multiview Online Passenger Flow Anomaly DetectionIEEE Sensors Journal10.1109/JSEN.2024.337591324:9(14668-14681)Online publication date: 1-May-2024
https://doi.org/10.1109/JSEN.2024.3375913
Fushimi TSaito KMotoda H(2023)Constructing outlier-free histograms with variable bin-width based on distance minimizationIntelligent Data Analysis10.3233/IDA-21631627:1(5-29)Online publication date: 30-Jan-2023
https://doi.org/10.3233/IDA-216316
Show More Cited By

Index Terms

Efficient elastic burst detection in data streams
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

EclatDS: An efficient sliding window based frequent pattern mining method for data streams

Mining frequent patterns over data streams is an interesting problem due to its wide application area. The researchers in this field have been facing two key challenges, namely reduction in runtime and memory usage. In this study, a novel method for ...
Detecting Volatility Shift in Data Streams
ICDM '14: Proceedings of the 2014 IEEE International Conference on Data Mining

Current drift detection techniques detect a change in distribution within a stream. However, there are no current techniques that analyze the change in the rate of these detected changes. We coin the term stream volatility, to describe the rate of ...
Improved approximate detection of duplicates for data streams over sliding windows

Detecting duplicates in data streams is an important problem that has a wide range of applications. In general, precisely detecting duplicates in an unbounded data stream is not feasible in most streaming scenarios, and, on the other hand, the elements ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining

August 2003

736 pages

ISBN:1581137370

DOI:10.1145/956750

Conference Chair:
Lise Getoor
University of Maryland, College Park
,
General Chair:
Ted Senator
DARPA
,
Program Chairs:
Pedro Domingos
University of Washington
,
Christos Faloutsos
Carnegie Mellon University

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 August 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

KDD03

Sponsor:

KDD03: The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 24 - 27, 2003

Washington, D.C.

Acceptance Rates

KDD '03 Paper Acceptance Rate 46 of 298 submissions, 15%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

201
Total Citations
View Citations
2,250
Total Downloads

Downloads (Last 12 months)49
Downloads (Last 6 weeks)7

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bhukar KKumar HMahindru RArora RNagar SAggarwal PParadkar ARoychoudhury APaiva AAbreu RStorey MAniche MNagappan N(2024)Dynamic Alert Suppression Policy for Noise Reduction in AIOpsProceedings of the 46th International Conference on Software Engineering: Software Engineering in Practice10.1145/3639477.3639752(178-188)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3639477.3639752
Tan EYan HZhao KMa XMa ZDu Y(2024)MVOPFAD: Multiview Online Passenger Flow Anomaly DetectionIEEE Sensors Journal10.1109/JSEN.2024.337591324:9(14668-14681)Online publication date: 1-May-2024
https://doi.org/10.1109/JSEN.2024.3375913
Fushimi TSaito KMotoda H(2023)Constructing outlier-free histograms with variable bin-width based on distance minimizationIntelligent Data Analysis10.3233/IDA-21631627:1(5-29)Online publication date: 30-Jan-2023
https://doi.org/10.3233/IDA-216316
Zhang ZLi QDuan GZhao DXiao JXie GJiang Y(2023)Pontus: Finding Waves in Data StreamsProceedings of the ACM on Management of Data10.1145/35889601:1(1-26)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588960
DeVol NSaldaña CFu K(2023)Methods for the Automated Determination of Sustained Maximum Amplitudes in Oscillating SignalsJournal of Computing and Information Science in Engineering10.1115/1.406313024:2Online publication date: 25-Aug-2023
https://doi.org/10.1115/1.4063130
Miao RZhong ZGuo JLi ZYang TCui B(2023)BurstSketch: Finding Bursts in Data StreamsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.322368635:11(11126-11140)Online publication date: 1-Nov-2023
https://doi.org/10.1109/TKDE.2022.3223686
Zhang HFu LDing JTang FXiao YWang XChen GZhou C(2023)Maximizing the Spread of Effective Information in Social NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.313878335:4(4062-4076)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TKDE.2021.3138783
Cao RLiu XFang ZXu XWang X(2023)How do scientific papers from different journal tiers gain attention on social media?Information Processing and Management: an International Journal10.1016/j.ipm.2022.10315260:1Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.ipm.2022.103152
Shinoj TGeethu NSelvaraaj MAbraham PAthula Devi S(2023)Adaptive Threshold Peak Detection for Launch Vehicle Simulation Time Series Data AnalysisMachine Intelligence Techniques for Data Analysis and Signal Processing10.1007/978-981-99-0085-5_48(589-600)Online publication date: 31-May-2023
https://doi.org/10.1007/978-981-99-0085-5_48
Hofstätter DIlager SLujic IBrandic I(2023)SymED: Adaptive and Online Symbolic Representation of Data on the EdgeEuro-Par 2023: Parallel Processing10.1007/978-3-031-39698-4_28(411-425)Online publication date: 24-Aug-2023
https://doi.org/10.1007/978-3-031-39698-4_28
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents