Back to papers
Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries
Summary: Combines Count Sketch with convolution/cross-correlation to support AMS-style cardinality estimation for complex multi-way equi-joins, finally getting fast updates for multi-join sketches. Unbiased estimator with AMS-level error guarantees; orders-of-magnitude faster maintenance, often better accuracy.
(summarized by gpt-5.4-mini on May 24 2026)
- Paper ID
- 6895
- Venue
- SIGMOD
- Year
- 2024
- Pagerank
- 4.461508e-05
- Overall Rank
- 8,695 | 39.57%
- DOI
-
10.1145/3654932
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
Outgoing Citations (Sorted by Pagerank)
Showing 24 of 24 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 71 |
How Good Are Query Optimizers, Really? |
2016 |
VLDB |
0.00059446482 |
| 344 |
Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries |
2001 |
VLDB |
0.00026698826 |
| 454 |
An Overview of Query Optimization in Relational Systems |
1998 |
PODS |
0.00022796106 |
| 550 |
Tracking Join and Self-Join Sizes in Limited Storage |
1999 |
PODS |
0.00020346247 |
| 606 |
DeepDB: Learn from Data, not from Queries! |
2020 |
VLDB |
0.00019251186 |
| 627 |
Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors |
2009 |
VLDB |
0.00018959896 |
| 905 |
NeuroCard: One Cardinality Estimator for All Tables |
2021 |
VLDB |
0.00015423174 |
| 1,065 |
Processing Complex Aggregate Queries over Data Streams |
2002 |
SIGMOD |
0.00014344675 |
| 1,194 |
Join Size Estimation Subject to Filter Conditions |
2015 |
VLDB |
0.00013411666 |
| 1,394 |
Sketching Streams Through the Net: Distributed Approximate Query Tracking |
2005 |
VLDB |
0.00012218557 |
| 1,586 |
Augmented Sketch: Faster and More Accurate Stream Processing |
2016 |
SIGMOD |
0.00011245213 |
| 1,638 |
Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation |
2022 |
VLDB |
0.00011050093 |
| 2,143 |
Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities |
2019 |
SIGMOD |
9.4437798e-05 |
| 2,769 |
FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation |
2021 |
VLDB |
8.1512848e-05 |
| 3,176 |
Interactive Outlier Exploration in Big Data Streams |
2014 |
VLDB |
7.4380543e-05 |
| 4,437 |
TencentRec: Real-time Stream Recommendation in Practice |
2015 |
SIGMOD |
6.1825805e-05 |
| 5,188 |
Finding Hierarchical Heavy Hitters in Data Streams |
2003 |
VLDB |
5.635103e-05 |
| 5,377 |
Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams |
2017 |
VLDB |
5.5381456e-05 |
| 5,632 |
Complex Event Recognition in the Big Data Era |
2017 |
VLDB |
5.3993008e-05 |
| 5,886 |
COMPASS: Online Sketch-based Query Optimization for In-Memory Databases |
2021 |
SIGMOD |
5.2847297e-05 |
| 6,075 |
IBM InfoSphere Streams for Scalable, Real-Time, Intelligent Transportation Services |
2010 |
SIGMOD |
5.2210956e-05 |
| 9,022 |
STAR: A Distributed Stream Warehouse System for Spatial Data |
2020 |
SIGMOD |
4.4040354e-05 |
| 9,079 |
JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation |
2023 |
SIGMOD |
4.3956812e-05 |
| 9,761 |
TeRec: A Temporal Recommender System Over Tweet Stream |
2013 |
VLDB |
4.2833359e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 2,971 |
Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models |
2017 |
VLDB |
7.7935535e-05 |
| 1,194 |
Join Size Estimation Subject to Filter Conditions |
2015 |
VLDB |
0.00013411666 |
| 2,143 |
Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities |
2019 |
SIGMOD |
9.4437798e-05 |
| 9,079 |
JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation |
2023 |
SIGMOD |
4.3956812e-05 |
| 1,065 |
Processing Complex Aggregate Queries over Data Streams |
2002 |
SIGMOD |
0.00014344675 |
| 12,484 |
A Simple and Efficient Estimation Method for Stream Expression Cardinalities |
2007 |
VLDB |
4.1905499e-05 |
| 12,540 |
Join-Distinct Aggregate Estimation over Update Streams |
2005 |
PODS |
4.1905499e-05 |
| 3,706 |
Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates |
2019 |
CIDR |
6.8232992e-05 |
| 6,243 |
Approximate Distinct Counts for Billions of Datasets |
2019 |
SIGMOD |
5.1348218e-05 |
| 9,628 |
Approximate Sketches |
2024 |
SIGMOD |
4.3102157e-05 |