{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T17:06:43Z","timestamp":1787591203225,"version":"build-2736575974"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF-BSF","award":["2109922"],"award-info":[{"award-number":["2109922"]}]},{"name":"NSF IIS","award":["1907997"],"award-info":[{"award-number":["1907997"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Tensor programs often need to process large tensors (vectors, matrices, or higher order tensors) that require a specialized storage format for their memory layout. Several such layouts have been proposed in the literature, such as the Coordinate Format, the Compressed Sparse Row format, and many others, that were especially designed to optimally store tensors with specific sparsity properties. However, existing tensor processing systems require specialized extensions in order to take advantage of every new storage format. In this paper we describe a system that allows users to define flexible storage formats in a declarative tensor query language, similar to the language used by the tensor program. The programmer only needs to write storage mappings, which describe, in a declarative way, how the tensors are laid out in main memory. Then, we describe a cost-based optimizer that optimizes the tensor program for the specific memory layout. We demonstrate empirically significant performance improvements compared to state-of-the-art tensor processing systems.<\/jats:p>","DOI":"10.1145\/3588717","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T13:42:05Z","timestamp":1685454125000},"page":"1-27","source":"Crossref","is-referenced-by-count":21,"title":["Optimizing Tensor Programs on Flexible Storage"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-5502-869X","authenticated-orcid":false,"given":"Maximilian","family":"Schleich","sequence":"first","affiliation":[{"name":"RelationalAI, Berkeley, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9062-759X","authenticated-orcid":false,"given":"Amir","family":"Shaikhha","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4144-0868","authenticated-orcid":false,"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000024"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3322967"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457311"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1979.1658743"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/060676489"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276386"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/141000671"},{"key":"e_1_2_2_8_1","unstructured":"Mark Blacher Joachim Giesen S\u00f6ren Laue Julien Klaus and Vikor Leis. 2022. Machine Learning Linear Algebra and More: Is SQL All You Need?. In CIDR."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229865"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137633"},{"key":"e_1_2_2_11_1","volume-title":"TVM: An Automated End-to-End Optimizing Compiler for Deep Learning. In 13th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2018","author":"Chen Tianqi","year":"2018","unstructured":"Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Q. Yan, Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018. TVM: An Automated End-to-End Optimizing Compiler for Deep Learning. In 13th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2018, Carlsbad, CA, USA, October 8--10, 2018, Andrea C. Arpaci-Dusseau and Geoff Voelker (Eds.). USENIX Association, 578--594. https:\/\/www.usenix.org\/conference\/osdi18\/presentation\/chen"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254079"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276493"},{"key":"e_1_2_2_14_1","unstructured":"The SciPy community. 2022. scipy.sparse.dok_matrix -- SciPy v1.8.0 Reference Guide. https:\/\/docs.scipy.org\/doc\/scipy\/reference\/generated\/scipy.sparse.dok_matrix.html. Accessed: 2022-04--14."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/1385-7258(72)90034-0"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407797"},{"key":"e_1_2_2_18_1","first-page":"19","article-title":"The Cascades Framework for Query Optimization","volume":"18","author":"Graefe Goetz","year":"1995","unstructured":"Goetz Graefe. 1995. The Cascades Framework for Query Optimization. IEEE Data Eng. Bull., Vol. 18, 3 (1995), 19--29. http:\/\/sites.computer.org\/debull\/95SEP-CD.pdf","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780100054"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-020--2649--2"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3070607.3070608"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359630"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375661"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3314872.3314894"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133901"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465334"},{"key":"e_1_2_2_28_1","volume-title":"Sketch-Guided Equality Saturation: Scaling Equality Saturation to Complex Optimizations in Languages with Bindings. arXiv preprint arXiv:2111.13040","author":"Koehler Thomas","year":"2021","unstructured":"Thomas Koehler, Phil Trinder, and Michel Steuwer. 2021. Sketch-Guided Equality Saturation: Scaling Equality Saturation to Complex Optimizations in Languages with Bindings. arXiv preprint arXiv:2111.13040 (2021)."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723713"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3405470"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164207"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925952"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629698"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2004.840306"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320212"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3150211"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462176"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324961"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.5441\/002"},{"key":"e_1_2_2_41_1","volume-title":"Functional Collection Programming with Semi-Ring Dictionaries. CoRR","author":"Shaikhha Amir","year":"2021","unstructured":"Amir Shaikhha, Mathieu Huot, Jaclyn Smith, and Dan Olteanu. 2021a. Functional Collection Programming with Semi-Ring Dictionaries. CoRR, Vol. abs\/2103.06376 (2021). showeprint[arXiv]2103.06376 https:\/\/arxiv.org\/abs\/2103.06376"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368826.3377923"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476356"},{"key":"e_1_2_2_44_1","volume-title":"FROSTT: The formidable repository of open sparse tensors and tools.","author":"Smith Shaden","year":"2017","unstructured":"Shaden Smith, Jee W Choi, Jiajia Li, Richard Vuduc, Jongsoo Park, Xing Liu, and George Karypis. 2017. FROSTT: The formidable repository of open sparse tensors and tools."},{"key":"e_1_2_2_45_1","volume-title":"Proceedings of Annual IEEE\/ACM International Symposium on Code Generation and Optimization. 23--32","author":"Spampinato Daniele G","year":"2014","unstructured":"Daniele G Spampinato and Markus P\u00fcschel. 2014. A basic linear algebra compiler. In Proceedings of Annual IEEE\/ACM International Symposium on Code Generation and Optimization. 23--32."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2784731.2784754"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2013.19"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480915"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050018"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.5441\/002"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686--2"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407799"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434304"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457399"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463684"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498696"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588717","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588717","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T12:47:35Z","timestamp":1750164455000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588717"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588717"],"URL":"https:\/\/doi.org\/10.1145\/3588717","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}