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.6564176e-05
Overall Rank
4,330 | 70.90%
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,669 SystemDS: A Declarative Machine Learning System for the End-to-End Data Science Lifecycle 2020 CIDR 9.9324573e-05
6,171 Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra 2021 SIGMOD 5.8597104e-05
6,666 UPLIFT: Parallelization Strategies for Feature Transformations in Machine Learning Workloads 2022 VLDB 5.7144587e-05
7,368 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.5392867e-05
8,389 AWARE: Workload-aware, Redundancy-exploiting Linear Algebra 2023 SIGMOD 5.3396465e-05
9,166 HADAD: A Lightweight Approach for Optimizing Hybrid Complex Analytics Queries 2021 SIGMOD 5.2144986e-05
9,952 On Efficient Large Sparse Matrix Chain Multiplication 2024 SIGMOD 5.101836e-05
10,709 Automated Tensor-Relational Decomposition for Large-Scale Sparse Tensor Computation 2026 VLDB 4.9769913e-05
10,907 stratum: A System Infrastructure for Massive Agent-Centric ML Workloads 2026 VLDB 4.9769913e-05
10,954 Morphing-based Compression for Data-centric ML Pipelines 2026 VLDB 4.9769913e-05
11,852 Redundancy Elimination in Distributed Matrix Computation 2022 SIGMOD 4.9769913e-05
11,876 Givens QR Decomposition over Relational Databases 2022 SIGMOD 4.9769913e-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.00036817139
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00034748721
295 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00021908194
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020013731
416 SystemML: Declarative Machine Learning on Spark 2016 VLDB 0.00018650998
494 An Optimal Algorithm for the Distinct Elements Problem 2010 PODS 0.00017379171
688 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014749318
707 On Synopses for Distinct-Value Estimation Under Multiset Operations 2007 SIGMOD 0.00014633741
1,185 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011607329
1,223 Data Management in Machine Learning: Challenges, Techniques, and Systems 2017 SIGMOD 0.00011468426
1,258 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00011308863
1,537 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.00010324934
1,614 Compressed Linear Algebra for Large-Scale Machine Learning 2016 VLDB 0.00010067153
1,892 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4150583e-05
2,087 LINVIEW: Incremental View Maintenance for Complex Analytical Queries 2014 SIGMOD 9.0661817e-05
2,249 Cumulon: Optimizing Statistical Data Analysis in the Cloud 2013 SIGMOD 8.7544468e-05
2,432 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 8.4742372e-05
3,103 On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML 2018 VLDB 7.6456038e-05
3,132 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 7.6107287e-05
3,331 SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning 2017 CIDR 7.4138851e-05
4,117 Resource Elasticity for Large-Scale Machine Learning 2015 SIGMOD 6.7929814e-05
5,047 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.2972183e-05
9,151 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 5.2181099e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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