Back to search

University of Washington

Data-Aware Complexity Analysis and Program Optimization

Abstract

dc:description.abstract

This dissertation explores the problem of analyzing and optimizing data-dependent programs from a theoretical and practical perspective. The performance of these programs depends in a complex manner on the distribution of the input data, and they arise in many contexts, e.g. databases, sparse tensor programming, and graph analytics. By definition, these programs cannot be optimized by considering the code alone, so an optimizer for them must consider information about the data distribution. This dissertation presents two new theoretical approaches for analyzing data-dependent programs by bounding the size of their intermediate results: the degree sequence bound and partition constraints. It then describes two practical systems for producing these bounds: SafeBound and COLOR. Lastly, we present a state-of-the-art optimizer for sparse tensor programs, Galley, that demonstrates the value of data-aware optimization.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Deeds, Kyle
Advisors dc:contributor.advisor
  • Suciu, Dan
  • Balazinska, Magda

Subjects

dc:subject × 8

Rights

dc:rights
Statement dc:rights
  • CC BY
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1773/53971

Chain of custody

source
Harvested from
University of Washington
Base URL
digital.lib.washington.edu/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Deeds, Kyle. Data-Aware Complexity Analysis and Program Optimization. 2025. https://hdl.handle.net/1773/53971