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.9088372e-05
Overall Rank
1,678 | 88.72%
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.00035864347
1,465
Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019
SIGMOD
0.00010576304
2,824
G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020
SIGMOD
7.9698957e-05
3,090
Correlation Sketches for Approximate Join-Correlation Queries 2021
SIGMOD
7.6584982e-05
3,210
Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020
VLDB
7.5363533e-05
3,424
AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics 2018
SIGMOD
7.3117029e-05
3,494
On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023
PODS
7.2582926e-05
3,982
Simplicity Done Right for Join Ordering 2021
CIDR
6.8750228e-05
4,311
ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024
VLDB
6.6727978e-05
5,021
Adaptive Sampling for Rapidly Matching Histograms 2018
VLDB
6.3106761e-05
5,241
FASTgres: Making Learned Query Optimizer Hinting Effective 2023
VLDB
6.2154384e-05
5,831
Joins on Samples: A Theoretical Guide for Practitioners 2020
VLDB
5.9782109e-05
5,902
Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025
SIGMOD
5.9536872e-05
7,234
Hypothetical Reasoning via Provenance Abstraction 2019
SIGMOD
5.5792063e-05
7,364
Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021
SIGMOD
5.5418075e-05
8,347
alpha to omega: The Greek Alphabet of Sampling 2020
CIDR
5.350539e-05
8,421
Sampling Methods for Inner Product Sketching 2024
VLDB
5.3350162e-05
8,580
Conditional Cuckoo Filters 2021
SIGMOD
5.3100462e-05
8,659
ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation 2023
VLDB
5.2930951e-05
8,770
One Size Does Not Fit All: A Bandit-Based Sampler Combination Framework with Theoretical Guarantees 2022
SIGMOD
5.2812395e-05
9,910
Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects 2025
VLDB
5.1103839e-05
10,627
CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026
SIGMOD
4.9793485e-05
11,280
Evaluating Methods for Efficient Entity Count Estimation 2025
VLDB
4.9793485e-05
11,290
Cardinality Estimation for Having-Clauses 2025
VLDB
4.9793485e-05
11,443
LEAP: A Low-cost Spark SQL Query Optimizer using Pairwise Comparison 2025
VLDB
4.9793485e-05
11,536
Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024
SIGMOD
4.9793485e-05
11,545
SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs 2024
SIGMOD
4.9793485e-05
12,202
Tighter Upper Bounds for Join Cardinality Estimates 2018
SIGMOD
4.9793485e-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