research-article

Boolean representation based data-adaptive correlation analysis over time series streams

Authors:

Tiancheng Zhang,

Ge YuAuthors Info & Claims

CIKM '07: Proceedings of the sixteenth ACM conference on Conference on information and knowledge management

Pages 203 - 212

https://doi.org/10.1145/1321440.1321471

Published: 06 November 2007 Publication History

Abstract

Correlation analysis is a basic problem in the field of data stream mining. Typical approaches add sliding window to data streams to get the recent results, but the window length defined by users is always fixed which is not suitable for the changing stream environment. We propose a Boolean representation based data-adaptive method for correlation analysis among a large number of time series streams. The periodical trends of each stream series to are monitored to choose the most suitable window size and group the series with the same trends together. Instead of adopting complex pair-wise calculation, we can also quickly get the correlation pairs of series at the optimal window sizes. All the processing is realized by simple Boolean operations. Both the theory analysis and the experimental evaluations show that our method has good computation efficiency with high accuracy.

References

[1]

R. Agrawal, C. Faloutsos, A. Swami. Efficient similarity search in sequences database. Proc. of FODO, Chicago, USA, 1993.

Digital Library

[2]

C. Faloutsos, M. Ranganathan, Y. Mandoponlos. Fast subsequence matching in time-series databases. Proc. of ACM SIGMOD Conf, Mineapolis, USA, 1994.

Digital Library

[3]

E. J. Keogh, K. Chakrabarti, S. Mehrotra, and M. J. Pazzani. Locally adaptive dimensionality reduction for indexing large time series databases. Proc. of ACM SIGMOD, Santa Barbara, California, USA, 2001.

Digital Library

[4]

V. Megalooikonomou, G. Li, Q. Wang. A dimensionality reduction technique for efficient similarity analysis of time series databases. Proc. of ACM CIKM, Washington DC, USA, 2004.

Digital Library

[5]

K. P. Chan, A. W. C. Fu. Efficient time series matching by wavelets. Proc. of ICDE, Sydney, Australia, 1999.

Digital Library

[6]

M. J. Hsieh, M. S. Chen, P. S. Yu. Integrating DCT and DWT for approximating cube streams. Proc. of CIKM, Bremen, Germany, 2005.

Digital Library

[7]

A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss. Surfing wavelets on streams: One-pass summaries for approximate aggregate queries. Proc. of VLDB, Roma, Italy, 2001.

Digital Library

[8]

S. Guha, C. Kim, and K. Shim. Xwave: optimal and approximate extended wavelets for streaming data. Proc. of VLDB, Toronto, Canada, 2004.

Digital Library

[9]

F. Korn, H. Jagadish, C. Faloutsos. Efficiently supporting ad hoc queries in large datasets of time sequences. Proc. of ACM SIGMOD, Tucson, Arizona, USA, 1997.

Digital Library

[10]

A. Dobra, M. N. Garofalakis, J. Gehrke, and R. Rastogi. Processing complex aggregate queries over data streams. Proc. of ACM SIGMOD, Madison, Wisconsin, USA, 2002.

Digital Library

[11]

C. Ratanamahatana, E. Keogh, A. Bagnall, S. Lonardi. A novel bit level time series representation with implication for similarity search and clustering. Proc. of PAKDD, Hanoi, Vietnam, 2005.

Digital Library

[12]

S. Guha, A. Meyerson, N. Mishra, R. Motwani, and L. O'Callaghan. Clustering data streams: Theory and practice. IEEE TKDE, 15(3):515--528, 2003.

Digital Library

[13]

P. Domingos and G. hulten. Mining high speed data streams. Proc. of KDD, Boston, Massachusetts, USA, 2000.

Digital Library

[14]

H. Wang, W. Fan, P. S. Yu and J. Han. Mining concept-drifting data streams using ensemble classifiers. Proc. of ACM SIGKDD, Washington DC, USA, 2003.

Digital Library

[15]

C. C. Aggarwal, J. Han, and P. S. Yu. A framework for clustering evolving data streams. Proc. of VLDB, Berlin, Germany, 2003.

Digital Library

[16]

Y. Zhu, D. Shasha. StatStream: Statistical monitoring of thousands of data streams in real time. Proc. of VLDB, Hong Kong, 2002.

Digital Library

[17]

Y. Sakurai, S.Panadimitriou, J. Sun, C. Faloutsos. Braid: Stream mining through group lag correlations. Proc. of ACM SIGMOD, Baltimore, Maryland, 2005.

Digital Library

[18]

S. Guha, D. Gunopulos, N. Koudas. Correlating synchronous and asynchronous data streams. Proc. of KDD, Washington DC, USA, 2003.

Digital Library

[19]

B. K. Yi, N. Sidiropouls, T. Johnson, H. Jagadish, C. Faloutsos, and A. Biliris. Online data mining for co-evolving time sequences. Proc. of ICDE, San Diego, California, USA, 2000.

Digital Library

[20]

S. Papadimitriou, J. Sun, C. Faloutsos. Stream pattern discovery in multiple time series. Proc. of VLDB, Trondheim, Norway, 2005.

