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: 12651
Venue: VLDB
Year: 2022
Pagerank: 5.5377539e-05
Overall Rank: 8,189 | 43.09%
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
7,415	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	5.6888792e-05
8,914	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	5.4089358e-05
9,932	ChainedFilter: Combining Membership Filters by Chain Rule	2023	SIGMOD	5.2377177e-05
10,327	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	5.1725247e-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,320	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011277617
2,001	Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity	2018	VLDB	9.4135494e-05
2,358	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.7690225e-05
2,829	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	8.1284257e-05
3,101	Persistent Data Sketching	2015	SIGMOD	7.8222282e-05
3,175	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	7.7393361e-05
4,804	Approximate Frequency Counts over Data Streams	2012	VLDB	6.5670506e-05
4,841	Finding Persistent Items in Data Streams	2017	VLDB	6.5485268e-05
5,122	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	6.41928e-05
5,194	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.3919263e-05
5,498	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.264399e-05
6,178	Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix	2021	SIGMOD	6.0242169e-05
8,522	Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying	2021	SIGMOD	5.4798703e-05
8,523	Bidirectionally Densifying LSH Sketches with Empty Bins	2021	SIGMOD	5.4798703e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,399	Randomized Sketches for Quantile in LSM-tree based Store	2025	SIGMOD	5.1725247e-05
4,088	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.9732881e-05
2,358	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.7690225e-05
8,276	Single Update Sketch with Variable Counter Structure	2023	VLDB	5.5173597e-05
11,306	Bayesian Sketches for Volume Estimation in Data Streams	2023	VLDB	5.1725247e-05
6,919	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	5.8098536e-05
6,992	PR-Sketch: Monitoring Per-key Aggregation of Streaming Data with Nearly Full Accuracy	2021	VLDB	5.7883015e-05
1,320	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011277617
10,034	SieveSketch: A Fine-grained and Adaptive Sketch Framework for Accurate Frequency Estimation	2026	SIGMOD	5.1725247e-05
5,122	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	6.41928e-05