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.8821344e-05
Overall Rank
1,681 | 88.74%
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.00035920657
1,444
Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019
SIGMOD
0.00010616242
2,829
G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020
SIGMOD
7.9469964e-05
3,093
Correlation Sketches for Approximate Join-Correlation Queries 2021
SIGMOD
7.6378811e-05
3,212
Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020
VLDB
7.5145409e-05
3,435
AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics 2018
SIGMOD
7.2845431e-05
3,502
On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023
PODS
7.2308675e-05
3,995
Simplicity Done Right for Join Ordering 2021
CIDR
6.8530469e-05
4,315
ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024
VLDB
6.6545412e-05
5,049
Adaptive Sampling for Rapidly Matching Histograms 2018
VLDB
6.287033e-05
5,245
FASTgres: Making Learned Query Optimizer Hinting Effective 2023
VLDB
6.1995935e-05
5,841
Joins on Samples: A Theoretical Guide for Practitioners 2020
VLDB
5.9569427e-05
5,911
Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025
SIGMOD
5.9338021e-05
7,252
Hypothetical Reasoning via Provenance Abstraction 2019
SIGMOD
5.5583413e-05
7,387
Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021
SIGMOD
5.5212177e-05
8,363
alpha to omega: The Greek Alphabet of Sampling 2020
CIDR
5.3305234e-05
8,446
Sampling Methods for Inner Product Sketching 2024
VLDB
5.3148581e-05
8,604
Conditional Cuckoo Filters 2021
SIGMOD
5.2899825e-05
8,685
ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation 2023
VLDB
5.2730954e-05
8,790
One Size Does Not Fit All: A Bandit-Based Sampler Combination Framework with Theoretical Guarantees 2022
SIGMOD
5.2633515e-05
9,952
Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects 2025
VLDB
5.0910746e-05
10,699
CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026
SIGMOD
4.9605343e-05
11,344
Evaluating Methods for Efficient Entity Count Estimation 2025
VLDB
4.9605343e-05
11,353
Cardinality Estimation for Having-Clauses 2025
VLDB
4.9605343e-05
11,501
LEAP: A Low-cost Spark SQL Query Optimizer using Pairwise Comparison 2025
VLDB
4.9605343e-05
11,591
Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024
SIGMOD
4.9605343e-05
11,600
SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs 2024
SIGMOD
4.9605343e-05
12,251
Tighter Upper Bounds for Join Cardinality Estimates 2018
SIGMOD
4.9605343e-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