Detecting multiple periods and periodic patterns in event time sequences

Quan Yuan, Jingbo Shang, Xin Cao, Chao Zhang, Xinhe Geng, Jiawei Han

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

Abstract

Periodicity is prevalent in physical world, and many events involve more than one periods, e.g., individual's mobility, tide paern, and massive transportation utilization. Knowing the true periods of events can benefit a number of applications, such as traffic prediction, time-aware recommendation and advertisement, and anomaly detection. However, detecting multiple periods is a very challenging task due to not only the interwoven periodic patterns but also the low quality of event tracking records. In this paper, we study the problem of discovering all true periods and the corresponded occurring patterns of an event from a noisy and incomplete observation sequence. We devise a novel scoring function, by maximizing which we can identify the true periodic patterns involved in the sequence. We prove that, however, optimizing the objective function is an NP-hard problem. To address this challenge, we develop a heuristic algorithm named Timeslot Coverage Model (TiCom), for identifying the periods and periodic patterns approximately. The results of extensive experiments on both synthetic and reallife datasets show that our model outperforms the state-of-the-art baselines significantly in various tasks, including period detection, periodic pattern identification, and anomaly detection.

Original languageEnglish (US)
Title of host publicationCIKM 2017 - Proceedings of the 2017 ACM Conference on Information and Knowledge Management
PublisherAssociation for Computing Machinery
Pages617-626
Number of pages10
ISBN (Electronic)9781450349185
DOIs
StatePublished - Nov 6 2017
Event26th ACM International Conference on Information and Knowledge Management, CIKM 2017 - Singapore, Singapore
Duration: Nov 6 2017Nov 10 2017

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings
VolumePart F131841

Other

Other26th ACM International Conference on Information and Knowledge Management, CIKM 2017
CountrySingapore
CitySingapore
Period11/6/1711/10/17

Fingerprint

Anomaly detection
Experiment
Heuristic algorithm
NP-hard
Periodicity
Objective function
Scoring
Prediction

ASJC Scopus subject areas

  • Business, Management and Accounting(all)
  • Decision Sciences(all)

Cite this

Yuan, Q., Shang, J., Cao, X., Zhang, C., Geng, X., & Han, J. (2017). Detecting multiple periods and periodic patterns in event time sequences. In CIKM 2017 - Proceedings of the 2017 ACM Conference on Information and Knowledge Management (pp. 617-626). (International Conference on Information and Knowledge Management, Proceedings; Vol. Part F131841). Association for Computing Machinery. https://doi.org/10.1145/3132847.3133027

Detecting multiple periods and periodic patterns in event time sequences. / Yuan, Quan; Shang, Jingbo; Cao, Xin; Zhang, Chao; Geng, Xinhe; Han, Jiawei.

CIKM 2017 - Proceedings of the 2017 ACM Conference on Information and Knowledge Management. Association for Computing Machinery, 2017. p. 617-626 (International Conference on Information and Knowledge Management, Proceedings; Vol. Part F131841).

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

