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
h2527308ceaa47f6f
Venue
SIGMOD
Year
2017
Pagerank
9.9056116e-05
Overall Rank
1,678 | 88.73%
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
85
Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019
CIDR
0.00035876108
1,465
Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019
SIGMOD
0.00010572023
2,824
G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020
SIGMOD
7.9662478e-05
3,092
Correlation Sketches for Approximate Join-Correlation Queries 2021
SIGMOD
7.6548729e-05
3,208
Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020
VLDB
7.5355264e-05
3,424
AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics 2018
SIGMOD
7.3084429e-05
3,494
On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023
PODS
7.2548566e-05
3,983
Simplicity Done Right for Join Ordering 2021
CIDR
6.8722161e-05
4,299
ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024
VLDB
6.6766173e-05
5,025
Adaptive Sampling for Rapidly Matching Histograms 2018
VLDB
6.3078009e-05
5,236
FASTgres: Making Learned Query Optimizer Hinting Effective 2023
VLDB
6.2153504e-05
5,829
Joins on Samples: A Theoretical Guide for Practitioners 2020
VLDB
5.9764044e-05
5,895
Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025
SIGMOD
5.9534254e-05
7,235
Hypothetical Reasoning via Provenance Abstraction 2019
SIGMOD
5.5765963e-05
7,368
Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021
SIGMOD
5.5392867e-05
8,351
alpha to omega: The Greek Alphabet of Sampling 2020
CIDR
5.3480813e-05
8,430
Sampling Methods for Inner Product Sketching 2024
VLDB
5.3324907e-05
8,587
Conditional Cuckoo Filters 2021
SIGMOD
5.3075325e-05
8,667
ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation 2023
VLDB
5.2905894e-05
8,771
One Size Does Not Fit All: A Bandit-Based Sampler Combination Framework with Theoretical Guarantees 2022
SIGMOD
5.2808131e-05
9,917
Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects 2025
VLDB
5.1079647e-05
10,638
CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026
SIGMOD
4.9769913e-05
11,288
Evaluating Methods for Efficient Entity Count Estimation 2025
VLDB
4.9769913e-05
11,298
Cardinality Estimation for Having-Clauses 2025
VLDB
4.9769913e-05
11,449
LEAP: A Low-cost Spark SQL Query Optimizer using Pairwise Comparison 2025
VLDB
4.9769913e-05
11,542
Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024
SIGMOD
4.9769913e-05
11,551
SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs 2024
SIGMOD
4.9769913e-05
12,208
Tighter Upper Bounds for Join Cardinality Estimates 2018
SIGMOD
4.9769913e-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