Home

Paper abstract

Two heads better than one: Pattern Discovery in Time-evolving Multi-Aspect Data

Jimeng Sun - IBM, TJ Watson Research Center, USA
Tina Eliassi-Rad - Lawrence Livermore National Laboratory, USA
Charalampos E. Tsourakakis - CMU, USA
Evan Hoke - CMU, USA
Christos Faloutsos - CMU, USA

Session: Mining Sequences and Streams
Springer Link: http://dx.doi.org/10.1007/978-3-540-87479-9_19

Data stream values are often associated with multiple aspects. For example, each value observed at a given time-stamp from environmental sensors may have an associated type (e.g., temperature, humidity, etc) as well as location. Timestamp,type and location are the three aspects, which can be modeled using a tensor (high-order array). However, the time aspect is special, with a natural ordering, and with successive time-ticks having usually correlated values. Standard multiway analysis ignores this structure. To capture it, we propose 2 Heads Tensor Analysis (2-heads), which provides a qualitatively different treatmenton time. Unlike most existing approaches that use a PCA-like summarization scheme for all aspects, 2-heads treats the time aspect carefully. 2-heads combines the power of classic multilinear analysis (PARAFAC [1], Tucker [5],DTA/STA [3], WTA [2]) with wavelets, leading to a powerful mining tool. Furthermore, 2-heads has several other advantages as well: (a) it can be computed incrementally in a streaming fashion, (b) it has a provable error guarantee and, (c) it achieves significant compression ratio against competitors. Finally, we show experiments on real datasets, and we illustrate how 2-heads reveals interesting trends in the data.