Database Paper Browser

Back to papers

JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation

Summary: JoinSketch is a multi-component sketch for accurate, unbiased inner-product estimation in data management tasks (join size, stream similarity, cosine similarity) under skewed data. It provably achieves lower variance than AGMS/Fast-AGMS with ~10× accuracy gains and comparable throughput; code is open source. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
6584
Venue
SIGMOD
Year
2023
Pagerank
4.3998984e-05
Overall Rank
9,082 | 36.82%
DOI
10.1145/3588935

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank Citing Paper Year Venue Pagerank
8,697 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 4.4657888e-05
10,149 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 4.1945683e-05
10,981 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 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
99 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00050022914
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041786333
166 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00039361552
327 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00027308479
553 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00020272061
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,255 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00013024064
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,939 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00010025655
1,941 Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing 2018 SIGMOD 0.00010017745
2,142 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 9.4507296e-05
2,377 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 8.9402115e-05
3,271 Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation 2018 SIGMOD 7.2968732e-05
3,751 BurstSketch: Finding Bursts in Data Streams 2021 SIGMOD 6.7888099e-05
4,237 Statistical Analysis of Sketch Estimators 2007 SIGMOD 6.3333486e-05
5,880 COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021 SIGMOD 5.2898074e-05
6,593 Out of Many We are One: Measuring Item Batch with Clock-Sketch 2021 SIGMOD 4.9999287e-05
6,790 On-Off Sketch: A Fast and Accurate Sketch on Persistence 2021 VLDB 4.9251439e-05
8,250 Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation 2022 VLDB 4.5506131e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,141 ClusterJoin: A Similarity Joins Framework using Map-Reduce 2014 VLDB 7.4829448e-05
1,193 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00013414989
10,930 Similarity Joins of Sparse Features 2024 SIGMOD 4.1945683e-05
1,584 Augmented Sketch: Faster and More Accurate Stream Processing 2016 SIGMOD 0.00011255801
5,200 SetSketch: Filling the Gap between MinHash and HyperLogLog 2021 VLDB 5.6337581e-05
12,531 Join-Distinct Aggregate Estimation over Update Streams 2005 PODS 4.1945683e-05
11,025 Sampling Methods for Inner Product Sketching 2024 VLDB 4.1945683e-05
9,628 Approximate Sketches 2024 SIGMOD 4.3143499e-05
8,697 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 4.4657888e-05
11,168 Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation 2023 PODS 4.1945683e-05