CIF: Small: Rate Distortion Paradigms for the Big Data Era

以数据为中心的技术是国家经济和基础设施的重要组成部分。 随着这些技术的发展，被收集、存储和处理的信息量正以指数级速度增长。 管理这种数据爆炸的可持续解决方案应部分基于对如何以满足实用性和访问要求的简洁方式存储信息的基本理解。 本研究旨在量化与信息存储，实用性和可访问性相关的基本权衡。信息理论提供了一个框架，量化什么是不可能的数据压缩和传输。 然而，传统的信息理论框架并不容易解决现代数据处理应用程序和大型数据集所固有的关键挑战。 特别是，信息理论分析通常忽略复杂性约束，并遇到重大困难时，分布式设置被认为是。 基于最近的主要研究者对对数损失下的压缩和相似性查询的压缩的工作，该项目将通过调查分布式处理和复杂性约束的附加维度的率失真权衡来解决这两个问题。 该项目的具体目标包括：（i）表征信息源的压缩性，该信息源受到压缩域中支持基本查询的约束，具有有限的复杂性;以及（ii）量化分布式处理（相对于集中式处理）的压缩和推理性能。 作为一个对应的拟议的理论分析，设计的实用算法，能够实现既定的信息理论的限制将被追求。

Data-centric technologies form an essential part of the nation's economy and infrastructure. Coincident with the evolution of these technologies, the amount of information that is being collected, stored and processed is growing at an exponential pace. A sustainable solution for managing this explosion of data should be guided in part by a fundamental understanding of how information can be stored in a succinct manner that meets utility and access requirements. This research seeks to quantify basic tradeoffs associated with information storage, utility and accessibility.Information theory provides a framework for quantifying what is and what is not possible in data compression and transmission. The traditional information-theoretic framework, however, does not readily address critical challenges inherent to modern data processing applications and large data sets. In particular, information-theoretic analyses generally ignore complexity constraints and encounter significant difficulties when distributed settings are considered. Building on recent work by the principal investigator on compression under logarithmic loss and compression for similarity queries, this project will address these two issues by investigating rate-distortion tradeoffs with the added dimensions of distributed processing and complexity constraints. Specific goals of the project include (i) characterizing the compressibility of an information source subject to the constraint that elementary queries are supported in the compressed domain with bounded complexity; and (ii) quantifying the performance of distributed processing (relative to centralized processing) for compression and inference. As a counterpart to the proposed theoretical analyses, the design of practical algorithms that are capable of achieving the established information-theoretic limits will be pursued.