AHA: Scalable Alternative History Analysis for Operational Timeseries Applications

Harshavardhan Kamarthi, Harshil Shah, Henry Milner, Sayan Sinha, Yan Li, B. Aditya Prakash, Vyas Sekar

Here is a summary of the paper tailored for a technical audience:

TL;DR

Operational systems generate massive amounts of timeseries data, making retrospective "what-if" analysis prohibitively expensive or highly inaccurate. This paper introduces AHA (Alternative History Analytics), a system that leverages data sparsity and decomposable statistics to enable scalable, retrospective queries. By storing only granular "leaf" subgroup metrics and rolling them up on demand, AHA achieves 100% accuracy for downstream tasks while reducing total cost of ownership by up to 85x.

What Problem Does This Paper Address?

Modern operational systems—like video streaming platforms, ISPs, and IoT networks—collect high-dimensional timeseries data. Every user session is tagged with multiple attributes (e.g., location, device type, ISP) and performance metrics (e.g., buffering time, bitrate).

Data analysts and ML engineers constantly need to run alternative history analysis on this data. If they design a new anomaly detection algorithm, tweak an alert threshold, or run CI/CD regression tests, they need to see how these changes would have performed on historical data.

Existing solutions force a harsh tradeoff:

  1. Store all raw data: Guarantees perfect accuracy but incurs massive storage and compute costs (high Total Cost of Ownership, or TCO).
  2. Pre-compute everything: Impossible, as the number of possible attribute combinations grows exponentially.
  3. Approximate methods (Sampling/Sketching): Saves money but destroys fidelity, especially for smaller, niche user subgroups, leading to inaccurate ML predictions and false alerts.

Methods

AHA solves this by decoupling data ingestion from query execution using a "late binding" architecture. It relies on a two-step process:

  1. Ingest (Compute LEAF Statistics): Instead of storing raw data, AHA identifies the most granular combinations of attributes actually observed in the data (called "LEAF" subgroups). It computes and stores only the necessary base statistics (like count, sum, and sum of squares) for these specific leaves.
  2. Query (Reconstruct via CUBE): When an analyst queries a broader parent group (e.g., "All users in New York," which encompasses many ISPs and device types), AHA uses the CUBE operator found in modern OLAP databases (like ClickHouse). It dynamically and efficiently rolls up the stored leaf statistics to reconstruct the exact metrics for the requested parent group.

Datasets

The authors evaluated AHA across a mix of real-world and synthetic datasets:

  • VideoAnalytics: A massive, real-world deployment dataset from a major video-streaming provider (used to validate production readiness).
  • UmassTrace: Network trace data.
  • NYTaxi: Standard NYC taxi pickup/dropoff statistics.
  • CH-Bench: Anonymized database log traces from ClickHouse.
  • MGBench & BigData: Synthetic benchmarks for testing scale.
  • IMDB: Movie dataset featuring release years, actors, etc.

Key Insights and Ideas

  • Task Decomposability is a Superpower: Most anomaly detection algorithms (like K-Nearest Neighbors or Isolation Forests) rely on simple statistical features like mean and variance. These are decomposable—meaning the mean of a parent group can be perfectly calculated if you know the sums and counts of its child groups. You don't need raw data to get perfect accuracy.
  • The "Sparsity" Loophole: Theoretically, the number of possible user subgroups is exponential ($O(2^M)$ based on $M$ attributes). However, AHA capitalizes on active subgroup sparsity: in any given time-step, users only occupy a tiny fraction of these possible combinations. This means the active LEAF groups are small enough to easily fit into the RAM of a single machine.
  • In-Memory CUBE is King: Because the LEAF data fits in memory, standard CUBE operations—which are notoriously expensive and slow in distributed, multi-node setups—become incredibly fast. This allows AHA to outperform general-purpose compute engines like Spark.

Key Results

  • Perfect Fidelity: AHA maintained 100% accuracy (strong equivalence) for supported tasks. In contrast, sampling and sketching methods averaged only 71% and 88% accuracy, respectively, with massive variance for smaller subgroups.
  • Massive Cost Reduction: AHA achieved 34x to 85x lower TCO (compute + storage) compared to standard baselines that store raw data or pre-compute output features. It was also 6-10x cheaper than state-of-the-art sketching methods.
  • Production Impact: AHA was deployed in the core data pipeline of a large video analytics company. It reduced the total cost by 6.2x, translating to an estimated cost savings of over $0.7M per month.
  • Speed: In a production case study tracking user navigation patterns, AHA achieved a 1.25x speedup in data aggregation and 6.2x faster query execution compared to baseline raw data scans.

Limitations and Future Work

  • Reliance on Decomposability: AHA's perfect accuracy guarantee only holds for decomposable statistics. It cannot accurately compute exact non-decomposable metrics, such as exact medians or interquartile ranges, directly from the rolled-up data.
  • Approximations for Percentiles: To handle non-decomposable metrics, the system must fall back on storing histogram sketches for the leaf groups, which reintroduces slight approximations.
  • Future Work: While not explicitly detailed as a roadmap, the natural next steps involve extending this framework to support more complex, non-linear feature extractions used in deep learning, and optimizing the storage of advanced sketches for exact percentile calculations.

Summary updated

Abstract

Many operational systems collect high-dimensional timeseries data about users/systems on key performance metrics. For instance, ISPs, content distribution networks, and video delivery services collect quality of experience metrics for user sessions associated with metadata (e.g., location, device, ISP). Over such historical data, operators and data analysts often need to run retrospective analysis; e.g., analyze anomaly detection algorithms, experiment with different configurations for alerts, evaluate new algorithms, and so on. We refer to this class of workloads as alternative history analysis for operational datasets. We show that in such settings, traditional data processing solutions (e.g., data warehouses, sampling, sketching, big-data systems) either pose high operational costs or do not guarantee accurate replay. We design and implement a system, called AHA (Alternative History Analytics), that overcomes both challenges to provide cost efficiency and fidelity for high-dimensional data. The design of AHA is based on analytical and empirical insights about such workloads: 1) the decomposability of underlying statistics; 2) sparsity in terms of active number of subpopulations over attribute-value combinations; and 3) efficiency structure of aggregation operations in modern analytics databases. Using multiple real-world datasets and as well as case-studies on production pipelines at a large video analytics company, we show that AHA provides 100% accuracy for a broad range of downstream tasks and up to 85x lower total cost of ownership (i.e., compute + storage) compared to conventional methods.
BibTeX
@inproceedings{kamarthi2026aha,
  author = {Harshavardhan Kamarthi and Harshil Shah and Henry Milner and Sayan Sinha and Yan Li and B. Aditya Prakash and Vyas Sekar},
  title = {{AHA: Scalable Alternative History Analysis for Operational Timeseries Applications}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2026},
  doi = {10.1145/3770854.3783945},
}
Figure