CIF: Small: Collaborative Research: Ordinal Data Compression

随着社会科学和生命科学领域大数据平台的出现，开发高效的无损和有损数据压缩方法以适应这些信息系统的需求变得至关重要。尽管对于经典文本、图像和视频数据存在许多近乎最优的压缩方法，但它们往往在以碎片或有序形式自然出现的数据上表现不佳。这对于所谓的有序数据来说尤其如此，它出现在大众投票、推荐系统和基因组重排研究中。在这里，信息是相对于一个？而不是？绝对的？尺度和排序的特定约束不能通过简单的字典结构来适当地捕获。该项目旨在通过开发有序数据压缩的理论、算法和软件解决方案，改善一些数据管理、云计算和通信系统的操作性能。该项目的主要目标是发展第一个一般和全面的有序压缩理论框架。特别是，研究人员提出了新的有序数据失真措施和有耗有序压缩的率失真函数；概率有序模型的秩聚集和学习方法，用于有序聚类和量化；以及有序域的平滑压缩和压缩计算。拟议的分析框架还将允许解决在压缩完整、部分和弱排名的背景下出现的算法挑战。配套的软件解决方案有望在理论计算机科学（排序、搜索和选择）、机器学习（聚类和学习排序）、基因优先排序和系统发育（分别重建有影响的基因和祖先基因组列表）等不同领域找到广泛的应用。

With the emergence of Big Data platforms in social and life sciences, it is becoming of paramount importance to develop efficient lossless and lossy data compression methods catering to the need of such information systems. Although many near-optimal compression methods exist for classical text, image and video data, they tend to perform poorly on data which naturally appears in fragmented or ordered form. This is especially the case for so called ordinal data, arising in crowd-voting, recommender systems, and genome rearrangement studies. There, information is represented with respect to a ?relative,? rather than ?absolute? scale, and the particular constraints of the ordering cannot be properly captured via simple dictionary constructions. This project seeks to improve the operational performance of a number of data management, cloud computing and communication systems by developing theoretical, algorithmic and software solutions for ordinal data compaction.The main goal of the project is to develop the first general and comprehensive theoretical framework for ordinal compression. In particular, the investigators propose to investigate new distortion measures for ordinal data and rate-distortion functions for lossy ordinal compression; rank aggregation and learning methods for probabilistic ordinal models, used for ordinal clustering and quantization; and smooth compression and compressive computing in the ordinal domain. The proposed analytical framework will also allow for addressing algorithmic challenges arising in the context of compressing complete, partial and weak rankings. The accompanying software solutions are expected to find broad applications in areas as diverse as theoretical computer science (sorting, searching and selection), machine learning (clustering and learning to rank), and gene prioritization and phylogeny (reconstruction of lists of influential genes and ancestral genomes, respectively).