Fast window correlations over uncooperative time series

Richard Cole, Dennis Shasha, Xiaojian Zhao

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

Abstract

Data arriving in time order (a data stream) arises in fields including physics, finance, medicine, and music, to name a few. Often the data comes from sensors (in physics and medicine for example) whose data rates continue to improve dramatically as sensor technology improves. Further, the number of sensors is increasing, so correlating data between sensors becomes ever more critical in order to distill knowlege from the data. In many applications such as finance, recent correlations are of far more interest than long-term correlation, so correlation over sliding windows (windowed correlation) is the desired operation. Fast response is desirable in many applications (e.g., to aim a telescope at an activity of interest or to perform a stock trade). These three factors - data size, windowed correlation, and fast response - motivate this work. Previous work [10, 14] showed how to compute Pearson correlation using Fast Fourier Transforms and Wavelet transforms, but such techniques don't work for time series in which the energy is spread over many frequency components, thus resembling white noise. For such "uncooperative" time series, this paper shows how to combine several simple techniques - sketches (random projections), convolution, structured random vectors, grid structures, and combinatorial design - to achieve high performance windowed Pearson correlation over a variety of data sets.

Original languageEnglish (US)
Title of host publicationKDD-2005 - Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
EditorsR.L. Grossman, R. Bayardo, K. Bennett, J. Vaidya
Pages743-749
Number of pages7
DOIs
StatePublished - 2005
EventKDD-2005: 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - Chicago, IL, United States
Duration: Aug 21 2005Aug 24 2005

Other

OtherKDD-2005: 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
CountryUnited States
CityChicago, IL
Period8/21/058/24/05

Keywords

  • Correlation
  • Randomized algorithms
  • Time series

ASJC Scopus subject areas

  • Information Systems

Fingerprint Dive into the research topics of 'Fast window correlations over uncooperative time series'. Together they form a unique fingerprint.

Cite this