Digital Library

[21]

S. Papadimitriou, P. S. Yu. Optimal multi-scale patterns in time series streams. Proc. of ACM SIGMOD, Chicago, Illinois, USA, 2006.

Digital Library

[22]

T. Ide and K. Inoue. Knowledge discovery from heterogeneous dynamic systems using change-point correlations. Proc. of SDM, Trondheim, Norway, 2005.

[23]

D. D. Muresan and T. W. Parks. Adaptive principal components and image diagnosing. Proc. of ICIP, Barcelona, Spain, 2003.

[24]

M. G. Elefky, W. G. Aref, and A. K. Elmagarmid. Using convolution to mine obscure periodic pattern in one pass. Proc. of EDBT, Heraklion, Greece, 2004.

Cited By

Wang ZHe ZWang PWang YWang W(2024)Static and Streaming Discovery of Maximal Linear Representation Between Time SeriesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.328727336:1(401-415)Online publication date: Jan-2024
https://doi.org/10.1109/TKDE.2023.3287273
Fu T(2018)A review on time series data miningEngineering Applications of Artificial Intelligence10.1016/j.engappai.2010.09.00724:1(164-181)Online publication date: 27-Dec-2018
https://dl.acm.org/doi/10.1016/j.engappai.2010.09.007
Guo TSathe SAberer KBailey JMoffat AAggarwal Cde Rijke MKumar RMurdock VSellis TYu J(2015)Fast Distributed Correlation Discovery Over Streaming Time-Series DataProceedings of the 24th ACM International on Conference on Information and Knowledge Management10.1145/2806416.2806440(1161-1170)Online publication date: 17-Oct-2015
https://dl.acm.org/doi/10.1145/2806416.2806440
Show More Cited By

Index Terms

Boolean representation based data-adaptive correlation analysis over time series streams
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Adaptive correlation analysis in stream time series with sliding windows

Correlation analysis is a very useful technique for similarity search in the field of data stream mining. The traditional method is not suitable for real time processing especially when the amount of stream sequences is very large. In this paper, we ...
Correlation Analysis Based on Hierarchical Boolean Representation over Time Series Data Streams
FSKD '07: Proceedings of the Fourth International Conference on Fuzzy Systems and Knowledge Discovery - Volume 02

Correlation analysis is a basic problem in the field of data stream mining. Traditional method is not suitable for real time processing with huge amount of stream data. We propose a hierarchical Boolean representation method for correlation analysis ...
Time-slide window join over data streams

The join is an important operator in processing data streams. To produce outputs continuously over unbounded data streams, sliding windows are generally used to limit the scope of the join at a certain time. In the existing join algorithms, only a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '07: Proceedings of the sixteenth ACM conference on Conference on information and knowledge management

November 2007

1048 pages

ISBN:9781595938039

DOI:10.1145/1321440

Co-chair:
Alberto H. F. Laender,
Conference Chairs:
André O. Falcão
Universidade de Lisboa, Portugal
,
Øystein Haug Olsen,
General Chair:
Mário J. Silva
(Universidade de Lisboa, Portugal)
,
Program Chairs:
Ricardo Baeza-Yates,
Deborah L. McGuinness,
Bjorn Olstad

Copyright © 2007 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: 06 November 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CIKM07

Sponsor:

CIKM07: Conference on Information and Knowledge Management

November 6 - 10, 2007

Lisbon, Portugal

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
453
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang ZHe ZWang PWang YWang W(2024)Static and Streaming Discovery of Maximal Linear Representation Between Time SeriesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.328727336:1(401-415)Online publication date: Jan-2024
https://doi.org/10.1109/TKDE.2023.3287273
Fu T(2018)A review on time series data miningEngineering Applications of Artificial Intelligence10.1016/j.engappai.2010.09.00724:1(164-181)Online publication date: 27-Dec-2018
https://dl.acm.org/doi/10.1016/j.engappai.2010.09.007
Guo TSathe SAberer KBailey JMoffat AAggarwal Cde Rijke MKumar RMurdock VSellis TYu J(2015)Fast Distributed Correlation Discovery Over Streaming Time-Series DataProceedings of the 24th ACM International on Conference on Information and Knowledge Management10.1145/2806416.2806440(1161-1170)Online publication date: 17-Oct-2015
https://dl.acm.org/doi/10.1145/2806416.2806440
Kurasawa HSato HNakamura MMatsumura H(2012)Online Top-k Similar Time-Lagged Pattern Pair Search in Multiple Time SeriesDatabase and Expert Systems Applications10.1007/978-3-642-32597-7_38(432-441)Online publication date: 2012
https://doi.org/10.1007/978-3-642-32597-7_38
Kotov AZhai CSproat RKing INejdl WLi H(2011)Mining named entities with temporally correlated bursts from multilingual web news streamsProceedings of the fourth ACM international conference on Web search and data mining10.1145/1935826.1935870(237-246)Online publication date: 9-Feb-2011
https://dl.acm.org/doi/10.1145/1935826.1935870

View Options

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