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

随着社会和生命科学中大数据平台的出现，这对于开发有效的无损和有损数据压缩方法的重要性至关重要，以满足此类信息系统的需求。尽管对于经典文本，图像和视频数据存在许多近乎最佳的压缩方法，但它们在自然出现的数据上往往会表现不佳，而这些数据以碎片或有序形式出现。对于所谓的序数数据，尤其是在人群投票，推荐系统和基因组重排研究中产生的情况。在那里，信息表示相对的信息？而不是绝对？比例无法通过简单的词典结构正确捕获订购的特定约束。该项目旨在通过为序数数据压实开发理论，算法和软件解决方案，以改善许多数据管理，云计算和通信系统的运营性能。该项目的主要目标是开发第一个通用和全面的理论框架来进行序数。特别是，研究人员建议研究序数数据的新变形措施和损失序列压缩的率延伸功能；概率序数模型的秩集合和学习方法，用于顺序聚类和量化；以及顺序域中的平滑压缩和压缩计算。提出的分析框架还将允许在压缩完整，部分和弱排名的背景下解决算法挑战。随附的软件解决方案有望在理论计算机科学（分类，搜索和选择），机器学习（聚类和学习排名）以及基因优先和系统发育（分别重建有影响力的基因和祖先基因组清单的重建）等领域中找到广泛的应用。