{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T22:37:03Z","timestamp":1778279823075,"version":"3.51.4"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["SHF 2312195 and IIS 2314527"],"award-info":[{"award-number":["SHF 2312195 and IIS 2314527"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>\n                    The tensor programming abstraction is a foundational paradigm which allows users to write high performance programs via a high-level imperative interface. Recent work on\n                    <jats:italic toggle=\"yes\">sparse tensor compilers<\/jats:italic>\n                    has extended this paradigm to sparse tensors (i.e., tensors where most entries are not explicitly represented). With these systems, users define the semantics of the program and the algorithmic decisions in a concise language that can be compiled to efficient low-level code. However, these systems still require users to make complex decisions about program structure and memory layouts to write efficient programs.\n                  <\/jats:p>\n                  <jats:p>\n                    This work presents\n                    <jats:italic toggle=\"yes\">.Galley<\/jats:italic>\n                    , a system for declarative tensor programming that allows users to write efficient tensor programs without making complex algorithmic decisions. Galley is the first system to perform cost based lowering of sparse tensor algebra to the imperative language of sparse tensor compilers, and the first to optimize arbitrary operators beyond \u03a3 and *. First, it decomposes the input program into a sequence of aggregation steps through a novel extension of the FAQ framework. Second, Galley optimizes and converts each aggregation step to a concrete program, which is compiled and executed with a sparse tensor compiler. We show that Galley produces programs that are 1-300x faster than competing methods for machine learning over joins and 5-20x faster than a state-of-the-art relational database for subgraph counting workloads with a minimal optimization overhead.\n                  <\/jats:p>","DOI":"10.1145\/3725301","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-24","source":"Crossref","is-referenced-by-count":3,"title":["Galley: Modern Query Optimization for Sparse Tensor Programs"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2267-3276","authenticated-orcid":false,"given":"Kyle","family":"Deeds","sequence":"first","affiliation":[{"name":"University of Washington, Seattle, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4963-0869","authenticated-orcid":false,"given":"Willow","family":"Ahrens","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6805-0325","authenticated-orcid":false,"given":"Magdalena","family":"Balazinska","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4144-0868","authenticated-orcid":false,"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"[n. d.]. https:\/\/benchmark.clickhouse.com\/"},{"key":"e_1_2_2_2_1","volume-title":"Benoit Steiner, Paul A. Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zhang.","author":"Abadi Mart\u00edn","year":"2016","unstructured":"Mart\u00edn Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek Gordon Murray, Benoit Steiner, Paul A. Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zhang. 2016. TensorFlow: A system for large-scale machine learning. CoRR abs\/1605.08695 (2016). arXiv:1605.08695 http:\/\/arxiv.org\/abs\/1605.08695"},{"key":"e_1_2_2_3_1","volume-title":"Sparse: A more modern sparse array library.. In SciPy. 65--68.","author":"Abbasi Hameer","year":"2018","unstructured":"Hameer Abbasi. 2018. Sparse: A more modern sparse array library.. In SciPy. 65--68."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3579990.3580020"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523442"},{"key":"e_1_2_2_7_1","first-page":"769","article-title":"The foundation of the general theory of relativity","volume":"354","author":"Albert Einstein","year":"1916","unstructured":"Einstein Albert, W Perrett, and G Jeffery. 1916. The foundation of the general theory of relativity. Annalen der Physik 354, 7 (1916), 769.","journal-title":"Annalen der Physik"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SUPERC.1990.129995"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554853"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588682"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3544559"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589266"},{"key":"e_1_2_2_13_1","volume-title":"10th Conference on Innovative Data Systems Research, CIDR","author":"Boehm Matthias","year":"2020","unstructured":"Matthias Boehm, Iulian Antonov, Sebastian Baunsgaard, Mark Dokter, Robert Ginth\u00f6r, Kevin Innerebner, Florijan Klezin, Stefanie N. Lindstaedt, Arnab Phani, Benjamin Rath, Berthold Reinwald, Shafaq Siddiqui, and Sebastian Benjamin Wrede. 2020. SystemDS: A Declarative Machine Learning System for the End-to-End Data Science Lifecycle. In 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, The Netherlands, January 12--15, 2020, Online Proceedings. www.cidrdb.org. http:\/\/cidrdb.org\/cidr2020\/papers\/p22-boehm-cidr20.pdf"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007279"},{"key":"e_1_2_2_15_1","volume-title":"EinDecomp: Decomposition of Declaratively-Specified Machine Learning and Numerical Computations for Parallel Execution. arXiv preprint arXiv:2410.02682","author":"Bourgeois Daniel","year":"2024","unstructured":"Daniel Bourgeois, Zhimin Ding, Dimitrije Jankov, Jiehui Li, Mahmoud Sleem, Yuxin Tang, Jiawen Yao, Xinyu Yao, and Chris Jermaine. 2024. EinDecomp: Decomposition of Declaratively-Specified Machine Learning and Numerical Computations for Parallel Execution. arXiv preprint arXiv:2410.02682 (2024)."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3604437.3604458"},{"key":"e_1_2_2_18_1","volume-title":"Towards linear algebra over normalized data. arXiv preprint arXiv:1612.07448","author":"Chen Lingjiao","year":"2016","unstructured":"Lingjiao Chen, Arun Kumar, Jeffrey Naughton, and Jignesh M Patel. 2016. Towards linear algebra over normalized data. arXiv preprint arXiv:1612.07448 (2016)."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(99)00059-4"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588907"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2311.09549"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3595360.3595853"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1038\/S41586-020--2649--2"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551833"},{"key":"e_1_2_2_25_1","volume-title":"11th Conference on Innovative Data Systems Research, CIDR","author":"Hertzschuch Axel","year":"2021","unstructured":"Axel Hertzschuch, Claudio Hartmann, Dirk Habich, and Wolfgang Lehner. 2021. Simplicity Done Right for Join Ordering. In 11th Conference on Innovative Data Systems Research, CIDR 2021, Virtual Event, January 11--15, 2021, Online Proceedings. www.cidrdb.org. http:\/\/cidrdb.org\/cidr2021\/papers\/cidr2021_paper01.pdf"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356506"},{"key":"e_1_2_2_27_1","volume-title":"Sten: Productive and efficient sparsity in pytorch. arXiv preprint arXiv:2304.07613","author":"Ivanov Andrei","year":"2023","unstructured":"Andrei Ivanov, Nikoli Dryden, Tal Ben-Nun, Saleh Ashkboos, and Torsten Hoefler. 2023. Sten: Productive and efficient sparsity in pytorch. arXiv preprint arXiv:2304.07613 (2023)."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133901"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3467861.3467869"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723713"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.ASCOM.2021.100505"},{"key":"e_1_2_2_33_1","volume-title":"Freitag","author":"Neumann Thomas","year":"2020","unstructured":"Thomas Neumann and Michael J. Freitag. 2020. Umbra: A Disk-Based System with In-Memory Performance. In 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, The Netherlands, January 12--15, 2020, Online Proceedings. www.cidrdb.org. http:\/\/cidrdb.org\/cidr2020\/papers\/p29-neumann-cidr20.pdf"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526141"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389702"},{"key":"e_1_2_2_36_1","volume-title":"High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Paszke Adam","year":"2019","unstructured":"Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas K\u00f6pf, Edward Z. Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8--14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). 8024--8035. https:\/\/proceedings.neurips.cc\/paper\/2019\/hash\/bdbca288fee7f92f2bfa9f7012727740-Abstract.html"},{"key":"e_1_2_2_37_1","unstructured":"Pydata. [n. d.]. Pydata\/sparse: Sparse multi-dimensional arrays for the PyData ecosystem. https:\/\/github.com\/pydata\/sparse"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320212"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462176"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882939"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2312.17355"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3527333"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2013.19"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3603719.3603726"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW52791.2021.00046"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2017.2761740"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.CPC.2022.108292"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407799"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3665252.3665259"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457399"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725301","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:55:58Z","timestamp":1774983358000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725301"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725301"],"URL":"https:\/\/doi.org\/10.1145\/3725301","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}