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: h92fc44027f819841
Venue: SIGMOD
Year: 2023
Pagerank: 5.4025473e-05
Overall Rank: 8,035 | 45.98%
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 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,566	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD	5.4952834e-05
10,627	CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations	2026	SIGMOD	4.9793485e-05
10,815	CRAFT: Corpus Relatedness Analysis Using Fourier Transforms	2026	VLDB	4.9793485e-05
11,536	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9793485e-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
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.0003475226
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022214789
745	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014288286
750	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00014265196
842	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013540697
1,066	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012192801
1,203	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00011548537
1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011152286
1,319	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011045888
1,465	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010576304
1,891	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.4184294e-05
1,970	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	9.2902522e-05
2,930	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	7.8415815e-05
3,927	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.9192361e-05
3,980	BurstSketch: Finding Bursts in Data Streams	2021	SIGMOD	6.8788724e-05
5,003	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.3188773e-05
6,816	Out of Many We are One: Measuring Item Batch with Clock-Sketch	2021	SIGMOD	5.6731874e-05
7,180	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	5.5928753e-05
7,637	Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation	2022	VLDB	5.477389e-05

Semantically Similar Papers

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