EUVIMEDEUVIMED entdecken
Crossref

Galley: Modern Query Optimization for Sparse Tensor Programs

Kyle Deeds, Willow Ahrens, Magdalena Balazinska, Dan Suciu

Proceedings of the ACM on Management of Data · 17.06.2025 · 3 (3) · 1-24

DOI: 10.1145/3725301 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.06.2025. Verfasst von Kyle Deeds und 3 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 52 Literaturangaben. Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 sparse tensor compilers 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. This work presents .Galley , 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 Σ 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.

Förderung

  • National Science Foundation

Zitieren

APA

Deeds, K., Ahrens, W., Balazinska, M., & Suciu, D. (2025). Galley: Modern Query Optimization for Sparse Tensor Programs. Proceedings of the ACM on Management of Data, 3(3), 1-24. https://doi.org/10.1145/3725301

Vancouver

Deeds K, Ahrens W, Balazinska M, Suciu D. Galley: Modern Query Optimization for Sparse Tensor Programs. Proceedings of the ACM on Management of Data. 2025;3(3):1-24. doi:10.1145/3725301

BibTeX
@article{Deeds2025,
  author = {Deeds, Kyle and Ahrens, Willow and Balazinska, Magdalena and Suciu, Dan},
  title = {Galley: Modern Query Optimization for Sparse Tensor Programs},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2025},
  volume = {3},
  number = {3},
  pages = {1--24},
  doi = {10.1145/3725301}
}
Kostenlos starten →