Compressing Unordered Data: Theory, Algorithms, and Applications

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

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.