Database Paper Browser

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
3852
Venue
SIGMOD
Year
2007
Pagerank
0.00017377393
Overall Rank
737 | 94.88%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 34 of 34 citing papers.

Rank Citing Paper Year Venue Pagerank
449 An Optimal Algorithm for the Distinct Elements Problem 2010 PODS 0.00022914472
1,320 Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters 2016 SIGMOD 0.00012606067
1,661 On Multi-Column Foreign Key Discovery 2010 VLDB 0.00010967185
1,683 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.0001091276
1,970 Compressed Linear Algebra for Large-Scale Machine Learning 2016 VLDB 9.9024431e-05
2,177 A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data 2014 SIGMOD 9.371335e-05
2,442 Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries 2008 VLDB 8.8067249e-05
2,779 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.1314377e-05
2,881 Sampling Time-Based Sliding Windows in Bounded Space 2008 SIGMOD 7.9671512e-05
3,261 Multidimensional Content eXploration 2008 VLDB 7.3088095e-05
3,827 Correlation Sketches for Approximate Join-Correlation Queries 2021 SIGMOD 6.7195959e-05
3,930 Tighter Estimation using Bottom-k Sketches 2008 VLDB 6.6195837e-05
3,989 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.5545373e-05
4,835 MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions 2019 SIGMOD 5.8861112e-05
4,912 Randomized Error Removal for Online Spread Estimation in Data Streaming 2021 VLDB 5.8342232e-05
5,012 Dynamically Optimizing Queries over Large Scale Data Platforms 2014 SIGMOD 5.7543101e-05
5,371 Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches 2018 VLDB 5.5424564e-05
5,423 Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments 2009 VLDB 5.5143276e-05
6,365 Pre-training Summarization Models of Structured Datasets for Cardinality Estimation 2022 VLDB 5.0892829e-05
7,117 Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries 2020 PODS 4.8205884e-05
7,340 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 4.7526052e-05
7,414 Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g 2008 SIGMOD 4.7312542e-05
7,432 Adaptive Log Compression for Massive Log Data 2013 SIGMOD 4.7272331e-05
7,644 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 4.6853638e-05
8,515 UPLIFT: Parallelization Strategies for Feature Transformations in Machine Learning Workloads 2022 VLDB 4.4901466e-05
9,191 POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance 2024 VLDB 4.3738237e-05
10,370 Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces 2025 PODS 4.1905499e-05
10,507 PLM4NDV: Minimizing Data Access for Number of Distinct Values Estimation with Pre-trained Language Models 2025 SIGMOD 4.1905499e-05
10,647 Cardinality Estimation for Having-Clauses 2025 VLDB 4.1905499e-05
11,028 Sampling Methods for Inner Product Sketching 2024 VLDB 4.1905499e-05
11,171 Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation 2023 PODS 4.1905499e-05
11,417 No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing 2022 VLDB 4.1905499e-05
11,841 Streaming Algorithms for Robust Distinct Elements 2016 SIGMOD 4.1905499e-05
12,174 Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information 2011 PODS 4.1905499e-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.0040465394
316 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00027981848
325 The History of Histograms (abridged) 2003 VLDB 0.00027398081
380 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00024943236
481 Mining Database Structure; Or, How to Build a Data Quality Browser 2002 SIGMOD 0.000221538
600 Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies 1996 VLDB 0.00019400653
2,092 Multi-Dimensional Clustering: A New Data Layout Scheme in DB2 2003 SIGMOD 9.5635999e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
11,306 Bayesian Sketches for Volume Estimation in Data Streams 2023 VLDB 4.1905499e-05
955 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00015069776
3,273 Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation 2018 SIGMOD 7.2899198e-05
12,174 Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information 2011 PODS 4.1905499e-05
1,683 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.0001091276
60 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00064450997
12,540 Join-Distinct Aggregate Estimation over Update Streams 2005 PODS 4.1905499e-05
316 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00027981848
380 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00024943236
6,243 Approximate Distinct Counts for Billions of Datasets 2019 SIGMOD 5.1348218e-05