{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,9]],"date-time":"2026-09-09T03:36:57Z","timestamp":1788925017558,"version":"build-2803163510"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2023,2,27]],"date-time":"2023-02-27T00:00:00Z","timestamp":1677456000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Research Foundation of Korea (NRF) funded by MSIT","award":["2022R1A2C3007921"],"award-info":[{"award-number":["2022R1A2C3007921"]}]},{"name":"Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by MSIT","award":["2021-0-01343"],"award-info":[{"award-number":["2021-0-01343"]}]},{"name":"Artificial Intelligence Graduate School Program","award":["2021-0-02068"],"award-info":[{"award-number":["2021-0-02068"]}]},{"name":"Artificial Intelligence Innovation Hub"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2023,10,30]]},"abstract":"<jats:p>Given a dense tensor, how can we efficiently discover hidden relations and patterns in static and online streaming settings? Tucker decomposition is a fundamental tool to analyze multidimensional arrays in the form of tensors. However, existing Tucker decomposition methods in both static and online streaming settings have limitations of efficiency since they directly deal with large dense tensors for the result of Tucker decomposition. In a static setting, although few static methods have tried to reduce their time cost by sampling tensors, sketching tensors, and efficient matrix operations, there remains a need for an efficient method. Moreover, streaming versions of Tucker decomposition are still time-consuming to deal with newly arrived tensors.<\/jats:p>\n          <jats:p>We propose D-Tucker and D-TuckerO, efficient Tucker decomposition methods for large dense tensors in static and online streaming settings, respectively. By decomposing a given large dense tensor with randomized singular value decomposition, avoiding the reconstruction from SVD results, and carefully determining the order of operations, D-Tucker and D-TuckerO efficiently obtain factor matrices and core tensor. Experimental results show that D-Tucker achieves up to 38.4 \u00d7 faster running times, and requires up to 17.2 \u00d7 less space than existing methods while having similar accuracy. Furthermore, D-TuckerO is up to 6.1\u00d7 faster than existing streaming methods for each newly arrived tensor while its running time is proportional to the size of the newly arrived tensor, not the accumulated tensor.<\/jats:p>","DOI":"10.1145\/3568682","type":"journal-article","created":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T11:48:31Z","timestamp":1666266511000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Static and Streaming Tucker Decomposition for Dense Tensors"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8328-3920","authenticated-orcid":false,"given":"Jun-Gi","family":"Jang","sequence":"first","affiliation":[{"name":"Seoul National University, Seoul, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8774-6950","authenticated-orcid":false,"given":"U","family":"Kang","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,2,27]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1145\/3269206.3271775","volume-title":"Proceedings of the 27th ACM International Conference on Information and Knowledge Management","author":"Afshar Ardavan","year":"2018","unstructured":"Ardavan Afshar, Ioakeim Perros, Evangelos E. Papalexakis, Elizabeth Searles, Joyce Ho, and Jimeng Sun. 2018. COPA: Constrained PARAFAC2 for sparse & large datasets. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management. 793\u2013802."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-021-06059-7"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3482048"},{"key":"e_1_3_3_5_2","first-page":"912","volume-title":"Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium","author":"Austin Woody","year":"2016","unstructured":"Woody Austin, Grey Ballard, and Tamara G. Kolda. 2016. Parallel tensor compression for large-scale scientific data. In Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium. 912\u2013922."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1186785.1186794"},{"key":"e_1_3_3_7_2","article-title":"MATLAB Tensor Toolbox Version 3.0-dev","author":"Bader Brett W.","year":"2017","unstructured":"Brett W. Bader, Tamara G. Kolda, Acar Ataman, Evrim NMN, Daniel Dunlavy, Robert Bassett, Casey J. Battaglino, Todd Plantenga, Eric Chi, and Samantha Hansen. 2017. MATLAB Tensor Toolbox Version 3.0-dev. Available online. Retrieved from https:\/\/www.tensortoolbox.org.","journal-title":"Available online"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/04060593X"},{"key":"e_1_3_3_9_2","doi-asserted-by":"crossref","unstructured":"Grey Ballard Alicia Klinvex and Tamara G. Kolda. 2019. TuckerMPI: A parallel C++\/MPI software package for large-scale data compression via the tucker tensor decomposition. ACM Transactions on Mathematical Software (TOMS) 46 2 (2020) 1\u201331.","DOI":"10.1145\/3378445"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2014.2376938"},{"key":"e_1_3_3_11_2","first-page":"1038","volume-title":"Proceedings of the 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS)","author":"Chakaravarthy Venkatesan T.","year":"2017","unstructured":"Venkatesan T. Chakaravarthy, Jee W. Choi, Douglas J. Joseph, Xing Liu, Prakash Murali, Yogish Sabharwal, and Dheeraj Sreedhar. 2017. On optimizing distributed tucker decomposition for dense tensors. In Proceedings of the 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 1038\u20131047."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10444-018-9622-8"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0217316"},{"key":"e_1_3_3_14_2","first-page":"42:1\u201342:11","volume-title":"Proceedings of the SC18: International Conference for High Performance Computing, Networking, Storage and Analysis","author":"Choi Jee W.","unstructured":"Jee W. Choi, Xing Liu, and Venkatesan T. Chakaravarthy. [n. d.]. High-performance dense tucker decomposition on GPU clusters. In Proceedings of the SC18: International Conference for High Performance Computing, Networking, Storage and Analysis. 42:1\u201342:11."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3019134"},{"key":"e_1_3_3_16_2","volume-title":"Proceedings of the 18th International Society for Music Information Retrieval Conference (ISMIR\u201917)","author":"Defferrard Micha\u00ebl","year":"2017","unstructured":"Micha\u00ebl Defferrard, Kirell Benzi, Pierre Vandergheynst, and Xavier Bresson. 2017. FMA: A dataset for music analysis. In Proceedings of the 18th International Society for Music Information Retrieval Conference (ISMIR\u201917)."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3184558.3192310"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1364\/JOSAA.23.002359"},{"key":"e_1_3_3_19_2","first-page":"387","volume-title":"Proceedings of the 2018 SIAM International Conference on Data Mining","author":"Gujral Ekta","year":"2018","unstructured":"Ekta Gujral, Ravdeep Pasricha, and Evangelos E. Papalexakis. 2018. SamBaTen: Sampling-based batch incremental tensor decomposition. In Proceedings of the 2018 SIAM International Conference on Data Mining. SIAM, 387\u2013395."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401933"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1058467"},{"key":"e_1_3_3_23_2","first-page":"2454","volume-title":"Proceedings of the International Council for Open and Distance Education","author":"Jang Jun-Gi","year":"2022","unstructured":"Jun-Gi Jang and U. Kang. 2022. DPar2: Fast and scalable PARAFAC2 decomposition for irregular dense tensors. In Proceedings of the International Council for Open and Distance Education. IEEE, 2454\u20132467."},{"key":"e_1_3_3_24_2","first-page":"1083","volume-title":"Proceedings of the Conference on Information and Knowledge Management","author":"Jang Jun-Gi","year":"2018","unstructured":"Jun-Gi Jang, Dongjin Choi, Jinhong Jung, and U. Kang. 2018. Zoom-SVD: Fast and memory efficient method for extracting key patterns in an arbitrary time range. In Proceedings of the Conference on Information and Knowledge Management. ACM, 1083\u20131092."},{"key":"e_1_3_3_25_2","doi-asserted-by":"crossref","first-page":"1850","DOI":"10.1109\/ICDE48307.2020.00186","volume-title":"Proceedings of the 2020 IEEE 36th International Conference on Data Engineering (ICDE\u201920)","author":"Jang Jun-Gi","year":"2020","unstructured":"Jun-Gi Jang and U. Kang. 2020. D-tucker: Fast and memory-efficient tucker decomposition for dense tensors. In Proceedings of the 2020 IEEE 36th International Conference on Data Engineering (ICDE\u201920). IEEE, 1850\u20131853."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467290"},{"key":"e_1_3_3_27_2","doi-asserted-by":"crossref","first-page":"1047","DOI":"10.1109\/ICDE.2015.7113355","volume-title":"Proceedings of the 2015 IEEE 31st International Conference on Data Engineering","author":"Jeon Inah","year":"2015","unstructured":"Inah Jeon, Evangelos E. Papalexakis, U. Kang, and Christos Faloutsos. 2015. HaTen2: Billion-scale tensor decompositions. In Proceedings of the 2015 IEEE 31st International Conference on Data Engineering. 1047\u20131058."},{"key":"e_1_3_3_28_2","unstructured":"Yong-Deok Kim Eunhyeok Park Sungjoo Yoo Taelim Choi Lu Yang and Dongjun Shin. 2016. Compression of deep convolutional neural networks for fast and low power mobile applications. In ICLR . arXiv:1511.06530. Retrieved from https:\/\/arxiv.org\/abs\/1511.06530."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/07070111X"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.89"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896305696"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479898346995"},{"key":"e_1_3_3_33_2","first-page":"840","volume-title":"Proceedings of the International Council for Open and Distance Education","author":"Lee Dongjin","year":"2021","unstructured":"Dongjin Lee and Kijung Shin. 2021. Robust factorization of real-world tensor streams with patterns, missing values, and outliers. In Proceedings of the International Council for Open and Distance Education. IEEE, 840\u2013851."},{"key":"e_1_3_3_34_2","first-page":"76:1\u201376:12","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis","author":"Li Jiajia","year":"2015","unstructured":"Jiajia Li, Casey Battaglino, Ioakeim Perros, Jimeng Sun, and Richard W. Vuduc. 2015. An input-adaptive and in-place approach to dense tensor-times-matrix multiply. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 76:1\u201376:12."},{"key":"e_1_3_3_35_2","first-page":"10117","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Malik Osman Asif","year":"2018","unstructured":"Osman Asif Malik and Stephen Becker. 2018. Low-rank tucker decomposition of large tensors using TensorSketch. In Proceedings of the Advances in Neural Information Processing Systems. 10117\u201310127."},{"key":"e_1_3_3_36_2","doi-asserted-by":"crossref","unstructured":"Rachel Minster Arvind K. Saibaba and Misha E. Kilmer. 2019. Randomized algorithms for low-rank tensor decompositions in the Tucker format. SIAM Journal on Mathematics of Data Science 2 1 (2020) 189\u2013215.","DOI":"10.1137\/19M1261043"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1152876"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2009.2016885"},{"key":"e_1_3_3_39_2","first-page":"761","volume-title":"Proceedings of the 10th ACM International Conference on Web Search and Data Mining","author":"Oh Jinoh","year":"2017","unstructured":"Jinoh Oh, Kijung Shin, Evangelos E. Papalexakis, Christos Faloutsos, and Hwanjo Yu. 2017. S-HOT: Scalable high-order tucker decomposition. In Proceedings of the 10th ACM International Conference on Web Search and Data Mining. 761\u2013770."},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2908639"},{"key":"e_1_3_3_41_2","first-page":"1120","volume-title":"Proceedings of the 2018 IEEE 34th International Conference on Data Engineering","author":"Oh Sejoon","year":"2018","unstructured":"Sejoon Oh, Namyong Park, Lee Sael, and U. Kang. 2018. Scalable tucker factorization for sparse tensors - algorithms and discoveries. In Proceedings of the 2018 IEEE 34th International Conference on Data Engineering. 1120\u20131131."},{"key":"e_1_3_3_42_2","first-page":"697","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Papadimitriou Spiros","year":"2005","unstructured":"Spiros Papadimitriou, Jimeng Sun, and Christos Faloutsos. 2005. Streaming pattern discovery in multiple time-series. In Proceedings of the International Conference on Very Large Data Bases. ACM, 697\u2013708."},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.29"},{"key":"e_1_3_3_44_2","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1145\/3097983.3098014","volume-title":"Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Perros Ioakeim","year":"2017","unstructured":"Ioakeim Perros, Evangelos E. Papalexakis, Fei Wang, Richard Vuduc, Elizabeth Searles, Michael Thompson, and Jimeng Sun. 2017. SPARTan: Scalable PARAFAC2 for large & sparse data. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 375\u2013384."},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/1718487.1718498"},{"key":"e_1_3_3_46_2","doi-asserted-by":"crossref","first-page":"1019","DOI":"10.1109\/BigData.2015.7363854","volume-title":"Proceedings of the 2015 IEEE International Conference on Big Data","author":"Schimbinschi Florin","year":"2015","unstructured":"Florin Schimbinschi, Xuan Vinh Nguyen, James Bailey, Chris Leckie, Hai Vu, and Rao Kotagiri. 2015. Traffic forecasting in complex urban networks: Leveraging big data and machine learning. In Proceedings of the 2015 IEEE International Conference on Big Data. IEEE, 1019\u20131024."},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2610420"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/tsp.2017.2690524"},{"key":"e_1_3_3_49_2","first-page":"81","volume-title":"Proceedings of the 2018 SIAM International Conference on Data Mining","author":"Smith Shaden","year":"2018","unstructured":"Shaden Smith, Kejun Huang, Nicholas D. Sidiropoulos, and George Karypis. 2018. Streaming tensor factorization for infinite data sources. In Proceedings of the 2018 SIAM International Conference on Data Mining. SIAM, 81\u201389."},{"key":"e_1_3_3_50_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1007\/978-3-319-64203-1_47","volume-title":"Euro-Par 2017","author":"Smith Shaden","year":"2017","unstructured":"Shaden Smith and George Karypis. 2017. Accelerating the tucker decomposition with compressed sparse tensors. In Euro-Par 2017(Lecture Notes in Computer Science, Vol. 10417). Springer, 653\u2013668."},{"issue":"4","key":"e_1_3_3_51_2","first-page":"1","article-title":"DAO-CP: Data-adaptive online CP decomposition for tensor stream","volume":"17","author":"Son Sangjun","year":"2022","unstructured":"Sangjun Son, Yong-chan Park, Minyong Cho, and U. Kang. 2022. DAO-CP: Data-adaptive online CP decomposition for tensor stream. PLOS ONE 17, 4 (042022), 1\u201318.","journal-title":"PLOS ONE"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098007"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150445"},{"key":"e_1_3_3_54_2","doi-asserted-by":"crossref","unstructured":"Yiming Sun Yang Guo Charlene Luo Joel A. Tropp and Madeleine Udell. 2020. Low-rank tucker approximation of a tensor from streaming data. SIAM Journal on Mathematics of Data Science 2 4 (2020) 1123\u20131150.","DOI":"10.1137\/19M1257718"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2019.2906603"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/tpami.2016.2608882"},{"key":"e_1_3_3_57_2","first-page":"689","volume-title":"Proceedings of the 2010 SIAM International Conference on Data Mining","author":"Tsourakakis Charalampos E.","year":"2010","unstructured":"Charalampos E. Tsourakakis. 2010. MACH: Fast randomized tensor decompositions. In Proceedings of the 2010 SIAM International Conference on Data Mining. 689\u2013700."},{"issue":"2","key":"e_1_3_3_58_2","article-title":"A new truncation strategy for the higher-order singular value decomposition","volume":"34","author":"Vannieuwenhoven Nick","year":"2012","unstructured":"Nick Vannieuwenhoven, Raf Vandebril, and Karl Meerbergen. 2012. A new truncation strategy for the higher-order singular value decomposition. SIAM Journal on Scientific Computing 34, 2 (2012), A1027\u2013A1052.","journal-title":"SIAM Journal on Scientific Computing"},{"key":"e_1_3_3_59_2","first-page":"393","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition CVPR Workshops","author":"Wang Yi","year":"2014","unstructured":"Yi Wang, Pierre-Marc Jodoin, Fatih Murat Porikli, Janusz Konrad, Yannick Benezeth, and Prakash Ishwar. 2014. CDnet 2014: An expanded change detection benchmark dataset. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition CVPR Workshops. 393\u2013400."},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2007.12.002"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.14778\/3067421.3067424"},{"key":"e_1_3_3_62_2","first-page":"594","volume-title":"Proceedings of the 2021 SIAM International Conference on Data Mining (SDM\u201921)","author":"Yin Kejing","year":"2021","unstructured":"Kejing Yin, William K. Cheung, Benjamin C. M. Fung, and Jonathan Poon. 2021. Tedpar: Temporally dependent parafac2 factorization for phenotype-based disease progression modeling. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM\u201921). SIAM, 594\u2013602."},{"key":"e_1_3_3_63_2","doi-asserted-by":"crossref","first-page":"1458","DOI":"10.1109\/ICDM.2018.00202","volume-title":"Proceedings of the 2018 IEEE International Conference on Data Mining","author":"Zhou Shuo","year":"2018","unstructured":"Shuo Zhou, Sarah M. Erfani, and James Bailey. 2018. Online CP decomposition for sparse tensors. In Proceedings of the 2018 IEEE International Conference on Data Mining. IEEE Computer Society, 1458\u20131463."},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939763"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3568682","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3568682","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:34Z","timestamp":1750183714000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3568682"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,27]]},"references-count":63,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10,30]]}},"alternative-id":["10.1145\/3568682"],"URL":"https:\/\/doi.org\/10.1145\/3568682","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,27]]},"assertion":[{"value":"2021-12-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}