At-the-time and Back-in-time Persistent Sketches

Summary: Proposes ATTP and BITP sketches to answer historical queries with far smaller space. Presents multiple implementations and shows superior empirical efficiency over state-of-the-art historical-query methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h48e1c3d4e00f7e91
Venue: SIGMOD
Year: 2021
Pagerank: 6.1336701e-05
Overall Rank: 5,399 | 63.82%
DOI: 10.1145/3448016.3452802

Incoming Non-self Citations Over Time

Authors

1. Benwei Shi (University of Utah)
2. Zhuoyue Zhao (University of Utah)
3. Yanqing Peng (University of Utah)
4. Feifei Li (University of Utah)
5. Jeff M. Phillips (University of Utah)

BibTeX Citation

@inproceedings{shi_sigmod21,
        title = {{At-the-time and Back-in-time Persistent Sketches}},
        author = {Shi, Benwei and Zhao, Zhuoyue and Peng, Yanqing and Li, Feifei and Phillips, Jeff M.},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3452802},
        url = {https://dl.acm.org/doi/10.1145/3448016.3452802},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,657	Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation	2022	VLDB	5.456693e-05
7,895	Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items	2023	SIGMOD	5.4152499e-05
8,499	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	5.3131213e-05
9,592	Optimal Matrix Sketching over Sliding Windows	2024	VLDB	5.1376962e-05
9,771	CAFE: Towards Compact, Adaptive, and Fast Embedding for Large-scale Recommendation Models	2024	SIGMOD	5.115551e-05
10,506	Concurrent Path-Copying Update to Tree Structures	2026	SIGMOD	4.9605343e-05
10,688	AeroSketch: Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams	2026	SIGMOD	4.9605343e-05
11,296	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 29 of 29 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
21	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.00056737487
177	The Vertica Analytic Database: C-Store 7 Years Later	2012	VLDB	0.00026571747
343	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020486383
452	Mergeable Summaries	2012	PODS	0.00018032092
495	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017347522
565	Distributed Top-K Monitoring	2003	SIGMOD	0.00016238411
594	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015814493
686	Access Methods For Multiversion Data	1989	SIGMOD	0.00014736882
738	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD	0.0001432185
841	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00013503124
1,065	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012181098
1,070	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.0001215545
1,095	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012036913
1,210	Immortal DB: Transaction Time Support for SQL Server	2005	SIGMOD	0.00011495323
1,435	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010659454
1,874	G-OLA: Generalized On-Line Aggregation for Interactive Analysis on Big Data	2015	SIGMOD	9.4470874e-05
1,924	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	9.3535088e-05
2,014	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.1775869e-05
2,472	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.3988741e-05
2,658	A Geometric Approach to Monitoring Threshold Functions Over Distributed Data Streams	2006	SIGMOD	8.1455298e-05
2,702	Quality and Efficiency in Kernel Density Estimates for Large Data	2013	SIGMOD	8.0958339e-05
3,090	Persistent Data Sketching	2015	SIGMOD	7.6420011e-05
3,108	Skippy: a New Snapshot Indexing Method for Time Travel in the Storage Manager	2008	SIGMOD	7.6237576e-05
3,763	Searching in Time	2006	SIGMOD	7.0180801e-05
3,932	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.900511e-05
5,119	Persistent Bloom Filter: Membership Testing for the Entire History	2018	SIGMOD	6.2541554e-05
5,140	Shape Sensitive Geometric Monitoring	2008	PODS	6.2436669e-05
6,310	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.7992155e-05
8,129	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	5.3739121e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,643	Focus! Fast On-disk Concurrency-control Using Sketches	2026	SIGMOD
2	3,216	Fully Persistent B+-trees	1991	SIGMOD
3	10,378	AITTI: Augmented Interval Tree for Temporal Indexing	2027	SIGMOD
4	12,301	Durable Top-k Queries on Temporal Data	2018	VLDB
5	6,569	Optimal Splitters for Temporal and Multi-version Databases	2013	SIGMOD
6	11,296	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB
7	10,578	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
8	12,369	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS
9	7,204	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB
10	3,090	Persistent Data Sketching	2015	SIGMOD