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.64569e-05
Overall Rank
4,329 | 70.99%
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,616 SystemDS: A Declarative Machine Learning System for the End-to-End Data Science Lifecycle 2020 CIDR 0.00010048776
5,505 Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra 2021 SIGMOD 6.0884328e-05
6,679 UPLIFT: Parallelization Strategies for Feature Transformations in Machine Learning Workloads 2022 VLDB 5.6956362e-05
7,387 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.5212177e-05
8,407 AWARE: Workload-aware, Redundancy-exploiting Linear Algebra 2023 SIGMOD 5.3219903e-05
9,190 HADAD: A Lightweight Approach for Optimizing Hybrid Complex Analytics Queries 2021 SIGMOD 5.1972757e-05
9,985 On Efficient Large Sparse Matrix Chain Multiplication 2024 SIGMOD 5.0849662e-05
10,770 Automated Tensor-Relational Decomposition for Large-Scale Sparse Tensor Computation 2026 VLDB 4.9605343e-05
10,968 stratum: A System Infrastructure for Massive Agent-Centric ML Workloads 2026 VLDB 4.9605343e-05
11,015 Morphing-based Compression for Data-centric ML Pipelines 2026 VLDB 4.9605343e-05
11,896 Redundancy Elimination in Distributed Matrix Computation 2022 SIGMOD 4.9605343e-05
11,920 Givens QR Decomposition over Relational Databases 2022 SIGMOD 4.9605343e-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
78 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036725074
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00034691614
296 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00021874894
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020048899
415 SystemML: Declarative Machine Learning on Spark 2016 VLDB 0.00018619173
495 An Optimal Algorithm for the Distinct Elements Problem 2010 PODS 0.00017347522
689 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014725904
711 On Synopses for Distinct-Value Estimation Under Multiset Operations 2007 SIGMOD 0.00014589586
1,185 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011586181
1,226 Data Management in Machine Learning: Challenges, Techniques, and Systems 2017 SIGMOD 0.00011432354
1,261 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00011289724
1,534 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.00010309919
1,615 Compressed Linear Algebra for Large-Scale Machine Learning 2016 VLDB 0.00010054378
1,896 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4010932e-05
2,083 LINVIEW: Incremental View Maintenance for Complex Analytical Queries 2014 SIGMOD 9.0563677e-05
2,250 Cumulon: Optimizing Statistical Data Analysis in the Cloud 2013 SIGMOD 8.7477605e-05
2,438 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 8.4532693e-05
3,104 On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML 2018 VLDB 7.6281929e-05
3,136 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 7.5902303e-05
3,331 SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning 2017 CIDR 7.4065701e-05
4,134 Resource Elasticity for Large-Scale Machine Learning 2015 SIGMOD 6.7721426e-05
5,056 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.282339e-05
9,173 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 5.2011875e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 5,505 Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra 2021 SIGMOD
2 10,404 NeutronSparse: Coordinating Heterogeneous Engines for Sparse Matrix Multiplication on NPUs 2027 SIGMOD
3 5,929 Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix 2021 SIGMOD
4 8,799 Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices 2022 VLDB
5 8,407 AWARE: Workload-aware, Redundancy-exploiting Linear Algebra 2023 SIGMOD
6 1,615 Compressed Linear Algebra for Large-Scale Machine Learning 2016 VLDB
7 13,716 STile: Searching Hybrid Sparse Formats for Sparse Deep Learning Operators Automatically 2024 SIGMOD
8 4,505 SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra 2020 VLDB
9 11,742 Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation 2023 PODS
10 9,985 On Efficient Large Sparse Matrix Chain Multiplication 2024 SIGMOD