Persistent Data Sketching

Summary: Persistent sketches extend multiversion data structures to keep all versions as updates arrive. They enable time-travel queries on streams by maintaining sublinear-space summaries that answer past-state queries with controlled accuracy. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5122
Venue: SIGMOD
Year: 2015
Pagerank: 7.8398269e-05
Overall Rank: 3,023 | 79.27%
DOI: 10.1145/2723372.2749443

Incoming Non-self Citations Over Time

Authors

1. Zhewei Wei (Renmin University of China)
2. Ge Luo (Hong Kong University of Science and Technology)
3. Ke Yi (Hong Kong University of Science and Technology)
4. Xiaoyong Du (Renmin University of China)
5. Ji-Rong Wen (Renmin University of China)

BibTeX Citation

@inproceedings{wei_sigmod15,
        title = {{Persistent Data Sketching}},
        author = {Wei, Zhewei and Luo, Ge and Yi, Ke and Du, Xiaoyong and Wen, Ji-Rong},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2749443},
        url = {https://dl.acm.org/doi/10.1145/2723372.2749443},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,905	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	9.5034849e-05
2,698	Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores	2020	SIGMOD	8.2450522e-05
3,898	BurstSketch: Finding Bursts in Data Streams	2021	SIGMOD	7.0367583e-05
4,971	Persistent Bloom Filter: Membership Testing for the Entire History	2018	SIGMOD	6.4195676e-05
5,255	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.2982495e-05
6,685	Out of Many We are One: Measuring Item Batch with Clock-Sketch	2021	SIGMOD	5.8034001e-05
7,036	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	5.7212447e-05
7,498	Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation	2022	VLDB	5.6031077e-05
7,551	Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams	2022	VLDB	5.6006414e-05
7,716	Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items	2023	SIGMOD	5.5605526e-05
8,310	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	5.4556836e-05
10,212	Concurrent Path-Copying Update to Tree Structures	2026	SIGMOD	5.093636e-05
10,824	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB	5.093636e-05
11,562	MinMax Sampling: A Near-optimal Global Summary for Aggregation in the Wide Area	2022	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
681	Access Methods For Multiversion Data	1989	SIGMOD	0.0001502579
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702
838	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001370404
1,210	Immortal DB: Transaction Time Support for SQL Server	2005	SIGMOD	0.00011656235
2,576	Optimal Sampling from Sliding Windows	2009	PODS	8.3964437e-05
3,038	Skippy: a New Snapshot Indexing Method for Time Travel in the Storage Manager	2008	SIGMOD	7.8272965e-05
3,691	Searching in Time	2006	SIGMOD	7.1998478e-05
4,142	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.8764637e-05
7,936	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	5.5181056e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,697	Sketching Probabilistic Data Streams	2007	SIGMOD
2	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
3	9,188	OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates	2024	VLDB
4	8,414	Single Update Sketch with Variable Counter Structure	2023	VLDB
5	7,110	PR-Sketch: Monitoring Per-key Aggregation of Streaming Data with Nearly Full Accuracy	2021	VLDB
6	7,713	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
7	10,289	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
8	10,673	Pandora: An Efficient and Rapid Solution for Persistence-Based Tasks in High-Speed Data Streams	2025	SIGMOD
9	7,036	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB
10	5,255	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD