Fast and Memory-Efficient Tucker decomposition for Answering Diverse Time Range Queries


Given a temporal dense tensor, how can we efficiently find latent patterns in an arbitrary time range? Tucker decomposition is a fundamental tool for analyzing dense tensors to discover hidden factors, and has been exploited in many data mining applications. However, existing decomposition methods do not provide the functionality to analyze a specific range of a temporal tensor. The existing methods are one-off, with focus on performing Tucker decomposition once for a whole input tensor. Although a few existing methods with a preprocessing phase can deal with a time range query, they are still time-consuming and suffer from low accuracy.

In this paper, we propose Zoom-Tucker, a novel Tucker decomposition method to find latent factors in an arbitrary time range. Zoom-Tucker allows us to efficiently deal with various time range queries. Zoom-Tucker fully exploits block structure to compress a given tensor, supporting an efficient query and capturing local information. Zoom-Tucker answers diverse time range queries quickly and memory-efficiently, by elaborately decoupling the preprocessed results included in the range and carefully determining the order of computations. We demonstrate that Zoom-Tucker is up to 171.9x faster and requires up to 230x less space than existing methods while providing comparable accuracy.


Zoom-Tucker is described in the following paper:



Boats320 x 240 x 7000
(height x width x time)
Video ChangeDetection.NET Link
Walking Video1080 x 1980 x 2400
(height x width x time)
Video Tucker-TensorSketch Link
Korea Stock3028 x 54 x 3050
(stock x feature x date)
Time series Korea Stocks Link
Traffic1084 x 96 x 2000
(sensor x frequency x time)
Traffic volume VicRoads dataset Link
FMA7994 x 1025 x 700
(song x frequency x time)
Music A dataset for music analysis Link
Absorb192 x 288 x 30 x 1200
(longitudes x latitudes x altitude x time)
Climate Climate Data at NCAR Link