Efficiency of Data Structures

数据结构的效率

• 批准号: RGPIN-2018-03972
• 负责人: Munro, Ian
• 金额: $ 4.01万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=711705
• 关键词: Efficiency; Data; Structures

This research lies at the heart of Data Structures and Algorithms, indeed at the heart of Computer Science itself. Most is motivated by applications on very large data sets; all is motivated by finding the "best possible way" to solve natural problems. The work is primarily mathematical in nature, developing data structures and proving lower bounds, but also includes some implementations. As demand for fast large information systems escalates, the manner in which data is organized and the algorithms used to manipulate information become increasingly critical. More time and space efficient methods must be created to allow large systems to better perform in response to sophisticated queries and updates. Space efficiency is crucial, not because of a shortage of storage in general, but because dramatic reduction in space requirements can allow the information required by a computation to be in a faster (smaller) level of memory when needed, thus drastically reducing the computation time. The principal focus of this research is to address several aspects of this issue. The first is that of succinct representations of data structures: the representation of structural information (search trees etc.) in the information theoretic minimum space while still permitting the required operations (navigation etc.) in constant time. A natural continuation of this is the application of succinct data structures to text indexing and to geometric problems. In tandem with this application-driven work is the fundamental notion of actually proving that the methods developed are indeed the best possible for the tasks at hand. A second line of research involves the computational complexity of comparison-based problems: issues such as sorting (or partially sorting) in the minimum number of comparisons. This latter work is primarily of theoretical interest and gives motivation for the development of various mathematical tools (such as graph entropy), but it also sheds light on the practical aspects of large scale computation. The work focuses on the intellectual development of the field, but also has real potential for immediate application and advancing Canada's software industry.

这项研究是数据结构和算法的核心，实际上是计算机科学本身的核心。大多数是由非常大的数据集的应用程序驱动的；这一切都是为了寻找解决自然问题的“最佳方法”。这项工作主要是数学性质的，开发数据结构和证明下界，但也包括一些实现。随着对快速大型信息系统需求的增加，组织数据的方式和用于操作信息的算法变得越来越重要。必须创建更节省时间和空间的方法，以使大型系统能够更好地响应复杂的查询和更新。空间效率是至关重要的，这并不是因为通常的存储不足，而是因为空间需求的大幅减少可以允许计算所需的信息在需要时存储在更快（更小）的内存级别，从而大大减少计算时间。本研究的主要重点是解决这一问题的几个方面。第一种是数据结构的简洁表示：在信息论最小空间中表示结构信息（搜索树等），同时仍然允许在恒定时间内进行所需的操作（导航等）。这方面的自然延续是将简洁的数据结构应用于文本索引和几何问题。与此应用程序驱动的工作相结合的是实际证明所开发的方法确实是手头任务的最佳可能的基本概念。第二条研究路线涉及基于比较的问题的计算复杂性：例如在最小比较数量中排序（或部分排序）的问题。后一项工作主要是理论性的，并为各种数学工具（如图熵）的发展提供了动力，但它也揭示了大规模计算的实际方面。这项工作侧重于该领域的智力发展，但也具有立即应用和推动加拿大软件产业发展的真正潜力。