Fast and Memory-Efficient Algorithms for High-Order Tucker Decomposition

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 22
  • Download : 0
Multi-aspect data appear frequently in web-related applications. For example, product reviews are quadruplets of the form (user, product, keyword, timestamp), and search-engine logs are quadruplets of the form (user, keyword, location, timestamp). How can we analyze such web-scale multi-aspect data on an off-the-shelf workstation with a limited amount of memory? Tucker decomposition has been used widely for discovering patterns in such multi-aspect data, which are naturally expressed as large but sparse tensors. However, existing Tucker decomposition algorithms have limited scalability, failing to decompose large-scale high-order (= 4) tensors, since they explicitly materialize intermediate data, whose size grows exponentially with the order. To address this problem, which we call "Materialization Bottleneck," we propose S- HOT, a scalable algorithm for high-order Tucker decomposition. S- HOT minimizes materialized intermediate data by using an on-the-fly computation, and it is optimized for disk-resident tensors that are too large to fit in memory. We theoretically analyze the amount of memory and the number of data scans required by S- HOT. Moreover, we empirically showthat S- HOT handles tensors with higher order, dimensionality, and rank than baselines. For example, S- HOT successfully decomposes a real-world tensor from the Microsoft Academic Graph on an off-the-shelf workstation, while all baselines fail. Especially, in terms of dimensionality, S- HOT decomposes 1000xlarger tensors than baselines.
Publisher
SPRINGER LONDON LTD
Issue Date
2020-07
Language
English
Article Type
Article
Citation

KNOWLEDGE AND INFORMATION SYSTEMS, v.62, no.7, pp.2765 - 2794

ISSN
0219-1377
DOI
10.1007/s10115-019-01435-1
URI
http://hdl.handle.net/10203/276684
Appears in Collection
RIMS Journal Papers
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0