Back to papers
MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions
Summary: Proposes MNC, a simple count-based matrix synopsis that exploits structural sparsity to estimate intermediates for linear algebra expressions. Sketch propagation with expression-aware estimators yields accurate sparsity at very low overhead, enabling practical plan and memory-aware ML systems.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 5666
- Venue
- SIGMOD
- Year
- 2019
- Pagerank
- 5.8916346e-05
- Overall Rank
- 4,833 | 66.38%
- DOI
-
10.1145/3299869.3319854
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 11 of 11 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 2,122 |
SystemDS: A Declarative Machine Learning System for the End-to-End Data Science Lifecycle |
2020 |
CIDR |
9.4989076e-05 |
| 6,191 |
Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra |
2021 |
SIGMOD |
5.1642282e-05 |
| 7,358 |
Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries |
2021 |
SIGMOD |
4.7529363e-05 |
| 8,514 |
UPLIFT: Parallelization Strategies for Feature Transformations in Machine Learning Workloads |
2022 |
VLDB |
4.4944285e-05 |
| 8,786 |
AWARE: Workload-aware, Redundancy-exploiting Linear Algebra |
2023 |
SIGMOD |
4.4521262e-05 |
| 8,980 |
HADAD: A Lightweight Approach for Optimizing Hybrid Complex Analytics Queries |
2021 |
SIGMOD |
4.4169807e-05 |
| 9,670 |
On Efficient Large Sparse Matrix Chain Multiplication |
2024 |
SIGMOD |
4.3066148e-05 |
| 10,226 |
Automated Tensor-Relational Decomposition for Large-Scale Sparse Tensor Computation |
2026 |
VLDB |
4.1945683e-05 |
| 10,291 |
Morphing-based Compression for Data-centric ML Pipelines |
2026 |
VLDB |
4.1945683e-05 |
| 11,339 |
Redundancy Elimination in Distributed Matrix Computation |
2022 |
SIGMOD |
4.1945683e-05 |
| 11,363 |
Givens QR Decomposition over Relational Databases |
2022 |
SIGMOD |
4.1945683e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 23 of 23 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 59 |
Sampling-Based Estimation of the Number of Distinct Values of an Attribute |
1995 |
VLDB |
0.00064501896 |
| 99 |
On the Propagation of Errors in the Size of Join Results |
1991 |
SIGMOD |
0.00050022914 |
| 378 |
Towards Estimation Error Guarantees for Distinct Values |
2000 |
PODS |
0.0002497492 |
| 383 |
An Optimal Algorithm for the Distinct Elements Problem |
2010 |
PODS |
0.00024820873 |
| 557 |
SystemML: Declarative Machine Learning on Spark |
2016 |
VLDB |
0.00020197988 |
| 583 |
FAQ: Questions Asked Frequently |
2016 |
PODS |
0.00019717214 |
| 727 |
On Synopses for Distinct-Value Estimation Under Multiset Operations |
2007 |
SIGMOD |
0.00017508726 |
| 1,105 |
Cardinality Estimation Done Right: Index-Based Join Sampling |
2017 |
CIDR |
0.00013990395 |
| 1,532 |
Data Management in Machine Learning: Challenges, Techniques, and Systems |
2017 |
SIGMOD |
0.00011472681 |
| 1,619 |
Adaptive Optimization of Very Large Join Queries |
2018 |
SIGMOD |
0.00011111678 |
| 1,683 |
Cardinality Estimation: An Experimental Survey |
2018 |
VLDB |
0.00010922679 |
| 1,758 |
Sampling-Based Query Re-Optimization |
2016 |
SIGMOD |
0.00010655546 |
| 1,967 |
Compressed Linear Algebra for Large-Scale Machine Learning |
2016 |
VLDB |
9.9131712e-05 |
| 2,255 |
LINVIEW: Incremental View Maintenance for Complex Analytical Queries |
2014 |
SIGMOD |
9.1884983e-05 |
| 2,377 |
CS2: A New Database Synopsis for Query Estimation |
2013 |
SIGMOD |
8.9402115e-05 |
| 2,667 |
Cumulon: Optimizing Statistical Data Analysis in the Cloud |
2013 |
SIGMOD |
8.3413995e-05 |
| 3,013 |
Cardinality Estimation Using Sample Views with Quality Assurance |
2007 |
SIGMOD |
7.7137441e-05 |
| 3,702 |
Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates |
2019 |
CIDR |
6.8295759e-05 |
| 3,918 |
On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML |
2018 |
VLDB |
6.6315176e-05 |
| 4,505 |
SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning |
2017 |
CIDR |
6.1327108e-05 |
| 4,802 |
Resource Elasticity for Large-Scale Machine Learning |
2015 |
SIGMOD |
5.9114415e-05 |
| 5,535 |
Lightweight Cardinality Estimation in LSM-based Systems |
2018 |
SIGMOD |
5.4539235e-05 |
| 8,893 |
Histograms Reloaded: The Merits of Bucket Diversity |
2010 |
SIGMOD |
4.4275272e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 2,848 |
Exploiting Matrix Dependency for Efficient Distributed Matrix Computation |
2015 |
SIGMOD |
8.0208832e-05 |
| 6,191 |
Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra |
2021 |
SIGMOD |
5.1642282e-05 |
| 6,085 |
Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix |
2021 |
SIGMOD |
5.2195267e-05 |
| 8,657 |
Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices |
2022 |
VLDB |
4.4730648e-05 |
| 8,786 |
AWARE: Workload-aware, Redundancy-exploiting Linear Algebra |
2023 |
SIGMOD |
4.4521262e-05 |
| 1,967 |
Compressed Linear Algebra for Large-Scale Machine Learning |
2016 |
VLDB |
9.9131712e-05 |
| 13,150 |
STile: Searching Hybrid Sparse Formats for Sparse Deep Learning Operators Automatically |
2024 |
SIGMOD |
- |
| 5,487 |
SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra |
2020 |
VLDB |
5.4791501e-05 |
| 11,168 |
Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation |
2023 |
PODS |
4.1945683e-05 |
| 9,670 |
On Efficient Large Sparse Matrix Chain Multiplication |
2024 |
SIGMOD |
4.3066148e-05 |