Collaborative Research: Information Theory of Data Structures

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

• 批准号: 0830140
• 负责人: Wojciech Szpankowski
• 金额: $ 28.21万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830140&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).

1953年，信息论创始人克劳德·香农（Claude Shannon）指出，没有任何理论可以量化结构中包含的信息;这种情况至今仍然有效。近年来，随着各种应用中结构化数据集的激增，对这种理论的需求变得越来越迫切。 我们还没有回答一些基本的问题，比如：结构信息的存储和处理的基本限制是什么？从大型生物数据库中提取信息的基本界限是什么？缺乏对这些问题的理解，可能会严重阻碍复杂系统科学和工程的进一步发展。 这项工作的主要目标是寻找度量和算法来评估人工制品和自然对象中体现的组织和结构的数量。我们建议在数据结构的信息理论方面取得进展。数据越来越多地以各种形式（例如，序列、表达、相互作用、结构）和呈指数增长的量。大多数这样的数据是多维的和上下文相关的，因此它需要新的理论和有效的算法来提取有意义的信息，从非传统的数据结构。在压缩这样的数据结构时，必须考虑两种类型的信息：由结构本身传递的信息，以及由植入结构中的数据标签传递的信息。 该项目的具体目标是：（i）表征数据结构所传达的信息总量（以及如何分解为上述两种类型的信息），以及（ii）基于（i）中传达的信息总量设计有效的压缩算法。