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
- 5667
- Venue
- SIGMOD
- Year
- 2019
- Pagerank
- 5.8861112e-05
- Overall Rank
- 4,835 | 66.40%
- 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.4905306e-05 |
| 6,194 |
Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra |
2021 |
SIGMOD |
5.1592984e-05 |
| 7,340 |
Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries |
2021 |
SIGMOD |
4.7526052e-05 |
| 8,515 |
UPLIFT: Parallelization Strategies for Feature Transformations in Machine Learning Workloads |
2022 |
VLDB |
4.4901466e-05 |
| 8,782 |
AWARE: Workload-aware, Redundancy-exploiting Linear Algebra |
2023 |
SIGMOD |
4.4478585e-05 |
| 8,981 |
HADAD: A Lightweight Approach for Optimizing Hybrid Complex Analytics Queries |
2021 |
SIGMOD |
4.4138435e-05 |
| 9,670 |
On Efficient Large Sparse Matrix Chain Multiplication |
2024 |
SIGMOD |
4.3024878e-05 |
| 10,226 |
Automated Tensor-Relational Decomposition for Large-Scale Sparse Tensor Computation |
2026 |
VLDB |
4.1905499e-05 |
| 10,303 |
Morphing-based Compression for Data-centric ML Pipelines |
2026 |
VLDB |
4.1905499e-05 |
| 11,341 |
Redundancy Elimination in Distributed Matrix Computation |
2022 |
SIGMOD |
4.1905499e-05 |
| 11,365 |
Givens QR Decomposition over Relational Databases |
2022 |
SIGMOD |
4.1905499e-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 |
| 60 |
Sampling-Based Estimation of the Number of Distinct Values of an Attribute |
1995 |
VLDB |
0.00064450997 |
| 100 |
On the Propagation of Errors in the Size of Join Results |
1991 |
SIGMOD |
0.00050033475 |
| 380 |
Towards Estimation Error Guarantees for Distinct Values |
2000 |
PODS |
0.00024943236 |
| 449 |
An Optimal Algorithm for the Distinct Elements Problem |
2010 |
PODS |
0.00022914472 |
| 557 |
SystemML: Declarative Machine Learning on Spark |
2016 |
VLDB |
0.00020186115 |
| 564 |
FAQ: Questions Asked Frequently |
2016 |
PODS |
0.00020002796 |
| 737 |
On Synopses for Distinct-Value Estimation Under Multiset Operations |
2007 |
SIGMOD |
0.00017377393 |
| 1,104 |
Cardinality Estimation Done Right: Index-Based Join Sampling |
2017 |
CIDR |
0.0001398479 |
| 1,534 |
Data Management in Machine Learning: Challenges, Techniques, and Systems |
2017 |
SIGMOD |
0.00011462072 |
| 1,621 |
Adaptive Optimization of Very Large Join Queries |
2018 |
SIGMOD |
0.00011105663 |
| 1,683 |
Cardinality Estimation: An Experimental Survey |
2018 |
VLDB |
0.0001091276 |
| 1,756 |
Sampling-Based Query Re-Optimization |
2016 |
SIGMOD |
0.00010659753 |
| 1,970 |
Compressed Linear Algebra for Large-Scale Machine Learning |
2016 |
VLDB |
9.9024431e-05 |
| 2,260 |
LINVIEW: Incremental View Maintenance for Complex Analytical Queries |
2014 |
SIGMOD |
9.1771829e-05 |
| 2,369 |
CS2: A New Database Synopsis for Query Estimation |
2013 |
SIGMOD |
8.9462051e-05 |
| 2,672 |
Cumulon: Optimizing Statistical Data Analysis in the Cloud |
2013 |
SIGMOD |
8.3334428e-05 |
| 3,013 |
Cardinality Estimation Using Sample Views with Quality Assurance |
2007 |
SIGMOD |
7.7082045e-05 |
| 3,706 |
Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates |
2019 |
CIDR |
6.8232992e-05 |
| 3,920 |
On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML |
2018 |
VLDB |
6.6246708e-05 |
| 4,508 |
SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning |
2017 |
CIDR |
6.1261819e-05 |
| 4,807 |
Resource Elasticity for Large-Scale Machine Learning |
2015 |
SIGMOD |
5.9045148e-05 |
| 5,543 |
Lightweight Cardinality Estimation in LSM-based Systems |
2018 |
SIGMOD |
5.4486922e-05 |
| 8,893 |
Histograms Reloaded: The Merits of Bucket Diversity |
2010 |
SIGMOD |
4.4232868e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 2,855 |
Exploiting Matrix Dependency for Efficient Distributed Matrix Computation |
2015 |
SIGMOD |
8.013421e-05 |
| 6,194 |
Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra |
2021 |
SIGMOD |
5.1592984e-05 |
| 6,089 |
Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix |
2021 |
SIGMOD |
5.2145151e-05 |
| 8,655 |
Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices |
2022 |
VLDB |
4.4687769e-05 |
| 8,782 |
AWARE: Workload-aware, Redundancy-exploiting Linear Algebra |
2023 |
SIGMOD |
4.4478585e-05 |
| 1,970 |
Compressed Linear Algebra for Large-Scale Machine Learning |
2016 |
VLDB |
9.9024431e-05 |
| 13,164 |
STile: Searching Hybrid Sparse Formats for Sparse Deep Learning Operators Automatically |
2024 |
SIGMOD |
- |
| 5,497 |
SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra |
2020 |
VLDB |
5.4741034e-05 |
| 11,171 |
Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation |
2023 |
PODS |
4.1905499e-05 |
| 9,670 |
On Efficient Large Sparse Matrix Chain Multiplication |
2024 |
SIGMOD |
4.3024878e-05 |