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: 6585
Venue: SIGMOD
Year: 2023
Pagerank: 4.3956812e-05
Overall Rank: 9,079 | 36.91%
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,695	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD	4.461508e-05
10,149	CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations	2026	SIGMOD	4.1905499e-05
10,984	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.1905499e-05

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.00059446482
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041819767
168	Approximate Frequency Counts over Data Streams	2002	VLDB	0.0003915627
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
553	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00020272747
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,254	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00013018797
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,938	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025547
1,944	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	0.00010008078
2,143	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4437798e-05
2,369	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	8.9462051e-05
3,273	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	7.2899198e-05
3,755	BurstSketch: Finding Bursts in Data Streams	2021	SIGMOD	6.7822789e-05
4,239	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.3273184e-05
5,886	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	5.2847297e-05
6,594	Out of Many We are One: Measuring Item Batch with Clock-Sketch	2021	SIGMOD	4.9951304e-05
6,791	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	4.9204179e-05
8,246	Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation	2022	VLDB	4.5462498e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,139	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB	7.4915127e-05
1,194	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00013411666
1,586	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011245213
10,933	Similarity Joins of Sparse Features	2024	SIGMOD	4.1905499e-05
5,201	SetSketch: Filling the Gap between MinHash and HyperLogLog	2021	VLDB	5.6283451e-05
12,540	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS	4.1905499e-05
11,028	Sampling Methods for Inner Product Sketching	2024	VLDB	4.1905499e-05
9,628	Approximate Sketches	2024	SIGMOD	4.3102157e-05
8,695	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD	4.461508e-05
11,171	Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation	2023	PODS	4.1905499e-05