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
- 6894
- Venue
- SIGMOD
- Year
- 2024
- Pagerank
- 4.4657888e-05
- Overall Rank
- 8,697 | 39.50%
- 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.00059038975 |
| 344 |
Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries |
2001 |
VLDB |
0.00026702512 |
| 454 |
An Overview of Query Optimization in Relational Systems |
1998 |
PODS |
0.00022734812 |
| 549 |
Tracking Join and Self-Join Sizes in Limited Storage |
1999 |
PODS |
0.00020376603 |
| 608 |
DeepDB: Learn from Data, not from Queries! |
2020 |
VLDB |
0.00019235898 |
| 629 |
Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors |
2009 |
VLDB |
0.00018942366 |
| 910 |
NeuroCard: One Cardinality Estimator for All Tables |
2021 |
VLDB |
0.00015423056 |
| 1,064 |
Processing Complex Aggregate Queries over Data Streams |
2002 |
SIGMOD |
0.00014356481 |
| 1,193 |
Join Size Estimation Subject to Filter Conditions |
2015 |
VLDB |
0.00013414989 |
| 1,392 |
Sketching Streams Through the Net: Distributed Approximate Query Tracking |
2005 |
VLDB |
0.00012229045 |
| 1,584 |
Augmented Sketch: Faster and More Accurate Stream Processing |
2016 |
SIGMOD |
0.00011255801 |
| 1,638 |
Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation |
2022 |
VLDB |
0.00011049779 |
| 2,142 |
Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities |
2019 |
SIGMOD |
9.4507296e-05 |
| 2,762 |
FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation |
2021 |
VLDB |
8.1585394e-05 |
| 3,171 |
Interactive Outlier Exploration in Big Data Streams |
2014 |
VLDB |
7.4447236e-05 |
| 4,439 |
TencentRec: Real-time Stream Recommendation in Practice |
2015 |
SIGMOD |
6.1885354e-05 |
| 5,016 |
Finding Hierarchical Heavy Hitters in Data Streams |
2003 |
VLDB |
5.7580375e-05 |
| 5,369 |
Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams |
2017 |
VLDB |
5.5434712e-05 |
| 5,625 |
Complex Event Recognition in the Big Data Era |
2017 |
VLDB |
5.4044959e-05 |
| 5,880 |
COMPASS: Online Sketch-based Query Optimization for In-Memory Databases |
2021 |
SIGMOD |
5.2898074e-05 |
| 6,071 |
IBM InfoSphere Streams for Scalable, Real-Time, Intelligent Transportation Services |
2010 |
SIGMOD |
5.2261393e-05 |
| 9,019 |
STAR: A Distributed Stream Warehouse System for Spatial Data |
2020 |
SIGMOD |
4.4082606e-05 |
| 9,082 |
JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation |
2023 |
SIGMOD |
4.3998984e-05 |
| 9,759 |
TeRec: A Temporal Recommender System Over Tweet Stream |
2013 |
VLDB |
4.2874442e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 2,969 |
Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models |
2017 |
VLDB |
7.7974762e-05 |
| 1,193 |
Join Size Estimation Subject to Filter Conditions |
2015 |
VLDB |
0.00013414989 |
| 2,142 |
Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities |
2019 |
SIGMOD |
9.4507296e-05 |
| 9,082 |
JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation |
2023 |
SIGMOD |
4.3998984e-05 |
| 1,064 |
Processing Complex Aggregate Queries over Data Streams |
2002 |
SIGMOD |
0.00014356481 |
| 12,475 |
A Simple and Efficient Estimation Method for Stream Expression Cardinalities |
2007 |
VLDB |
4.1945683e-05 |
| 12,531 |
Join-Distinct Aggregate Estimation over Update Streams |
2005 |
PODS |
4.1945683e-05 |
| 3,702 |
Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates |
2019 |
CIDR |
6.8295759e-05 |
| 6,244 |
Approximate Distinct Counts for Billions of Datasets |
2019 |
SIGMOD |
5.139669e-05 |
| 9,628 |
Approximate Sketches |
2024 |
SIGMOD |
4.3143499e-05 |