CIF: Small: Collaborative Research: Ordinal Data Compression

CIF：小型：协作研究：有序数据压缩

• 批准号: 1526763
• 负责人: Arya Mazumdar
• 金额: $ 25万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2016-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1526763&HistoricalAwards=false
• 关键词: CIF; Small; Collaborative; Research; Ordinal

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

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