PDL Abstract

Parsimonious Linear Fingerprinting for Time Series

Proceedings of the VLDB Endowment, Vol. 3, No. 1, September 2010.

Lei Li, B. Aditya Prakash, Christos Faloutsos

School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213


We study the problem of mining and summarizing multiple time series e®ectively and e±ciently. We propose PLiF, a novel method to discover essential characteristics ("fingerprints"), by exploiting the joint dynamics in numerical sequences. Our fingerprinting method has the following benefits: (a) it leads to interpretable features; (b) it is versatile: PLiF enables numerous mining tasks, including clustering, compression, visualization, forecasting, and segmentation, matching top competitors in each task; and (c) it is fast and scalable, with linear complexity on the length of the sequences.

We did experiments on both synthetic and real datasets, including human motion capture data (17MB of human motions), sensor data (166 sensors), and network router traffic data (18 million raw updates over 2 years). Despite its generality, PLiF outperforms the top clustering methods on clustering; the top compression methods on compression (3 times better reconstruction error, for the same compression ratio); it gives meaningful visualization and at the same time, enjoys a linear scale-up.