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: 4.5462498e-05
Overall Rank: 8,246 | 42.70%
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,600	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	4.9925547e-05
9,079	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	4.3956812e-05
9,932	ChainedFilter: Combining Membership Filters by Chain Rule	2023	SIGMOD	4.2461158e-05
10,327	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	4.1905499e-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,586	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011245213
2,439	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.8181328e-05
2,469	Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity	2018	VLDB	8.7255912e-05
3,273	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	7.2899198e-05
3,618	Persistent Data Sketching	2015	SIGMOD	6.9080647e-05
3,827	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	6.7195959e-05
5,082	Approximate Frequency Counts over Data Streams	2012	VLDB	5.7066369e-05
5,163	Finding Persistent Items in Data Streams	2017	VLDB	5.6495769e-05
5,377	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	5.5381456e-05
5,886	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	5.2847297e-05
5,910	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	5.2718714e-05
6,089	Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix	2021	SIGMOD	5.2145151e-05
8,634	Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying	2021	SIGMOD	4.4758632e-05
8,635	Bidirectionally Densifying LSH Sketches with Empty Bins	2021	SIGMOD	4.4758632e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,399	Randomized Sketches for Quantile in LSM-tree based Store	2025	SIGMOD	4.1905499e-05
4,239	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.3273184e-05
2,439	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.8181328e-05
8,380	Single Update Sketch with Variable Counter Structure	2023	VLDB	4.5267558e-05
11,306	Bayesian Sketches for Volume Estimation in Data Streams	2023	VLDB	4.1905499e-05
6,791	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	4.9204179e-05
6,909	PR-Sketch: Monitoring Per-key Aggregation of Streaming Data with Nearly Full Accuracy	2021	VLDB	4.8878659e-05
1,586	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011245213
10,034	SieveSketch: A Fine-grained and Adaptive Sketch Framework for Accurate Frequency Estimation	2026	SIGMOD	4.1905499e-05
5,377	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	5.5381456e-05