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).