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: h0432f7fe704d67e7
Venue: VLDB
Year: 2022
Pagerank: 5.456693e-05
Overall Rank: 7,657 | 48.68%
DOI: 10.14778/3523210.3523220
PDF: Download (CC BY-NC-ND 4.0)

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 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,714	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	5.4557265e-05
8,060	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	5.382134e-05
10,330	ChainedFilter: Combining Membership Filters by Chain Rule	2023	SIGMOD	5.0239924e-05
10,403	Near-Optimal Per-Key Streaming Quantile Estimation	2027	SIGMOD	4.9605343e-05
10,584	Sublime: Sublinear Error & Space for Unbounded Skewed Streams	2026	SIGMOD	4.9605343e-05
11,130	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	4.9605343e-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,329	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011013041
1,856	Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity	2018	VLDB	9.4802321e-05
2,430	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.4651179e-05
2,938	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	7.8224388e-05
3,090	Persistent Data Sketching	2015	SIGMOD	7.6420011e-05
3,093	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	7.6378811e-05
4,570	Approximate Frequency Counts over Data Streams	2012	VLDB	6.5162084e-05
5,005	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	6.3061786e-05
5,029	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.2952031e-05
5,040	Finding Persistent Items in Data Streams	2017	VLDB	6.2901248e-05
5,399	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.1336701e-05
5,929	Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix	2021	SIGMOD	5.9278154e-05
7,208	Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying	2021	SIGMOD	5.5701802e-05
8,802	Bidirectionally Densifying LSH Sketches with Empty Bins	2021	SIGMOD	5.2601468e-05

Semantically Similar Papers

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