Efficiency of Data Structures

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

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.