Transmission and Storage Rates for Sequential Massive Random Access

Elsa Dupraz, Thomas Maugey, Aline Roumy, Michel KiefferHAL 2018

TL;DR

This paper introduces Sequential Massive Random Access (SMRA), a new framework for efficiently storing and transmitting data when clients sequentially request subsets of correlated sources. They establish theoretical bounds and demonstrate practical implementations showing that SMRA can achieve transmission rates comparable to traditional methods while offering significant storage savings.

What Problem Does This Paper Address?

The explosion of data, particularly in applications like free-viewpoint television (FTV) or sensor networks, presents a challenge for traditional data delivery systems. In these scenarios, a large database of correlated data is stored, and clients only need to access specific parts of it. The sheer number of simultaneous clients makes re-encoding data on demand computationally infeasible. Existing methods struggle to balance storage efficiency with the need for rapid, on-demand transmission of requested data subsets without re-encoding. This paper addresses this gap by proposing and analyzing SMRA, a paradigm that jointly optimizes storage and transmission rates for such scenarios.

Methods

The authors introduce a formal definition of SMRA, which involves an "offline encoder" that compresses the entire dataset once and a "online extractor" that retrieves only the requested data without re-encoding. They derive theoretical bounds for achievable storage and transmission rates for various source models, including i.i.d. and non i.i.d. sources, both with and without known statistics, and for lossy compression scenarios with Gaussian sources. A key aspect of their approach is the information-theoretic analysis, which establishes fundamental limits on performance. For practical implementation, they propose using rate-compatible LDPC codes, demonstrating how these can be adapted to the SMRA framework.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulation with synthetic data models (i.i.d. sources, Gaussian sources, WP-sources) rather than real-world datasets.

Key Insights and Ideas

  • Joint Optimization is Crucial: Unlike traditional approaches that treat storage and transmission separately, SMRA highlights the necessity of jointly optimizing both for efficiency in massive, sequential access scenarios.
  • No Re-encoding is Key: The constraint of no re-encoding at the server is central to the problem, driving the need for novel coding strategies.
  • Transmission Rate Can Match Traditional Methods: Despite the complexity of sequential access and unknown requests, SMRA can achieve transmission rates comparable to point-to-point source coding schemes.
  • Storage Savings are Significant: The proposed SMRA framework offers substantial storage rate advantages compared to naive approaches that might store all possible data combinations.
  • LDPC Codes are Practical: Rate-compatible LDPC codes are shown to be effective in building practical SMRA systems that approach theoretical performance limits.
  • Unknown Statistics Don't Necessarily Increase Rates: The paper demonstrates that for i.i.d. sources, unknown statistics do not increase the achievable storage or transmission rates when using universal coding schemes.

Key Results

  • Theoretical Bounds: Achievable storage and transmission rates are derived for i.i.d. and non i.i.d. sources, establishing lower bounds for SMRA performance.
  • Rate-Distortion Regions: For Gaussian sources, the paper characterizes the trade-off between storage, transmission rates, and distortion.
  • Practical Performance: Experimental results using LDPC staircase and LDPCA codes show that practical SMRA systems can achieve rates close to the theoretical bounds, even with erasures or binary errors in side information. For instance, Table II shows that for a theoretical storage of 40,000 symbols, LDPC staircase codes require only slightly more (40,023) for a specific erasure probability.

Limitations and Future Work

  • General Sources Complexity: While the paper provides theoretical results for general (non i.i.d.) sources, practical implementations are primarily demonstrated for i.i.d. sources. Extending practical implementations to more general source models remains a challenge.
  • Navigation Graph Influence: The paper acknowledges that the influence of the navigation graph structure on storage and transmission rates could be further explored.
  • Unknown Statistics for General Sources: The analysis of unknown statistics is primarily focused on i.i.d. sources. Extending this to general non i.i.d. sources with unknown statistics is a potential area for future research.
  • Real-World Data: The experimental validation uses synthetic data models. Applying and validating SMRA on real-world datasets like FTV would be a valuable next step.

Summary updated

Abstract

This paper introduces a new source coding paradigm called Sequential Massive Random Access (SMRA). In SMRA, a set of correlated sources is encoded once for all and stored on a server, and clients want to successively access to only a subset of the sources. Since the number of simultaneous clients can be huge, the server is only allowed to extract a bitstream from the stored data: no re-encoding can be performed before the transmission of the specific client's request. In this paper, we formally define the SMRA framework and introduce both storage and transmission rates to characterize the performance of SMRA. We derive achievable transmission and storage rates for lossless source coding of i.i.d. and non i.i.d. sources, and transmission and storage rates-distortion regions for Gaussian sources. We also show two practical implementations of SMRA systems based on rate-compatible LDPC codes. Both theoretical and experimental results demonstrate that SMRA systems can reach the same transmission rates as in traditional point to point source coding schemes, while having a reasonable overhead in terms of storage rate. These results constitute a breakthrough for many recent data transmission applications in which different parts of the data are requested by the clients.
BibTeX
@inproceedings{dupraz2018transmission,
  author = {Elsa Dupraz and Thomas Maugey and Aline Roumy and Michel Kieffer},
  title = {{Transmission and Storage Rates for Sequential Massive Random Access}},
  booktitle = {HAL},
  year = {2018},
}

Loading related content...

Figure