Back to papers
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
- 13883
- Venue
- VLDB
- Year
- 2025
- Pagerank
- 4.1945683e-05
- Overall Rank
- 10,608 | 26.21%
- DOI
-
10.14778/3742728.3742732
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
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 |
| 126 |
Space-Efficient Online Computation of Quantile Summaries |
2001 |
SIGMOD |
0.00044744986 |
| 210 |
Gorilla: A Fast, Scalable, In-Memory Time Series Database |
2015 |
VLDB |
0.0003404384 |
| 323 |
Gigascope: A Stream Database for Network Applications |
2003 |
SIGMOD |
0.00027492196 |
| 429 |
The Aqua Approximate Query Answering System |
1999 |
SIGMOD |
0.00023476494 |
| 848 |
Approximate Counts and Quantiles over Sliding Windows |
2004 |
PODS |
0.0001597308 |
| 905 |
The Design of an Acquisitional Query Processor For Sensor Networks |
2003 |
SIGMOD |
0.0001546195 |
| 1,204 |
VerdictDB: Universalizing Approximate Query Processing |
2018 |
SIGMOD |
0.00013319541 |
| 1,359 |
Range Queries in OLAP Data Cubes |
1997 |
SIGMOD |
0.0001238588 |
| 1,487 |
Scuba: Diving into Data at Facebook |
2013 |
VLDB |
0.00011701099 |
| 1,805 |
M4: A Visualization-Oriented Time Series Data Aggregation |
2014 |
VLDB |
0.00010493299 |
| 2,914 |
DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees |
2019 |
VLDB |
7.9118579e-05 |
| 3,944 |
AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics |
2018 |
SIGMOD |
6.6078243e-05 |
| 6,296 |
Visualization-aware Time Series Min-Max Caching with Error Bound Guarantees |
2024 |
VLDB |
5.1249171e-05 |
| 6,596 |
Heracles: An Efficient Storage Model and Data Flushing for Performance Monitoring Timeseries |
2021 |
VLDB |
4.9988301e-05 |
| 6,740 |
Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing |
2021 |
SIGMOD |
4.944395e-05 |
| 7,534 |
Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams |
2022 |
VLDB |
4.7180004e-05 |
| 7,834 |
Sketch-based Querying of Distributed Sliding-Window Data Streams |
2012 |
VLDB |
4.6382551e-05 |
| 8,673 |
CoopStore: Optimizing Precomputed Summaries for Aggregation |
2020 |
VLDB |
4.4709116e-05 |
| 9,682 |
Lindorm TSDB: A Cloud-native Time-series Database for Large-scale Monitoring Systems |
2023 |
VLDB |
4.3047774e-05 |
| 9,685 |
Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors |
2016 |
PODS |
4.3047774e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 4,237 |
Statistical Analysis of Sketch Estimators |
2007 |
SIGMOD |
6.3333486e-05 |
| 11,853 |
Scalable Approximate Query Tracking over Highly Distributed Data Streams |
2016 |
SIGMOD |
4.1945683e-05 |
| 5,369 |
Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams |
2017 |
VLDB |
5.5434712e-05 |
| 6,596 |
Heracles: An Efficient Storage Model and Data Flushing for Performance Monitoring Timeseries |
2021 |
VLDB |
4.9988301e-05 |
| 1,064 |
Processing Complex Aggregate Queries over Data Streams |
2002 |
SIGMOD |
0.00014356481 |
| 9,038 |
OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates |
2024 |
VLDB |
4.4039656e-05 |
| 7,699 |
Sketch-based Geometric Monitoring of Distributed Stream Queries |
2013 |
VLDB |
4.6746076e-05 |
| 7,834 |
Sketch-based Querying of Distributed Sliding-Window Data Streams |
2012 |
VLDB |
4.6382551e-05 |
| 1,392 |
Sketching Streams Through the Net: Distributed Approximate Query Tracking |
2005 |
VLDB |
0.00012229045 |
| 6,905 |
PR-Sketch: Monitoring Per-key Aggregation of Streaming Data with Nearly Full Accuracy |
2021 |
VLDB |
4.8925595e-05 |