Efficiency of Data Structures

数据结构的效率

• 批准号: 8237-2012
• 负责人: Munro, Ian
• 金额: $ 6.7万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=544496
• 关键词: 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高效算法的方法来解决，包括缓存无关技术（其中不包括内存的细节，因此同时适用于内存层次结构的所有级别）。与这种应用程序驱动的工作相结合的是实际证明所开发的方法确实是手头任务的最佳可能的基本概念。第二条研究线涉及基于比较的问题的计算复杂性：例如在最小数量的比较中排序（或部分排序）的问题。后者的工作主要是理论上的兴趣，并为各种数学工具（如图熵）的发展提供了动力，但它也揭示了大规模计算的实际方面。这项工作的重点是该领域的智力发展，但也有真实的潜力，可立即应用和推动加拿大的软件业。