skip to main content
10.1145/2504335.2504370acmotherconferencesArticle/Chapter ViewAbstractPublication PagespetraConference Proceedingsconference-collections
research-article

Multiresolution similarity search in time series data: an application to EEG signals

Published: 29 May 2013 Publication History

Abstract

Time series constitute a prevalent data type that arise in several diverse disciplines (e.g., biomedical data, sensor data, images, video data), and therefore analyzing time series is a significant task with a plethora of important applications. In this paper, we study the general problem of similarity search in time series databases and we propose a novel multiresolution indexing (i.e., representation) and retrieval method for time series similarity search. Our approach is motivated by the idea that if we examine a time series at different resolution levels, we could possibly acquire further insights about the data. The proposed algorithm adopts a combined, two-step pruning (filtering) strategy to further reduce data dimensionality by discarding irrelevant time series (i.e., false alarms). At a first level, the time series are represented by line segments and filtered by the triangular inequality property. Then, a Vector Quantization like scheme is applied to encode data and thus to reduce dimensionality.
We test and demonstrate the performance of the proposed method, analyzing EEG time series data for retrieval of one of the constituent brain waveforms in EEG recordings, the K-complex, but the method can as well be applied for retrieval of other patterns of interest in time series analysis. The automatic detection and categorization of the EEG patterns will allow the advanced correlation analysis of large amounts of data and will lead to advanced decision making capabilities assisting diagnosis by medical professionals.

References

[1]
R. Agrawal, C. Faloutsos, and A. N. Swami. Efficient similarity search in sequence databases. In FODO, pages 69--84, 1993.
[2]
V. Athitsos, P. Papapetrou, M. Potamias, G. Kollios, and D. Gunopulos. Approximate embedding-based subsequence matching of time series. In SIGMOD, pages 365--378, 2008.
[3]
S. Cash, E. Halgren, N. Dehghani, and et al. Human K-Complex Represents an Isolated Cortical Down-State. Science, 324:1084--87, 2005.
[4]
K.-P. Chan and A. W.-C. Fu. Efficient time series matching by wavelets. In ICDE, pages 126--133, 1999.
[5]
H. Ding, G. Trajcevski, P. Scheuermann, X. Wang, and E. Keogh. Querying and mining of time series data: experimental comparison of representations and distance measures. Proc. VLDB Endow., 1(2):1542--1552, 2008.
[6]
C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. Fast subsequence matching in time-series databases. In SIGMOD, pages 419--429, 1994.
[7]
A. Gersho and R. M. Gray. Vector quantization and signal compression. Kluwer Academic Publishers, Norwell, MA, USA, 1991.
[8]
P. Halász. K-complex, a reactive EEG graphoelement of NREM sleep: an old chap in a new garment. Sleep Med Rev., 9(5):391--412, 2005.
[9]
E. Keogh and C. A. Ratanamahatana. Exact indexing of dynamic time warping. Knowledge and Information Systems, 7:358--386, 2005.
[10]
V. Kokkinos and G. Kostopoulos. Human non-rapid eye movement stage II sleep spindles are blocked upon spontaneous K-complex coincidence and resume as higher frequency spindles afterwards. J Sleep Res., 20(1 Pt 1):57--72, 2011.
[11]
V. Kokkinos, A. Koupparis, M. Stavrinou, and G. Kostopoulos. The hypnospectrogram: An eeg power spectrum based means to concurrently overview the macroscopic and microscopic architecture of human sleep. Journal of Neuroscience Methods, 185(1):29--38, 2009.
[12]
G. Kostopoulos. Brain mechanisms linking epilepsy to sleep. Encyclopedia of Basic Epilepsy Research, 7:1327--1336, 2009.
[13]
A. Kotsifakos, P. Papapetrou, J. Hollmén, D. Gunopulos, and V. Athitsos. A survey of query-by-humming similarity methods. In PETRA, pages 5:1--5:4, 2012.
[14]
J. Lin, E. Keogh, L. Wei, and S. Lonardi. Experiencing sax: a novel symbolic representation of time series. Data Min. Knowl. Discov., 15(2):107--144, 2007.
[15]
V. Megalooikonomou, G. Li, and Q. Wang. A dimensionality reduction technique for efficient similarity analysis of time series databases. In CIKM, pages 160--161, 2004.
[16]
M. M. Muhammad Fuad and P.-F. Marteau. Multi-resolution approach to time series retrieval. In IDEAS, pages 136--142, 2010.
[17]
A. Rechtschaffen and A. Kales. A manual of standardised terminology and scoring system for sleep stages in human subjects. U.S. Government Printing Office, Washinghton, DC, 1968.
[18]
Q. Wang and V. Megalooikonomou. A dimensionality reduction technique for efficient time series similarity analysis. Inf. Syst., 33(1):115--132, 2008.
[19]
Q. Wang, V. Megalooikonomou, and C. Faloutsos. Time series analysis with multiple resolutions. Inf. Syst., 35(1):56--74, 2010.

Index Terms

  1. Multiresolution similarity search in time series data: an application to EEG signals

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Other conferences
      PETRA '13: Proceedings of the 6th International Conference on PErvasive Technologies Related to Assistive Environments
      May 2013
      413 pages
      ISBN:9781450319737
      DOI:10.1145/2504335
      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

      • NSF: National Science Foundation
      • FORTH: Foundation for Research and Technology - Hellas
      • HERACLEIA: HERACLEIA Human-Centered Computing Laboratory at UTA
      • U of Tex at Arlington: U of Tex at Arlington
      • TEI: Technological Educational Institution of Athens
      • UCG: University of Central Greece
      • NCRS: Demokritos National Center for Scientific Research
      • Fulbrigh, Greece: Fulbright Foundation, Greece
      • Ionian: Ionian University, GREECE

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 29 May 2013

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. EEG signals
      2. assistive environments
      3. similarity search
      4. time series

      Qualifiers

      • Research-article

      Funding Sources

      Conference

      PETRA '13
      Sponsor:
      • NSF
      • FORTH
      • HERACLEIA
      • U of Tex at Arlington
      • TEI
      • UCG
      • NCRS
      • Fulbrigh, Greece
      • Ionian

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • 0
        Total Citations
      • 124
        Total Downloads
      • Downloads (Last 12 months)6
      • Downloads (Last 6 weeks)2
      Reflects downloads up to 17 Jan 2025

      Other Metrics

      Citations

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media