Periodicity detection in time series databases
- 23 May 2005
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 17 (7), 875-887
- https://doi.org/10.1109/tkde.2005.114
Abstract
Periodicity mining is used for predicting trends in time series data. Discovering the rate at which the time series is periodic has always been an obstacle for fully automated periodicity mining. Existing periodicity mining algorithms assume that the periodicity, rate (or simply the period) is user-specified. This assumption is a considerable limitation, especially in time series data where the period is not known a priori. In this paper, we address the problem of detecting the periodicity rate of a time series database. Two types of periodicities are defined, and a scalable, computationally efficient algorithm is proposed for each type. The algorithms perform in O(n log n) time for a time series of length n. Moreover, the proposed algorithms are extended in order to discover the periodic patterns of unknown periods at the same time without affecting the time complexity. Experimental results show that the proposed algorithms are highly accurate with respect to the discovered periodicity rates and periodic patterns. Real-data experiments demonstrate the practicality of the discovered periodic patterns.Keywords
This publication has 12 references indexed in Scilit:
- Incremental, online, and merge mining of partial periodic patterns in time-series databasesIEEE Transactions on Knowledge and Data Engineering, 2004
- SEGMENTING TIME SERIES: A SURVEY AND NOVEL APPROACHPublished by World Scientific Pub Co Pte Ltd ,2004
- A review of symbolic analysis of experimental dataReview of Scientific Instruments, 2003
- Mining sequential patternsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Sequential PAttern mining using a bitmap representationPublished by Association for Computing Machinery (ACM) ,2002
- Finding surprising patterns in a time series database in linear time and spacePublished by Association for Computing Machinery (ACM) ,2002
- A Randomized Algorithm for Approximate String MatchingAlgorithmica, 2001
- Mining asynchronous periodic patterns in time series dataPublished by Association for Computing Machinery (ACM) ,2000
- Discovering frequent event patterns with multiple granularities in time sequencesIEEE Transactions on Knowledge and Data Engineering, 1998
- Generalized String MatchingSIAM Journal on Computing, 1987