Back to papers
Two-Level Sampling for Join Size Estimation
Summary: Two-Level Sampling for Join Size Estimation proposes a one-pass, hybrid method for join cardinality. It leverages l_k-norms and heavy hitters to deliver accurate estimates for PK–FK, many-to-many, and complex joins with simple implementation.
(summarized by gpt-5-nano on Feb 09 2026)
Paper ID
5349
Venue
SIGMOD
Year
2017
Pagerank
0.00010070362
Overall Rank
1,664 | 88.59%
DOI
10.1145/3035918.3035921
Incoming Non-self Citations Over Time
Authors
1.
Yu Chen
(Hong Kong University of Science and Technology)
2.
Ke Yi
(Hong Kong University of Science and Technology)
BibTeX Citation
@inproceedings{chen_sigmod17,
title = {{Two-Level Sampling for Join Size Estimation}},
author = {Chen, Yu and Yi, Ke},
series = {{SIGMOD} '17},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3035918.3035921},
url = {https://dl.acm.org/doi/10.1145/3035918.3035921},
year = {2017}
}
Incoming Citations (Sorted by Pagerank)
Showing 28 of 28 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
84
Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019
CIDR
0.00035838391
1,499
Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019
SIGMOD
0.00010564536
2,940
G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020
SIGMOD
7.9381573e-05
3,162
Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020
VLDB
7.6785856e-05
3,228
Correlation Sketches for Approximate Join-Correlation Queries 2021
SIGMOD
7.6215176e-05
3,366
AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics 2018
SIGMOD
7.4748604e-05
3,453
On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023
PODS
7.4004131e-05
3,959
Simplicity Done Right for Join Ordering 2021
CIDR
6.9879431e-05
4,349
ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024
VLDB
6.7504619e-05
4,926
Adaptive Sampling for Rapidly Matching Histograms 2018
VLDB
6.4428362e-05
5,277
FASTgres: Making Learned Query Optimizer Hinting Effective 2023
VLDB
6.2859099e-05
5,743
Joins on Samples: A Theoretical Guide for Practitioners 2020
VLDB
6.1025457e-05
6,434
Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025
SIGMOD
5.8799421e-05
7,256
Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021
SIGMOD
5.6625146e-05
8,183
alpha to omega: The Greek Alphabet of Sampling 2020
CIDR
5.4714466e-05
8,252
Sampling Methods for Inner Product Sketching 2024
VLDB
5.4574671e-05
8,413
Conditional Cuckoo Filters 2021
SIGMOD
5.4306049e-05
8,492
ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation 2023
VLDB
5.4145838e-05
8,509
Hypothetical Reasoning via Provenance Abstraction 2019
SIGMOD
5.4120069e-05
8,608
One Size Does Not Fit All: A Bandit-Based Sampler Combination Framework with Theoretical Guarantees 2022
SIGMOD
5.4024561e-05
10,438
CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026
SIGMOD
5.093636e-05
10,878
Evaluating Methods for Efficient Entity Count Estimation 2025
VLDB
5.093636e-05
10,891
Cardinality Estimation for Having-Clauses 2025
VLDB
5.093636e-05
11,059
Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects 2025
VLDB
5.093636e-05
11,091
LEAP: A Low-cost Spark SQL Query Optimizer using Pairwise Comparison 2025
VLDB
5.093636e-05
11,194
Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024
SIGMOD
5.093636e-05
11,204
SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs 2024
SIGMOD
5.093636e-05
11,902
Tighter Upper Bounds for Join Cardinality Estimates 2018
SIGMOD
5.093636e-05
Outgoing Citations (Sorted by Pagerank)
Showing 12 of 12 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Semantically Similar Papers