Wavelet Models for Video Time-Series

Sheng Ma, Chuanyi JiNeurIPS 1997

As we move toward a world dominated by streaming and video-on-demand, network engineers face a critical challenge: predicting how video traffic will behave to prevent buffer overflows and lag. Researchers have developed a novel wavelet-based approach to model video traffic that captures both long-range and short-range dependencies simultaneously. By shifting from the time domain to the wavelet domain, they achieved a massive computational speedup—reducing processing time from five hours to just three minutes—while outperforming traditional models in accuracy.

The Challenge of Video Traffic

Video traffic is notoriously difficult to model because it exhibits two conflicting behaviors:

  1. Short-Range Dependence (SRD): Rapid, unpredictable fluctuations that occur within a single scene.
  2. Long-Range Dependence (LRD): "Self-similarity" or memory that persists over long periods, often caused by macro-level scene changes.

Existing models like FARIMA (Fractional Auto-regressive Integrated Moving Average) can capture these dual behaviors, but they are computationally "heavy." With an $O(N^2)$ complexity, they are far too slow for generating the large volumes of synthetic traffic needed for modern network simulations. Other models are either too mathematically complex for theoretical analysis or fail to capture the physical reality of scene changes.

The Wavelet Solution

The authors propose moving the entire modeling process into the wavelet domain. The core idea is that wavelets—mathematical functions that scale and shift—possess a "deterministic similar structure" that naturally matches the statistical self-similarity of video traffic. Instead of trying to model the complex time-series directly, the authors model the wavelet coefficients.

The algorithm follows a streamlined, five-step process:

  1. Decomposition: Perform a wavelet transform (using the simple Haar wavelet) on a real video trace to extract coefficients.
  2. Statistics: Calculate the variance of these coefficients at different time scales.
  3. Generation: Generate new coefficients independently using Gaussian distributions based on those variances.
  4. Refinement: Apply a transformation to these coefficients so their marginal density function matches the heavy-tailed nature of real video traffic.
  5. Reconstruction: Perform an inverse wavelet transform to create a synthetic video traffic trace.

Because wavelet transforms are highly efficient, the entire process runs in $O(N)$ time, representing the lowest possible computational cost for traffic modeling.

Key Insights from the Data

The study evaluated the model using two classic benchmarks in video traffic research: a long trace of "Star Wars" frames encoded using a JPEG-like encoder, and "MPEG GOP" (video coded at the Group of Pictures level). These datasets are standard for testing how well a model handles the bursty, unpredictable nature of real-world video.

The "Aha" Moment: Rapid Autocorrelation Decay

The researchers realized that while video traffic looks like a chaotic mess in the time domain, its wavelet coefficients are much better behaved.

Autocorrelation of wavelet coefficients for Star Wars and GOP datasets.

Specifically, the autocorrelation of wavelet coefficients drops to zero very quickly. This means you can model the coefficients as being independent within each scale without losing the "big picture" of the traffic's long-range memory. Since LRD is essentially a multi-scale phenomenon, the wavelet domain provides a unified language to describe both the micro-jitters (SRD) and the macro-trends (LRD) of a video stream.

The Importance of Heavy Tails

The paper highlights that simply matching the variance isn't enough. Real video traffic has "heavy tails," meaning extreme values (like sudden, massive bursts of data) are far more common than they would be in a standard normal distribution.

Q-Q plots showing heavy-tailed distributions in the video datasets.

Their algorithm explicitly corrects for this heavy-tailed behavior during the refinement step, which is vital for accurately predicting network buffer losses.

Performance and Results

The results of the wavelet approach are striking, both in terms of accuracy and computational efficiency:

  • Superior Accuracy: The wavelet model outperformed a complex, 45-parameter FARIMA model in matching the autocorrelation and buffer loss rates of the original video sources.
  • Massive Speedup: For a trace of 171,000 frames, the FARIMA model took over 5 hours of CPU time to develop and generate. The wavelet algorithm completed the exact same task in just 3 minutes on the same hardware.
  • Theoretical Validation: The authors provided a mathematical theorem proving that their simplified model (which ignores correlations between wavelet coefficients) still yields buffer overflow probabilities similar to the more complex Fractional Gaussian Noise (FGN) process.

Limitations and Future Directions

While highly effective, the model does make some simplifying assumptions. For the sake of speed, it neglects the correlation between wavelet coefficients at different time scales. While the results remain excellent, the authors note that a more careful treatment of inter-scale correlation might be needed for even higher precision.

Additionally, the theoretical proof provided in the paper currently holds for FGN processes, requiring further work to extend this framework to more general, non-Gaussian processes. Finally, while the model is incredibly fast at generating synthetic traces based on existing data, future research could explore how this $O(N)$ efficiency might be adapted for real-time, on-the-fly network management.

Summary updated

BibTeX
@inproceedings{ma1997wavelet,
  author = {Sheng Ma and Chuanyi Ji},
  title = {{Wavelet Models for Video Time-Series}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1997},
}
Figure