SliceNStitch: Continuous CP Decomposition of Sparse Tensor Streams

Consider traffic data (i.e., triplets in the form of source-destination-timestamp) that grow over time. Tensors (i.e., multi-dimensional arrays) with a time mode are widely used for modeling and analyzing such multi-aspect data streams. In such tensors, however, new entries are added only once per period, which is often an hour, a day, or even a year. This discreteness of tensors has limited their usage for real-time applications, where new data should be analyzed instantly as it arrives.

How can we analyze time-evolving multi-aspect sparse data 'continuously' using tensors where time is 'discrete'? We propose SLICENSTITCH for continuous CANDECOMP/PARAFAC (CP) decomposition, which has numerous time-critical applications, including anomaly detection, recommender systems, and stock market prediction. SLICENSTITCH changes the starting point of each period adaptively, based on the current time, and updates factor matrices (i.e., outputs of CP decomposition) instantly as new data arrives. We show, theoretically and experimentally, that SLICENSTITCH is (1) 'Any time': updating factor matrices immediately without having to wait until the current time period ends, (2) Fast: with constant-time updates up to 464× faster than online methods, and (3) Accurate: with fitness comparable (specifically, 72 -100%) to offline methods.

in the tensor in Fig. 1a, each slice represents the amounts of traffic for one hour, and thus the tensor grows with a new slice only once per hour. That is, it may take one hour for new traffic to be applied to the tensor. For instance, traffic occurring at 2:00:01 is applied to the tensor at 3:00:00. Due to this discreteness, the outputs of CPD (i.e., factor matrices) are updated also only once per period even if incremental algorithms [15]-[17] are used.

How can we perform CPD 'continuously' for real-time applications? A potential solution is to make the granularity of the time mode extremely fine. According to our preliminary studies, however, it causes the following problems:

• Degradation of Fitness (Fig. 1c) An extremely fine-grained