Approximation-First Timeseries Query At Scale

Summary: PromSketch: an approximation-first intermediate cache that precomputes sketch-based window summaries to avoid repeated scans and costly overlapping-window recomputation in rule queries. Standalone module integrates into Prometheus/VictoriaMetrics, covers ~70% of aggregation-over-time queries, achieving up to 100x latency and ~1000x processing-cost reductions with ≤5% average error. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 14071
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,865 | 25.46%
DOI: 10.14778/3742728.3742732

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Zeying Zhu (University of Maryland)
2. Jonathan Chamberlain (Boston University)
3. Kenny Wu (University of Maryland)
4. David Starobinski (Boston University)
5. Zaoxing Liu (University of Maryland)

BibTeX Citation

@article{zhu_vldb25,
        title = {{Approximation-First Timeseries Query At Scale}},
        author = {Zhu, Zeying and Chamberlain, Jonathan and Wu, Kenny and Starobinski, David and Liu, Zaoxing},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {8},
        pages = {2348--2361},
        doi = {10.14778/3742728.3742732},
        url = {https://doi.org/10.14778/3742728.3742732},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 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
148	Gorilla: A Fast, Scalable, In-Memory Time Series Database	2015	VLDB	0.00029250767
230	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023891474
327	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00021091539
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014147905
828	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00013769869
1,100	Range Queries in OLAP Data Cubes	1997	SIGMOD	0.00012169143
1,352	Scuba: Diving into Data at Facebook	2013	VLDB	0.00011064595
1,472	M4: A Visualization-Oriented Time Series Data Aggregation	2014	VLDB	0.00010668946
2,455	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB	8.5552968e-05
3,366	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.4748604e-05
6,180	Visualization-aware Time Series Min-Max Caching with Error Bound Guarantees	2024	VLDB	5.949572e-05
6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.9443409e-05
6,336	Heracles: An Efficient Storage Model and Data Flushing for Performance Monitoring Timeseries	2021	VLDB	5.9088937e-05
7,551	Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams	2022	VLDB	5.6006414e-05
7,713	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB	5.5610113e-05
8,616	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	5.4004741e-05
9,817	Lindorm TSDB: A Cloud-native Time-series Database for Large-scale Monitoring Systems	2023	VLDB	5.214913e-05
9,821	Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors	2016	PODS	5.214913e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,054	Scalable Approximate Query Tracking over Highly Distributed Data Streams	2016	SIGMOD
2	4,863	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB
3	6,336	Heracles: An Efficient Storage Model and Data Flushing for Performance Monitoring Timeseries	2021	VLDB
4	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
5	9,188	OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates	2024	VLDB
6	7,752	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB
7	10,289	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
8	7,713	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
9	1,045	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB
10	7,110	PR-Sketch: Monitoring Per-key Aggregation of Streaming Data with Nearly Full Accuracy	2021	VLDB