SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra

Summary: Converts large-scale linear algebra to relational algebra and optimizes via complete equality saturation. SPORES uses rule sampling to explore expression spaces and a solver to pick the optimal plan; integrated with SystemML, it yields up to 10× speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12277
Venue: VLDB
Year: 2020
Pagerank: 6.4168322e-05
Overall Rank: 4,976 | 65.87%
DOI: 10.14778/3407790.3407799

Incoming Non-self Citations Over Time

Authors

1. Yisu Remy Wang (University of Washington)
2. Shana Hutchison (University of Washington)
3. Jonathan Leang (University of Washington)
4. Bill Howe (University of Washington)
5. Dan Suciu (University of Washington)

BibTeX Citation

@article{wang_vldb20,
        title = {{SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra}},
        author = {Wang, Yisu Remy and Hutchison, Shana and Leang, Jonathan and Howe, Bill and Suciu, Dan},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {11},
        pages = {1919--1932},
        doi = {10.14778/3407790.3407799},
        url = {https://doi.org/10.14778/3407790.3407799},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,823	Query Processing on Tensor Computation Runtimes	2022	VLDB	8.0893814e-05
2,865	End-to-end Optimization of Machine Learning Prediction Queries	2022	SIGMOD	8.0180243e-05
2,888	AI Meets Database: AI4DB and DB4AI	2021	SIGMOD	7.9941489e-05
3,874	Tensors: An abstraction for general data processing	2021	VLDB	7.0561161e-05
4,240	LIMA: Fine-grained Lineage Tracing and Reuse in Machine Learning Systems	2021	SIGMOD	6.809685e-05
5,414	Optimizing Tensor Programs on Flexible Storage	2023	SIGMOD	6.2258658e-05
6,708	Serving Deep Learning Models with Deduplication from Relational Databases	2022	VLDB	5.7964983e-05
7,035	Optimizing Recursive Queries with Program Synthesis	2022	SIGMOD	5.7216112e-05
8,513	Galley: Modern Query Optimization for Sparse Tensor Programs	2025	SIGMOD	5.4119882e-05
8,999	HADAD: A Lightweight Approach for Optimizing Hybrid Complex Analytics Queries	2021	SIGMOD	5.3354529e-05
11,261	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.093636e-05
11,537	Redundancy Elimination in Distributed Matrix Computation	2022	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0024089429
17	Provenance Semirings	2007	PODS	0.00059843817
309	Optimization of Real Conjunctive Queries	1993	PODS	0.00021768596
358	FAQ: Questions Asked Frequently	2016	PODS	0.00020243592
536	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.0001693369
1,013	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012652549
1,298	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00011259156
1,549	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.00010390168
2,179	Enabling and Optimizing Non-linear Feature Interactions in Factorized Linear Algebra	2019	SIGMOD	9.0146333e-05
2,217	Cumulon: Optimizing Statistical Data Analysis in the Cloud	2013	SIGMOD	8.9332438e-05
2,927	In-Database Learning with Sparse Tensors	2018	PODS	7.9531195e-05
3,158	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.6888079e-05
3,205	On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML	2018	VLDB	7.6386536e-05
3,284	SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning	2017	CIDR	7.5663058e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,049	Resource Elasticity for Large-Scale Machine Learning	2015	SIGMOD
2	13,354	STile: Searching Hybrid Sparse Formats for Sparse Deep Learning Operators Automatically	2024	SIGMOD
3	4,409	MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions	2019	SIGMOD
4	2,239	An Intermediate Representation for Optimizing Machine Learning Pipelines	2019	VLDB
5	6,046	Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra	2021	SIGMOD
6	1,235	Towards Linear Algebra over Normalized Data	2017	VLDB
7	8,794	AWARE: Workload-aware, Redundancy-exploiting Linear Algebra	2023	SIGMOD
8	1,644	Compressed Linear Algebra for Large-Scale Machine Learning	2016	VLDB
9	3,205	On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML	2018	VLDB
10	3,284	SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning	2017	CIDR