High Performance Discovery In Time Series

1. Front Matter

   Pages i-xv

   PDF

2. Review of Techniques

   1. Front Matter

      Pages 1-1

      PDF

   2. Time Series Preliminaries

      • Dennis Shasha, Yunyue Zhu

      Pages 3-7

   3. Data Reduction and Transformation Techniques

      • Dennis Shasha, Yunyue Zhu

      Pages 9-71

   4. Indexing Methods

      • Dennis Shasha, Yunyue Zhu

      Pages 73-85

   5. Flexible Similarity Search

      • Dennis Shasha, Yunyue Zhu

      Pages 87-100

3. Case Studies

   1. Front Matter

      Pages 101-101

      PDF

   2. StatStream

      • Dennis Shasha, Yunyue Zhu

      Pages 103-126

   3. Query by Humming

      • Dennis Shasha, Yunyue Zhu

      Pages 127-150

   4. Elastic Burst Detection

      • Dennis Shasha, Yunyue Zhu

      Pages 151-173

   5. A Call to Exploration

      • Dennis Shasha, Yunyue Zhu

      Pages 175-175

4. Back Matter

   Pages 177-190

   PDF

Overview and Goals Data arriving in time order (a data stream) arises in fields ranging from physics to finance to medicine to music, just to name a few. Often the data comes from sensors (in physics and medicine for example) whose data rates continue to improve dramati­ cally as sensor technology improves. Further, the number of sensors is increasing, so correlating data between sensors becomes ever more critical in orderto distill knowl­ edge from the data. On-line response is desirable in many applications (e.g., to aim a telescope at a burst of activity in a galaxy or to perform magnetic resonance-based real-time surgery). These factors - data size, bursts, correlation, and fast response­ motivate this book. Our goal is to help you design fast, scalable algorithms for the analysis of single or multiple time series. Not only will you find useful techniques and systems built from simple primi­ tives, but creative readers will find many other applications of these primitives and may see how to create new ones of their own. Our goal, then, is to help research mathematicians and computer scientists find new algorithms and to help working scientists and financial mathematicians design better, faster software.

• algebra
• algorithms
• bioinformatics
• calculus
• communication
• computer
• data analysis
• database
• databases
• detection
• fast Fourier transform (FFT)
• linear algebra
• performance
• telecommunication
• wavelets
• algorithm analysis and problem complexity

From the reviews:

"The goal of the book is to show how to design fast scalable algorithms for the analysis of time series when much data must be analyzed. … A linear time filter is constructed in such a way that no burst will be missed and nearly all false positives are eliminated. … the book aims at efficient discovery in time series and presents practical algorithms for this task." (Jiri Andel, Mathematical Reviews, 2005)

 

• Courant Institute, New York, USA

  Dennis Shasha, Yunyue Zhu

Policies and ethics