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
5728
Venue
SIGMOD
Year
2019
Pagerank
6.7178579e-05
Overall Rank
4,409 | 69.76%
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 11 of 11 citing papers.

Rank Citing Paper Year Venue Pagerank
1,756 SystemDS: A Declarative Machine Learning System for the End-to-End Data Science Lifecycle 2020 CIDR 9.8172465e-05
6,046 Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra 2021 SIGMOD 5.9956597e-05
6,538 UPLIFT: Parallelization Strategies for Feature Transformations in Machine Learning Workloads 2022 VLDB 5.8477764e-05
7,256 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.6625146e-05
8,794 AWARE: Workload-aware, Redundancy-exploiting Linear Algebra 2023 SIGMOD 5.370464e-05
8,999 HADAD: A Lightweight Approach for Optimizing Hybrid Complex Analytics Queries 2021 SIGMOD 5.3354529e-05
9,766 On Efficient Large Sparse Matrix Chain Multiplication 2024 SIGMOD 5.2214067e-05
10,514 Automated Tensor-Relational Decomposition for Large-Scale Sparse Tensor Computation 2026 VLDB 5.093636e-05
10,589 Morphing-based Compression for Data-centric ML Pipelines 2026 VLDB 5.093636e-05
11,537 Redundancy Elimination in Distributed Matrix Computation 2022 SIGMOD 5.093636e-05
11,561 Givens QR Decomposition over Relational Databases 2022 SIGMOD 5.093636e-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
75 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00037277061
89 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00035031529
288 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00022296371
358 FAQ: Questions Asked Frequently 2016 PODS 0.00020243592
415 SystemML: Declarative Machine Learning on Spark 2016 VLDB 0.0001888524
482 An Optimal Algorithm for the Distinct Elements Problem 2010 PODS 0.00017772185
689 On Synopses for Distinct-Value Estimation Under Multiset Operations 2007 SIGMOD 0.00014940023
694 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014911698
1,250 Data Management in Machine Learning: Challenges, Techniques, and Systems 2017 SIGMOD 0.00011485301
1,256 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00011457194
1,286 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011320736
1,516 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.00010520885
1,644 Compressed Linear Algebra for Large-Scale Machine Learning 2016 VLDB 0.00010132912
1,893 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.5269935e-05
2,059 LINVIEW: Incremental View Maintenance for Complex Analytical Queries 2014 SIGMOD 9.2471145e-05
2,217 Cumulon: Optimizing Statistical Data Analysis in the Cloud 2013 SIGMOD 8.9332438e-05
2,404 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 8.6225576e-05
3,205 On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML 2018 VLDB 7.6386536e-05
3,215 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 7.6324234e-05
3,284 SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning 2017 CIDR 7.5663058e-05
4,049 Resource Elasticity for Large-Scale Machine Learning 2015 SIGMOD 6.9369379e-05
4,945 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.4321265e-05
8,998 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 5.3355988e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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