DBScholar

Back to papers

On Synopses for Distinct-Value Estimation Under Multiset Operations

Summary: DV estimation via scalable synopsis store: partition synopses computed in parallel, combinable for unions, intersections, and differences. Order-statistics-based estimators are unbiased; a Cohen-driven limit theorem sizes synopses, reducing cost and boosting accuracy. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
3913
Venue
SIGMOD
Year
2007
Pagerank
0.00014940023
Overall Rank
689 | 95.28%
DOI
10.1145/1247480.1247504

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{beyer_sigmod07,
        title = {{On Synopses for Distinct-Value Estimation Under Multiset Operations}},
        author = {Beyer, Kevin and Haas, Peter J. and Reinwald, Berthold and Sismanis, Yannis and Gemulla, Rainer},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247504},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247504},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 34 of 34 citing papers.

Rank Citing Paper Year Venue Pagerank
482 An Optimal Algorithm for the Distinct Elements Problem 2010 PODS 0.00017772185
819 Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters 2016 SIGMOD 0.00013815639
1,516 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.00010520885
1,521 On Multi-Column Foreign Key Discovery 2010 VLDB 0.00010506299
1,644 Compressed Linear Algebra for Large-Scale Machine Learning 2016 VLDB 0.00010132912
1,736 A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data 2014 SIGMOD 9.8984415e-05
2,150 Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries 2008 VLDB 9.081101e-05
2,308 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.7738996e-05
2,753 Sampling Time-Based Sliding Windows in Bounded Space 2008 SIGMOD 8.1647557e-05
3,228 Correlation Sketches for Approximate Join-Correlation Queries 2021 SIGMOD 7.6215176e-05
3,467 Multidimensional Content eXploration 2008 VLDB 7.3898968e-05
3,481 Tighter Estimation using Bottom k Sketches 2008 VLDB 7.376137e-05
4,285 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.7812351e-05
4,409 MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions 2019 SIGMOD 6.7178579e-05
4,481 Dynamically Optimizing Queries over Large Scale Data Platforms 2014 SIGMOD 6.6754521e-05
5,257 Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches 2018 VLDB 6.2971456e-05
5,385 Randomized Error Removal for Online Spread Estimation in Data Streaming 2021 VLDB 6.2369655e-05
5,792 Pre-training Summarization Models of Structured Datasets for Cardinality Estimation 2022 VLDB 6.0871213e-05
5,995 Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments 2009 VLDB 6.0155431e-05
6,538 UPLIFT: Parallelization Strategies for Feature Transformations in Machine Learning Workloads 2022 VLDB 5.8477764e-05
7,143 Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries 2020 PODS 5.6915726e-05
7,256 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.6625146e-05
7,363 Adaptive Log Compression for Massive Log Data 2013 SIGMOD 5.6333834e-05
7,377 Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g 2008 SIGMOD 5.6297042e-05
7,433 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 5.6197531e-05
8,252 Sampling Methods for Inner Product Sketching 2024 VLDB 5.4574671e-05
8,494 POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance 2024 VLDB 5.4142129e-05
10,651 Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces 2025 PODS 5.093636e-05
10,774 PLM4NDV: Minimizing Data Access for Number of Distinct Values Estimation with Pre-trained Language Models 2025 SIGMOD 5.093636e-05
10,891 Cardinality Estimation for Having-Clauses 2025 VLDB 5.093636e-05
11,374 Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation 2023 PODS 5.093636e-05
11,612 No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing 2022 VLDB 5.093636e-05
12,034 Streaming Algorithms for Robust Distinct Elements 2016 SIGMOD 5.093636e-05
12,362 Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information 2011 PODS 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
1 Access Path Selection in a Relational Database Management System 1979 SIGMOD 0.0024089429
255 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00023174541
257 The History of Histograms (abridged) 2003 VLDB 0.00023154793
288 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00022296371
432 Mining Database Structure; Or, How to Build a Data Quality Browser 2002 SIGMOD 0.00018572055
654 Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies 1996 VLDB 0.0001527187
2,197 Multi-Dimensional Clustering: A New Data Layout Scheme in DB2 2003 SIGMOD 8.9684812e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 11,503 Bayesian Sketches for Volume Estimation in Data Streams 2023 VLDB
2 842 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB
3 2,878 Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation 2018 SIGMOD
4 12,362 Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information 2011 PODS
5 1,516 Cardinality Estimation: An Experimental Survey 2018 VLDB
6 75 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB
7 12,724 Join-Distinct Aggregate Estimation over Update Streams 2005 PODS
8 255 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB
9 288 Towards Estimation Error Guarantees for Distinct Values 2000 PODS
10 5,998 Approximate Distinct Counts for Billions of Datasets 2019 SIGMOD