Collaborative Research: Information Theory of Data Structures

合作研究：数据结构信息论

• 批准号: 0830457
• 负责人: John Kieffer
• 金额: $ 8.75万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830457&HistoricalAwards=false
• 关键词: Collaborative; Research; Information; Theory; Data

In 1953, Claude Shannon, the founder of information theory, pointed out that there is no theory via which information embodied in structure can be quantified; this situation remains in effect today. The need for such a theory has become pressing in recent years with the proliferation of structured data sets arising from diverse applications. We have yet to answer fundamental questions such as:What are fundamental limits on storage and processing of structural information? What are fundamental bounds on extraction of information from large biological databases? Lack of understanding of such questions threatens to raise severe impediments to further advances in science and engineering of complex systems. The main goal of this work is to search for measures and algorithms to appraise the amount of organization and structure embodied in artifacts and natural objects.We propose to make headway in information theory of data structures.Data is increasingly available in various forms (e.g., sequences, expressions, interactions, structures) and in exponentially increasing amounts. Most of such data is multidimensional and context dependent; thus it necessitates novel theory and efficient algorithms to extract meaningful information from non-conventional data structures. In compressing such a data structure, one must take into account two types of information: the information conveyed by the structure itself, and then the information conveyed by the data labels implanted in the structure. The specific goals of this project are: (i) characterization of the total amount of information conveyed by a data structure (and how this decomposes into the two types of information mentioned above), and (ii) the design of efficient compression algorithms based upon the total amount of information conveyed in (i).

信息理论的创始人克劳德·香农（Claude Shannon）在1953年指出，没有理论可以量化结构中的信息。今天这种情况仍然有效。近年来，随着各种应用程序引起的结构化数据集的扩散，对这种理论的需求变得越来越紧迫。 我们尚未回答基本问题，例如：储存和处理结构信息的基本限制是什么？从大型生物数据库中提取信息的基本范围是什么？对此类问题的缺乏理解可能会增加严重的障碍，以进一步发展复杂系统的科学和工程。 这项工作的主要目的是寻找措施和算法，以评估伪像和自然对象体现的组织和结构的数量。我们建议在数据结构的信息理论中取得进展。DATA越来越多地以各种形式获得（例如，序列，表达式，表达式，互动，结构）以及实用的增加量。大多数此类数据都是多维和上下文依赖性的。因此，它需要新颖的理论和有效算法才能从非规定数据结构中提取有意义的信息。在压缩这种数据结构时，必须考虑两种类型的信息：结构本身传达的信息，然后考虑到结构中植入的数据标签传达的信息。 该项目的具体目标是：（i）表征数据结构传达的信息总量（以及如何将其分解为上面提到的两种信息），以及（ii）基于（i）中传达的信息总量的设计有效压缩算法的设计。