Tensors with a time mode are widely used for modeling and analyzing multi-aspect data streams that grow over time. However, the main drawback of such tensors is that they can be updated only once per period, which is often a day or even a year, even if the new data arrive in real-time. This discreteness of tensors has limited their usage for real-time applications with the sparse data streams, where new data have to be immediately analyzed as they arrive.
How can we analyze time-evolving multi-aspect sparse data 'continuously' using 'discrete-time' tensors? In this work, we propose SliceNStitch for the continuous tensor model and its CANDECOMP/PARAFAC (CP) decomposition, which has numerous time-critical applications, including anomaly detection and recommender systems. SliceNStitch changes the starting point of each period adaptively based on the current time and updates outputs of CP decomposition instantly as new data arrives. We show, theoretically and experimentally, that SliceNStitch is (1) Any time: updating outputs of CP decomposition immediately without having to wait until the current 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.
시간 축을 가진 텐서는 시간이 지남에 따라 증가하는 다차원 데이터 스트림을 모델링하고 분석하는 데 널리 사용되고 있다. 그렇지만 이러한 텐서는 새로운 데이터가 실시간으로 도착하더라도 하루, 혹은 일 년에 한 번씩 정해진 주기대로만 업데이트할 수 있다는 문제점이 있다. 이와 같은 텐서의 불연속성은 새로운 데이터가 도착하는 즉시 분석되어야 하는 희소 데이터 스트림 기반 실시간 애플리케이션에 텐서를 적용하기 어렵게 만드는 주된 요인 중 하나이다.
어떻게 하면 시간에 따라 변화하는 다차원 희소 데이터를 '이산 시간' 텐서를 사용하여 '연속적'으로 분석할 수 있는가? CANDECOMP/PARAFAC (CP) 분해는 이상치 탐지나 추천 시스템 등 시간에 민감한 다양한 작업에 널리 활용되고 있으므로, 본 논문에서는 연속적인 텐서 모델과 이에 관한 CP 분해를 위한 SliceNStitch를 제안하였다. SliceNStitch는 새로운 데이터를 받으면 즉시 현재 시각을 기준으로 각 기간의 시작점을 조정하고 CP 분해의 결과물을 갱신한다. 본 논문은 SliceNStitch가 이론적 및 실험적으로 (1) 즉각성: CP 분해의 결과물을 기다림 없이 바로 수정할 수 있고, (2) 신속성: 다른 실시간 알고리즘보다 최대 464배 빠른 상수 시간 업데이트가 가능하며, (3) 정확성: 비실시간 알고리즘과 비교해 72-100%의 정확도를 갖는 것을 입증하였다.
