Efficiency of Data Structures

数据结构的效率

• 批准号: 8237-2012
• 负责人: Munro, Ian
• 金额: $ 6.7万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2013
• 资助国家: 加拿大
• 起止时间: 2013-01-01 至 2014-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=521104
• 关键词: 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. 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. Another crucial issue is having the required data at the appropriate level in the memory hierarchy. This will be addressed through several approaches to I/O-efficient algorithms including cache-oblivious techniques (ones in which details of memory are not included and so apply simultaneously at all levels of the memory hierarchy). 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.

这项研究是数据结构和算法的核心，实际上也是计算机科学本身的核心。大多数的动机是在非常大的数据集上的应用程序；所有的动机都是为了找到解决自然问题的“可能的最佳方法”。这项工作主要是数学性质的，开发数据结构和证明下限，但也包括一些实现。随着对快速大型信息系统的需求升级，数据的组织方式和用于处理信息的算法变得越来越关键。必须创建更多时间和空间高效的方法，以使大型系统能够更好地响应复杂的查询和更新。这项研究的主要焦点是解决这个问题的几个方面。第一种是数据结构的简洁表示：结构信息(搜索树等)的表示。在信息论的最小空间中，同时仍允许所需的操作(导航等)在恒定的时间里。它的一个自然延续是将简洁的数据结构应用于文本索引和几何问题。另一个关键问题是将所需数据放在内存层次结构中的适当级别。这将通过几种I/O高效算法的方法来解决，包括缓存无关技术(其中不包括内存细节，因此同时应用于内存层次的所有级别)。与这种应用程序驱动的工作并驾齐驱的是一个基本概念，即实际证明所开发的方法确实是手头任务的最佳可能。第二类研究涉及基于比较的问题的计算复杂性：在最少的比较次数中进行排序(或部分排序)等问题。后一项工作主要是理论上的兴趣，并为各种数学工具(如图熵)的发展提供了动力，但它也揭示了大规模计算的实际方面。这项工作专注于该领域的智力发展，但也具有立即应用和推动加拿大软件产业的真正潜力。