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 language | English (US) |
|---|---|
| Title of host publication | CIKM 2017 - Proceedings of the 2017 ACM Conference on Information and Knowledge Management |
| Publisher | Association for Computing Machinery |
| Pages | 617-626 |
| Number of pages | 10 |
| ISBN (Electronic) | 9781450349185 |
| DOIs | |
| State | Published - Nov 6 2017 |
| Event | 26th ACM International Conference on Information and Knowledge Management, CIKM 2017 - Singapore, Singapore Duration: Nov 6 2017 → Nov 10 2017 |
Publication series
| Name | International Conference on Information and Knowledge Management, Proceedings |
|---|---|
| Volume | Part F131841 |
Other
| Other | 26th ACM International Conference on Information and Knowledge Management, CIKM 2017 |
|---|---|
| Country | Singapore |
| City | Singapore |
| Period | 11/6/17 → 11/10/17 |
Fingerprint
ASJC Scopus subject areas
- Business, Management and Accounting(all)
- Decision Sciences(all)
Cite this
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 proceeding › Conference contribution
}
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 -