Efficiency of 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.