DBScholar

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
h92fc2f9072c44bab
Venue
SIGMOD
Year
2019
Pagerank
6.6595681e-05
Overall Rank
4,330 | 70.89%
DOI
10.1145/3299869.3319854

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{sommer_sigmod19,
        title = {{MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions}},
        author = {Sommer, Johanna and Boehm, Matthias and Evfimievski, Alexandre V. and Reinwald, Berthold and Haas, Peter J.},
        series = {{SIGMOD} '19},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3299869.3319854},
        url = {https://dl.acm.org/doi/10.1145/3299869.3319854},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank Citing Paper Year Venue Pagerank
1,668 SystemDS: A Declarative Machine Learning System for the End-to-End Data Science Lifecycle 2020 CIDR 9.9371612e-05
6,169 Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra 2021 SIGMOD 5.8624857e-05
6,662 UPLIFT: Parallelization Strategies for Feature Transformations in Machine Learning Workloads 2022 VLDB 5.7171651e-05
7,364 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.5418075e-05
8,384 AWARE: Workload-aware, Redundancy-exploiting Linear Algebra 2023 SIGMOD 5.3421754e-05
9,157 HADAD: A Lightweight Approach for Optimizing Hybrid Complex Analytics Queries 2021 SIGMOD 5.2169683e-05
9,944 On Efficient Large Sparse Matrix Chain Multiplication 2024 SIGMOD 5.1042523e-05
10,699 Automated Tensor-Relational Decomposition for Large-Scale Sparse Tensor Computation 2026 VLDB 4.9793485e-05
10,898 stratum: A System Infrastructure for Massive Agent-Centric ML Workloads 2026 VLDB 4.9793485e-05
10,945 Morphing-based Compression for Data-centric ML Pipelines 2026 VLDB 4.9793485e-05
11,846 Redundancy Elimination in Distributed Matrix Computation 2022 SIGMOD 4.9793485e-05
11,870 Givens QR Decomposition over Relational Databases 2022 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

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
77 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036828234
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.0003475226
295 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00021914399
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020020639
415 SystemML: Declarative Machine Learning on Spark 2016 VLDB 0.0001865959
494 An Optimal Algorithm for the Distinct Elements Problem 2010 PODS 0.00017387321
688 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014753664
707 On Synopses for Distinct-Value Estimation Under Multiset Operations 2007 SIGMOD 0.00014640173
1,186 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.0001160797
1,255 Data Management in Machine Learning: Challenges, Techniques, and Systems 2017 SIGMOD 0.00011325762
1,257 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00011310561
1,536 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.00010327422
1,614 Compressed Linear Algebra for Large-Scale Machine Learning 2016 VLDB 0.00010071891
1,891 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4184294e-05
2,087 LINVIEW: Incremental View Maintenance for Complex Analytical Queries 2014 SIGMOD 9.068879e-05
2,247 Cumulon: Optimizing Statistical Data Analysis in the Cloud 2013 SIGMOD 8.7585767e-05
2,433 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 8.4766785e-05
3,101 On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML 2018 VLDB 7.649219e-05
3,131 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 7.6141006e-05
3,330 SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning 2017 CIDR 7.4173693e-05
4,116 Resource Elasticity for Large-Scale Machine Learning 2015 SIGMOD 6.7961306e-05
5,044 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.30014e-05
9,142 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 5.220581e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,723 Exploiting Matrix Dependency for Efficient Distributed Matrix Computation 2015 SIGMOD
2 6,169 Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra 2021 SIGMOD
3 5,910 Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix 2021 SIGMOD
4 8,773 Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices 2022 VLDB
5 8,384 AWARE: Workload-aware, Redundancy-exploiting Linear Algebra 2023 SIGMOD
6 1,614 Compressed Linear Algebra for Large-Scale Machine Learning 2016 VLDB
7 13,671 STile: Searching Hybrid Sparse Formats for Sparse Deep Learning Operators Automatically 2024 SIGMOD
8 4,974 SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra 2020 VLDB
9 11,690 Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation 2023 PODS
10 9,944 On Efficient Large Sparse Matrix Chain Multiplication 2024 SIGMOD