Compressing Unordered Data: Theory, Algorithms, and Applications

压缩无序数据：理论、算法和应用

• 批准号: 0729069
• 负责人: Vivek Goyal
• 金额: --
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-15 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0729069&HistoricalAwards=false
• 关键词: Compressing; Unordered; Data; Theory; Algorithms

Systems for information storage, gathering, or communication should be designed with careful attention to how the information will eventually be used. Often data are used without regard to their ordering; e.g., most databases are accessed by searching, and order is irrelevant to statistics like means, medians, etc. The observation that order can be irrelevant is powerful because sometimes ignoring order dramatically improves compression. Remarkably, in some situations the reduction in bits can approach 100%. This project seeks to develop theory, algorithms, and applications for communication when ordering is fully or partially irrelevant. The theoretical aspect includes establishing performance bounds when very little is known about the information source prior to encoding and when ordering is partially maintained. The algorithmic focus is on computationally-efficient algorithms with limited buffering requirements. Lowering the required communication rates in networked data gathering could enable cheaper, smaller andlower-power devices and thus hasten the deployment of large-scale and battery-operated sensing systems. The genesis of this project is the following order reduction: Communicating any nontrivial sequence of n (ordered) symbols requires a number of bits that is linear in n; however, disregarding orderlowers the rate to O(log n) when the source alphabet is finite. Results for universal coding over countable alphabets and rate-distortion problems also show large differences between theordered and unordered communication problems. The project aims to establish fundamental bounds on compressing unordered data (discrete-and continuous-valued sources, with or without full distributional knowledge); develop compression techniques (scalar and vector quantizers, indexing, refinement); and apply data set (as opposed to sequence) compression in practice. Extending the results to partial preservation of order could have important consequences for conventional compression.

在设计信息存储、收集或交流系统时，应仔细考虑信息最终将如何使用。 数据的使用通常不考虑其顺序;例如，大多数数据库是通过搜索来访问的，并且顺序与像均值、中值等统计量无关。顺序可以是无关的这一观察是有力的，因为有时忽略顺序会显著地改进压缩。 值得注意的是，在某些情况下，比特的减少可以接近100%。 该项目旨在开发理论，算法和应用程序的通信时，订购是完全或部分无关。 理论方面包括建立性能界限时，很少知道编码前的信息源和排序时，部分保持。算法的重点是有限的缓冲要求的计算效率的算法。 降低网络数据收集中所需的通信速率可以使设备更便宜，更小和更低功耗，从而加快大规模和电池供电传感系统的部署。这个项目的起源是以下的降阶：通信任何非平凡序列的n（有序）符号需要的位数是线性的n;然而，忽略order降低到O（log n）时，源字母表是有限的。可数字母上的通用编码和率失真问题的结果也显示了有序和无序通信问题之间的巨大差异。 该项目旨在确定压缩无序数据（离散和连续值源，有或没有完整的分布知识）的基本界限;开发压缩技术（标量和矢量量化器，索引，细化）;并在实践中应用数据集（相对于序列）压缩。 将结果扩展到部分保持顺序可能对传统压缩产生重要影响。