On-Off Sketch: A Fast and Accurate Sketch on Persistence

Summary: On-Off sketch for persistence in streaming data, addressing persistence estimation and persistent-item discovery. It compresses periodic increments when multiple items map to the same counter, achieving smaller error than Count-Min; with PIE, it uses much less space and delivers up to 2.84x throughput and up to 4 orders of magnitude error reduction. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12506
Venue: VLDB
Year: 2021
Pagerank: 5.7212447e-05
Overall Rank: 7,036 | 51.73%
DOI: 10.14778/3425879.3425884

Incoming Non-self Citations Over Time

Authors

1. Yinda Zhang (Peking University)
2. Jinyang Li (Peking University)
3. Yutian Lei (Xiangtan University)
4. Tong Yang (Peking University; Peng Cheng Laboratory)
5. Zhetao Li (Xiangtan University)
6. Gong Zhang (Huawei)
7. Bin Cui (National Engineering Laboratory for Big Data Analysis Technology and Application; Peking University)

BibTeX Citation

@article{zhang_vldb21,
        title = {{On-Off Sketch: A Fast and Accurate Sketch on Persistence}},
        author = {Zhang, Yinda and Li, Jinyang and Lei, Yutian and Yang, Tong and Li, Zhetao and Zhang, Gong and Cui, Bin},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {2},
        pages = {128--140},
        doi = {10.14778/3425879.3425884},
        url = {https://doi.org/10.14778/3425879.3425884},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,918	Pontus: Finding Waves in Data Streams	2023	SIGMOD	5.3483178e-05
9,027	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	5.3293224e-05
10,673	Pandora: An Efficient and Rapid Solution for Persistence-Based Tasks in High-Speed Data Streams	2025	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
216	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024498128
1,294	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011291308
1,905	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	9.5034849e-05
2,148	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	9.0825156e-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,765	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.1442477e-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,971	Persistent Bloom Filter: Membership Testing for the Entire History	2018	SIGMOD	6.4195676e-05
8,653	Bias-Aware Sketches	2017	VLDB	5.3914428e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,385	Randomized Error Removal for Online Spread Estimation in Data Streaming	2021	VLDB
2	9,188	OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates	2024	VLDB
3	4,863	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB
4	8,666	Efficient framework for operating on data sketches	2023	VLDB
5	10,289	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
6	7,498	Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation	2022	VLDB
7	10,329	SieveSketch: A Fine-grained and Adaptive Sketch Framework for Accurate Frequency Estimation	2026	SIGMOD
8	1,294	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD
9	7,110	PR-Sketch: Monitoring Per-key Aggregation of Streaming Data with Nearly Full Accuracy	2021	VLDB
10	3,023	Persistent Data Sketching	2015	SIGMOD