Rate-Distortion Performance of Sequential Massive Random Access to Gaussian Sources with Memory

Elsa Dupraz, Thomas Maugey, Aline Roumy, Michel KiefferarXiv 2018 · arXiv

Introduction

In the era of immersive media, services like Free Viewpoint Television (FTV) allow thousands of users to navigate complex datasets—such as multi-angle video streams—simultaneously. This creates a significant challenge for servers: how to provide personalized data streams to millions of users when each request is slightly different but highly correlated with others.

Traditionally, a server might re-encode data for every unique request to minimize transmission bandwidth. However, in a Massive Random Access (MRA) scenario, the computational overhead of real-time re-encoding is prohibitive. The Sequential Massive Random Access (SMRA) framework addresses this by requiring the server to perform only simple bit extraction from a pre-encoded index. This paper extends the SMRA framework to Gaussian sources with memory, providing a theoretical foundation for more efficient data storage and transmission in realistic, correlated environments.

The Challenge of Memory in Random Access

Previous research into MRA primarily focused on "memoryless" sources, where each data point is independent. In reality, data like video or sensor feeds exhibit high internal correlation (intra-correlation) over time, in addition to the correlation between different viewpoints (inter-correlation).

To model this, the authors utilize Gaussian sources with memory, characterized by Toeplitz covariance matrices. This mathematical structure captures the stationary nature of the data's internal dependencies. The goal is to determine the "Rate-Distortion" performance: the minimum transmission rate ($R$) and storage rate ($S$) required to achieve a specific level of fidelity (Distortion, $D$) when the server is restricted to bit extraction.

Methodology: Two-Phase Coding

The authors propose a two-phase strategy to handle the complexities of sequential access:

  1. Offline Encoding: The server jointly encodes all correlated sources into a single, incremental index sequence. Because the encoder does not know which specific sequence a user will eventually request, it must structure the data so that any possible request path can be satisfied by a subset of the stored bits.
  2. Online Extraction: When a user requests a specific source, the server identifies the user's current state—specifically, what information they already possess from previous requests (side information). The server then extracts and transmits only the incremental bits necessary to reconstruct the new source at the desired distortion level.

This approach leverages Wyner-Ziv source coding theory, which deals with lossy compression when the decoder has access to side information unknown to the encoder.

Key Insights and Theoretical Results

Double Optimality

The paper’s most significant contribution is the proof of "double optimality." The authors demonstrate that even under the strict constraint of bit extraction (no re-encoding), the system can achieve:

  • Optimal Transmission: The bit rate is as low as if the server could perform full, customized re-encoding for every request.
  • Optimal Storage: The total data stored on the server is no greater than if the users did not have random access capabilities at all.

The Impact of Intra-correlation

By accounting for the "memory" of the source, the required transmission rate drops significantly compared to models that treat data points as independent. This is because the system exploits the predictable nature of the Gaussian process. The authors show that the optimal bit allocation across the source's components follows a waterfilling approach, a concept borrowed from information theory where more bits are allocated to components with higher variance (more information) to minimize overall distortion.

Numerical Validation

The theoretical findings were validated using two synthetic models: a Nearest Neighbor Correlation Model and a First-order Markov Source. Simulations using Toeplitz matrices of length $N=1000$ confirmed that memory-aware SMRA consistently outperforms memoryless approaches, providing a lower transmission rate for the same level of distortion.

Limitations and Future Directions

While the paper establishes a robust theoretical framework, several challenges remain:

  • Distortion Coupling: The incremental nature of the bitstream means that optimizing the distortion for one specific request path may inadvertently affect the distortion levels for other paths.
  • History Depth: The current model assumes the user only utilizes the immediately preceding request as side information. Future work will explore scenarios where users have a longer history of cached data.
  • Complex Request Sets: The authors aim to generalize the framework to accommodate more complex, non-linear request patterns beyond simple sequences.

Conclusion

This research provides a critical step toward making massive random access systems more efficient. By proving that double optimality is achievable for Gaussian sources with memory, the authors offer a path forward for high-demand services like FTV and large-scale sensor networks to deliver personalized content without overwhelming server resources or network bandwidth.

Summary updated

Abstract

In Sequential Massive Random Access (SMRA), a set of correlated sources is jointly encoded and stored on a server, and clients want to access to only a subset of the sources. Since the number of simultaneous clients can be huge, the server is only authorized to extract a bitstream from the stored data: no re-encoding can be performed before the transmission of a request. In this paper, we investigate the SMRA performance of lossy source coding of Gaussian sources with memory. In practical applications such as Free Viewpoint Television, this model permits to take into account not only inter but also intra correlation between sources. For this model, we provide the storage and transmission rates that are achievable for SMRA under some distortion constraint, and we consider two particular examples of Gaussian sources with memory.
BibTeX
@misc{dupraz2018rate,
  author = {Elsa Dupraz and Thomas Maugey and Aline Roumy and Michel Kieffer},
  title = {{Rate-Distortion Performance of Sequential Massive Random Access to Gaussian Sources with Memory}},
  year = {2018},
  eprint = {1801.05655},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1801.05655},
}
Figure