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

Summary: Stingy Sketch jointly optimizes frequency-estimation accuracy and throughput via Bit-pinching Counter Trees, which encode carry operations compactly, and a prefetching Prophet Queue that keeps accesses in L2 cache. It improves accuracy up to 50% and speed up to 33% over state-of-the-art sketches. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12838
Venue: VLDB
Year: 2022
Pagerank: 5.6031077e-05
Overall Rank: 7,498 | 48.56%
DOI: 10.14778/3523210.3523220

Incoming Non-self Citations Over Time

Authors

1. Haoyu Li (Peking University)
2. Qizhi Chen (Peking University)
3. Yixin Zhang (Peking University)
4. Tong Yang (Peking University; Peng Cheng Laboratory)
5. Bin Cui (Peking University)

BibTeX Citation

@article{li_vldb22,
        title = {{Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation}},
        author = {Li, Haoyu and Chen, Qizhi and Zhang, Yixin and Yang, Tong and Cui, Bin},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {7},
        pages = {1426--1438},
        doi = {10.14778/3523210.3523220},
        url = {https://doi.org/10.14778/3523210.3523220},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,548	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	5.6021153e-05
9,027	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	5.3293224e-05
10,083	ChainedFilter: Combining Membership Filters by Chain Rule	2023	SIGMOD	5.1578347e-05
10,295	Sublime: Sublinear Error & Space for Unbounded Skewed Streams	2026	SIGMOD	5.093636e-05
10,613	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	5.093636e-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,294	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011291308
1,975	Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity	2018	VLDB	9.3645236e-05
2,377	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.6710302e-05
2,878	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	8.0058242e-05
3,023	Persistent Data Sketching	2015	SIGMOD	7.8398269e-05
3,228	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	7.6215176e-05
4,460	Approximate Frequency Counts over Data Streams	2012	VLDB	6.689845e-05
4,863	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	6.4740702e-05
4,898	Finding Persistent Items in Data Streams	2017	VLDB	6.454197e-05
4,900	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.4534715e-05
5,255	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.2982495e-05
5,793	Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix	2021	SIGMOD	6.0868713e-05
8,612	Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying	2021	SIGMOD	5.4012878e-05
8,613	Bidirectionally Densifying LSH Sketches with Empty Bins	2021	SIGMOD	5.4012878e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,377	gSketch: On Query Estimation in Graph Streams	2012	VLDB
2	8,414	Single Update Sketch with Variable Counter Structure	2023	VLDB
3	10,295	Sublime: Sublinear Error & Space for Unbounded Skewed Streams	2026	SIGMOD
4	10,289	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
5	11,503	Bayesian Sketches for Volume Estimation in Data Streams	2023	VLDB
6	7,036	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB
7	7,110	PR-Sketch: Monitoring Per-key Aggregation of Streaming Data with Nearly Full Accuracy	2021	VLDB
8	1,294	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD
9	10,329	SieveSketch: A Fine-grained and Adaptive Sketch Framework for Accurate Frequency Estimation	2026	SIGMOD
10	4,863	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB