Compressing Unordered Data: Theory, Algorithms, and Applications

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

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.