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: 6646
Venue: SIGMOD
Year: 2023
Pagerank: 5.3293224e-05
Overall Rank: 9,027 | 38.07%
DOI: 10.1145/3588935

Incoming Non-self Citations Over Time

Authors

1. Feiyu Wang (Peking University)
2. Qizhi Chen (Peking University)
3. Yuanpeng Li (Peking University)
4. Tong Yang (Peking University; Peng Cheng Laboratory)
5. Yaofeng Tu (ZTE Corporation)
6. Lian Yu (Peking University)
7. Bin Cui (Peking University)

BibTeX Citation

@inproceedings{wang_sigmod23,
        title = {{JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation}},
        author = {Wang, Feiyu and Chen, Qizhi and Li, Yuanpeng and Yang, Tong and Tu, Yaofeng and Yu, Lian and Cui, Bin},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3588935},
        url = {https://dl.acm.org/doi/10.1145/3588935},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,747	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD	5.5529458e-05
10,438	CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations	2026	SIGMOD	5.093636e-05
11,194	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	5.093636e-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
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
89	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00035031529
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
730	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014539362
737	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00014490983
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702
1,045	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012440928
1,186	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00011764128
1,294	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011291308
1,320	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011166426
1,499	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010564536
1,893	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.5269935e-05
1,905	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	9.5034849e-05
2,878	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	8.0058242e-05
3,898	BurstSketch: Finding Bursts in Data Streams	2021	SIGMOD	7.0367583e-05
4,142	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.8764637e-05
4,900	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.4534715e-05
6,685	Out of Many We are One: Measuring Item Batch with Clock-Sketch	2021	SIGMOD	5.8034001e-05
7,036	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	5.7212447e-05
7,498	Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation	2022	VLDB	5.6031077e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,567	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB
2	737	Join Size Estimation Subject to Filter Conditions	2015	VLDB
3	1,294	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD
4	11,149	Similarity Joins of Sparse Features	2024	SIGMOD
5	5,864	SetSketch: Filling the Gap between MinHash and HyperLogLog	2021	VLDB
6	12,724	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS
7	8,252	Sampling Methods for Inner Product Sketching	2024	VLDB
8	9,724	Approximate Sketches	2024	SIGMOD
9	7,747	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD
10	11,374	Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation	2023	PODS