Collaborative Research: Information Theory of Data Structures

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

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