Spatio-Temporal Tensor Sketching via Adaptive Sampling

Abstract

Mining massive spatio-temporal data can help a variety of real-world applications such as city capacity planning, event management, and social network analysis. The tensor representation can be used to capture the correlation between space and time and simultaneously exploit the latent structure of the spatial and temporal patterns in an unsupervised fashion. However, the increasing volume of spatio-temporal data has made it prohibitively expensive to store and analyze using tensor factorization. In this paper, we propose SkeTenSmooth, a novel tensor factorization framework that uses adaptive sampling to compress the tensor in a temporally streaming fashion and preserves the underlying global structure. SkeTenSmooth adaptively samples incoming tensor slices according to the detected data dynamics. Thus, the sketches are more representative and informative of the tensor dynamic patterns. In addition, we propose a robust tensor factorization method that can deal with the sketched tensor and recover the original patterns. Experiments on the New York City Yellow Taxi data show that SkeTenSmooth greatly reduces the memory cost and outperforms random sampling and fixed rate sampling method in terms of retaining the underlying patterns.

References in corpus (8)

• Convolutional LSTM Network: A Machine Learning Approach for Precipitation Nowcasting
• Scalable Tensor Factorizations for Incomplete Data
• Bayesian CP Factorization of Incomplete Tensors with Automatic Rank Determination
• Smooth PARAFAC Decomposition for Tensor Completion
• Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach
• A New Sampling Technique for Tensors
• A New Low-Rank Tensor Model for Video Completion
• Tensor sparsification via a bound on the spectral norm of random tensors