Yuan, Q, Shang, J, Cao, X, Zhang, C, Geng, X & Han, J 2017, Detecting multiple periods and periodic patterns in event time sequences. in CIKM 2017 - Proceedings of the 2017 ACM Conference on Information and Knowledge Management. International Conference on Information and Knowledge Management, Proceedings, vol. Part F131841, Association for Computing Machinery, pp. 617-626, 26th ACM International Conference on Information and Knowledge Management, CIKM 2017, Singapore, Singapore, 11/6/17. https://doi.org/10.1145/3132847.3133027
Yuan Q, Shang J, Cao X, Zhang C, Geng X, Han J. Detecting multiple periods and periodic patterns in event time sequences. In CIKM 2017 - Proceedings of the 2017 ACM Conference on Information and Knowledge Management. Association for Computing Machinery. 2017. p. 617-626. (International Conference on Information and Knowledge Management, Proceedings). https://doi.org/10.1145/3132847.3133027
Yuan, Quan ; Shang, Jingbo ; Cao, Xin ; Zhang, Chao ; Geng, Xinhe ; Han, Jiawei. / Detecting multiple periods and periodic patterns in event time sequences. CIKM 2017 - Proceedings of the 2017 ACM Conference on Information and Knowledge Management. Association for Computing Machinery, 2017. pp. 617-626 (International Conference on Information and Knowledge Management, Proceedings).
@inproceedings{831163a678c54c16ad1d198e994a8442,
title = "Detecting multiple periods and periodic patterns in event time sequences",
abstract = "Periodicity is prevalent in physical world, and many events involve more than one periods, e.g., individual's mobility, tide paern, and massive transportation utilization. Knowing the true periods of events can benefit a number of applications, such as traffic prediction, time-aware recommendation and advertisement, and anomaly detection. However, detecting multiple periods is a very challenging task due to not only the interwoven periodic patterns but also the low quality of event tracking records. In this paper, we study the problem of discovering all true periods and the corresponded occurring patterns of an event from a noisy and incomplete observation sequence. We devise a novel scoring function, by maximizing which we can identify the true periodic patterns involved in the sequence. We prove that, however, optimizing the objective function is an NP-hard problem. To address this challenge, we develop a heuristic algorithm named Timeslot Coverage Model (TiCom), for identifying the periods and periodic patterns approximately. The results of extensive experiments on both synthetic and reallife datasets show that our model outperforms the state-of-the-art baselines significantly in various tasks, including period detection, periodic pattern identification, and anomaly detection.",
author = "Quan Yuan and Jingbo Shang and Xin Cao and Chao Zhang and Xinhe Geng and Jiawei Han",
year = "2017",
month = "11",
day = "6",
doi = "10.1145/3132847.3133027",
language = "English (US)",
series = "International Conference on Information and Knowledge Management, Proceedings",
publisher = "Association for Computing Machinery",
pages = "617--626",
booktitle = "CIKM 2017 - Proceedings of the 2017 ACM Conference on Information and Knowledge Management",

}

TY - GEN

T1 - Detecting multiple periods and periodic patterns in event time sequences

AU - Yuan, Quan

AU - Shang, Jingbo

AU - Cao, Xin

AU - Zhang, Chao

AU - Geng, Xinhe

AU - Han, Jiawei

PY - 2017/11/6

Y1 - 2017/11/6

N2 - Periodicity is prevalent in physical world, and many events involve more than one periods, e.g., individual's mobility, tide paern, and massive transportation utilization. Knowing the true periods of events can benefit a number of applications, such as traffic prediction, time-aware recommendation and advertisement, and anomaly detection. However, detecting multiple periods is a very challenging task due to not only the interwoven periodic patterns but also the low quality of event tracking records. In this paper, we study the problem of discovering all true periods and the corresponded occurring patterns of an event from a noisy and incomplete observation sequence. We devise a novel scoring function, by maximizing which we can identify the true periodic patterns involved in the sequence. We prove that, however, optimizing the objective function is an NP-hard problem. To address this challenge, we develop a heuristic algorithm named Timeslot Coverage Model (TiCom), for identifying the periods and periodic patterns approximately. The results of extensive experiments on both synthetic and reallife datasets show that our model outperforms the state-of-the-art baselines significantly in various tasks, including period detection, periodic pattern identification, and anomaly detection.

AB - Periodicity is prevalent in physical world, and many events involve more than one periods, e.g., individual's mobility, tide paern, and massive transportation utilization. Knowing the true periods of events can benefit a number of applications, such as traffic prediction, time-aware recommendation and advertisement, and anomaly detection. However, detecting multiple periods is a very challenging task due to not only the interwoven periodic patterns but also the low quality of event tracking records. In this paper, we study the problem of discovering all true periods and the corresponded occurring patterns of an event from a noisy and incomplete observation sequence. We devise a novel scoring function, by maximizing which we can identify the true periodic patterns involved in the sequence. We prove that, however, optimizing the objective function is an NP-hard problem. To address this challenge, we develop a heuristic algorithm named Timeslot Coverage Model (TiCom), for identifying the periods and periodic patterns approximately. The results of extensive experiments on both synthetic and reallife datasets show that our model outperforms the state-of-the-art baselines significantly in various tasks, including period detection, periodic pattern identification, and anomaly detection.

UR - http://www.scopus.com/inward/record.url?scp=85037333803&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85037333803&partnerID=8YFLogxK

U2 - 10.1145/3132847.3133027

DO - 10.1145/3132847.3133027

M3 - Conference contribution

AN - SCOPUS:85037333803

T3 - International Conference on Information and Knowledge Management, Proceedings

SP - 617

EP - 626

BT - CIKM 2017 - Proceedings of the 2017 ACM Conference on Information and Knowledge Management

PB - Association for Computing Machinery

ER -