Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation

Summary: Stingy sketch: a sketch framework for accurate and fast frequency estimation on highly skewed streams, leveraging BCTree and PQueue. BCTree splits counters into a tree with carry-in encoding; PQueue enables pipelined L2-prefetch for memory-friendly precision, delivering up to 50% accuracy gains and 33% speedups over state-of-the-art rivals. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12650
Venue: VLDB
Year: 2022
Pagerank: 4.5506131e-05
Overall Rank: 8,250 | 42.61%
DOI: 10.14778/3523210.3523220

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,599	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	4.9973567e-05
9,082	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	4.3998984e-05
9,931	ChainedFilter: Combining Membership Filters by Chain Rule	2023	SIGMOD	4.250188e-05
10,315	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,584	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011255801
2,437	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.8231651e-05
2,471	Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity	2018	VLDB	8.7320072e-05
3,271	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	7.2968732e-05
3,614	Persistent Data Sketching	2015	SIGMOD	6.9147318e-05
3,824	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	6.7260705e-05
4,618	Approximate Frequency Counts over Data Streams	2012	VLDB	6.0446717e-05
5,163	Finding Persistent Items in Data Streams	2017	VLDB	5.6550193e-05
5,369	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	5.5434712e-05
5,880	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	5.2898074e-05
5,909	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	5.2769377e-05
6,085	Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix	2021	SIGMOD	5.2195267e-05
8,634	Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying	2021	SIGMOD	4.4801584e-05
8,635	Bidirectionally Densifying LSH Sketches with Empty Bins	2021	SIGMOD	4.4801584e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,388	Randomized Sketches for Quantile in LSM-tree based Store	2025	SIGMOD	4.1945683e-05
4,237	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.3333486e-05
2,437	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.8231651e-05
8,380	Single Update Sketch with Variable Counter Structure	2023	VLDB	4.5310997e-05
11,304	Bayesian Sketches for Volume Estimation in Data Streams	2023	VLDB	4.1945683e-05
6,790	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	4.9251439e-05
6,905	PR-Sketch: Monitoring Per-key Aggregation of Streaming Data with Nearly Full Accuracy	2021	VLDB	4.8925595e-05
1,584	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011255801
10,034	SieveSketch: A Fine-grained and Adaptive Sketch Framework for Accurate Frequency Estimation	2026	SIGMOD	4.1945683e-05
5,369	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	5.5434712e-05