Multi-Aspect Incremental Tensor Decomposition Based on Distributed In-Memory Big Data Systems

Yang, Hye-Kyung; Yong, Hwan-Seung

doi:10.2478/jdis-2020-0010

Abstract

Purpose

We propose InParTen2, a multi-aspect parallel factor analysis three-dimensional tensor decomposition algorithm based on the Apache Spark framework. The proposed method reduces re-decomposition cost and can handle large tensors.

Design/methodology/approach

Considering that tensor addition increases the size of a given tensor along all axes, the proposed method decomposes incoming tensors using existing decomposition results without generating sub-tensors. Additionally, InParTen2 avoids the calculation of Khari–Rao products and minimizes shuffling by using the Apache Spark platform.

Findings

The performance of InParTen2 is evaluated by comparing its execution time and accuracy with those of existing distributed tensor decomposition methods on various datasets. The results confirm that InParTen2 can process large tensors and reduce the re-calculation cost of tensor decomposition. Consequently, the proposed method is faster than existing tensor decomposition algorithms and can significantly reduce re-decomposition cost.

Research limitations

There are several Hadoop-based distributed tensor decomposition algorithms as well as MATLAB-based decomposition methods. However, the former require longer iteration time, and therefore their execution time cannot be compared with that of Spark-based algorithms, whereas the latter run on a single machine, thus limiting their ability to handle large data.

Practical implications

The proposed algorithm can reduce re-decomposition cost when tensors are added to a given tensor by decomposing them based on existing decomposition results without re-decomposing the entire tensor.

Originality/value

The proposed method can handle large tensors and is fast within the limited-memory framework of Apache Spark. Moreover, InParTen2 can handle static as well as incremental tensor decomposition.

References

Bennett, J., & Lanning, S. (2007). The Netflix prize. In Proceedings of the KDD Cup Workshop 2007 (pp. 3–6). ACM. New York, NY, USA. https://www.cs.uic.edu/~liub/KDD-cup-2007/NetflixPrize-description.pdf
Search in Google Scholar Back to article
Ge, H., Zhang, K., Alfifi, M., Hu, X., & Caverle, J. (2018). DisTenC: A distributed algorithm for scalable tensor completion on spark. In Proceedings of the 34th IEEE International Conference on Data Engineering (pp. 137–148). IEEE. Paris, France. DOI: 10.1109/ICDE.2018.00022
Open DOI Search in Google Scholar Back to article
Gujral, E., Pasricha, R., & Papalexakis, E.E. (2018). SamBaTen: Sampling-based batch incremental tensor decomposition. In Proceedings of the 2018 SIAM International Conference on Data Mining (pp. 387–395). SIAM. San Diego Marriott Mission Valley, San Diego, CA, USA. https://doi.org/10.1137/1.9781611975321.44
Search in Google Scholar Back to article
Jeon, B.S., Jeon, I., Lee, S., & Kang, U. (2016). SCouT: Scalable coupled matrix-tensor factorization—Algorithm and discoveries. In Proceedings of the 32nd IEEE International Conference on Data Engineering (pp. 811–822). IEEE. Helsinki, Finland.
Search in Google Scholar Back to article
Jeon, I., Papalexakis, E.E., Kang, U., & Faloutsos, C. (2015). HaTen2: Billion-scale tensor decompositions. In Proceedings of the 31st IEEE International Conference on Data Engineering (pp. 1047–1058). IEEE. Seoul, South Korea. DOI: 10.1109/ICDE.2015.7113355
Open DOI Search in Google Scholar Back to article
Kang, U., Papalexakis, E., Harpale, A., & Faloutsos, C. (2012). GigaTensor: Scaling tensor analysis up by 100 times—Algorithms and Discoveries. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 316–324). ACM. Beijing, China. https://doi.org/10.1145/2339530.2339583
Search in Google Scholar Back to article
Ma, C., Yang, X., & Wang, H. (2018). Randomized online CP decomposition. In Proceedings of the Tenth International Conference on Advanced Computational Intelligence (pp. 414–419). IEEE. Xiamen, China. DOI: 10.1109/ICACI.2018.8377495
Open DOI Search in Google Scholar Back to article
Najafi, M., He, L., & Yu, P.S. (2019). Outlier-robust multi-aspect streaming tensor completion and factorization. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (pp. 3187–3194). ijcai.org. Macao, China. https://doi.org/10.24963/ijcai.2019/442
Search in Google Scholar Back to article
Nimishakavi, M., Mishra, B., Gupta, M., & Talukdar, P. (2018). Inductive framework for multi-aspect streaming tensor completion with side information. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management (pp. 307–316). ACM. Torino, Italy. https://doi.org/10.1145/3269206.3271713
Search in Google Scholar Back to article
Papalexakis, E.E., Faloutsos, C., & Sidiropoulos, N.D. (2012). ParCube: Sparse parallelizable tensor decomposition. In Proceedings of Machine Learning and Knowledge Discovery in Databases—European Conference (pp. 521–536). Springer. Bristol, UK. DOI: 10.1007/978-3-642-33460-3_39
Open DOI Search in Google Scholar Back to article
Park, N., Jeon, B., Lee, J., & Kang, U. (2016). BIGtensor: Mining billion-scale tensor made easy. In Proceedings of the 25th ACM International Conference on Information and Knowledge Management (pp. 2457–2460). ACM. Indianapolis, IN, USA. http://dx.doi.org/10.1145/2983323.2983332
Search in Google Scholar Back to article
Song, Q., Huang, X., Ge, H., Caverlee, J., & Hu, X. (2017). Multi-aspect streaming tensor completion. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 435–443). ACM. Halifax, NS, Canada. https://doi.org/10.1145/3097983.3098007
Search in Google Scholar Back to article
Yang, H.K., & Yong, H.S. (2018). S-PARAFAC: Distributed tensor decomposition using Apache Spark. Journal of Korean Instituted of Information Scientists and Engineers, 45(3), 280–287.
Search in Google Scholar Back to article
Yang, H.K., & Yong, H.S. (2019a). Distributed PARAFAC decomposition method based on in-memory big data system. In Proceedings of Database Systems for Advanced Applications 24th International Conference (pp. 292–295). Springer. Chiang Mai, Thailand. https://doi.org/10.1007/978-3-030-18590-9_31
Search in Google Scholar Back to article
Yang, H.K., & Yong, H.S. (2019b). Incremental PARAFAC decomposition for three-dimensional tensors using Apache Spark. In Proceedings of Web Engineering-19th International Conference (pp. 53–71). Springer. Daejeon, South Korea. https://doi.org/10.1007/978-3-030-19274-7_5
Search in Google Scholar Back to article
Zaharia, M., Chowdhury, M., Das, T., Dave, A., Ma, J., McCauly, M.,…, & Stoica, I. (2012). Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation (pp. 15–28).USENIX. San Jose, CA, USA. https://dl.acm.org/doi/10.5555/2228298.2228301
Search in Google Scholar Back to article
Zhou, S., Erfani, S.M., & Bailey, J. (2018). Online CP decomposition for sparse tensors. In Proceedings of the IEEE International Conference on Data Mining (pp. 1458–1463). IEEE. Singapore. DOI: 10.1109/ICDM.2018.00202
Open DOI Search in Google Scholar Back to article