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

Overview

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.

Paper

Zoom-Tucker is described in the following paper:

• Fast and Memory-Efficient Tucker decomposition for Answering Diverse Time Range Queries
  Jun-Gi Jang and U Kang.
  

  The paper is accepted to KDD 2021 (awarded Best Research Paper).

  [Paper] [Bibtex] [Slide]

Code

• zoomtucker_code: [Download]

Datasets