Efficiency of data structures

今天的信息系统的规模和复杂性使五年前相形见绌，更不用说二十年前了。现代工业应用程序对具有更大内存的更快系统的需求正在从包含数十亿字节或千兆字节信息的“大型”数据库转移到数兆字节(万亿字节)范围内的专用系统。随着需求的升级，组织数据的方式和用于处理信息的算法(或问题解决方法)变得越来越关键。必须创造解决时间和空间限制的更有效的技术，以使大型系统能够更好地执行搜索操作，以响应复杂的查询和更新。特别是，这项工作将集中在数据结构的简洁表示及其在文本索引中的应用，以及在复杂的内存层级结构中高效工作的结构。与这种应用程序驱动的工作相结合的是一个基本概念，即实际证明所开发的方法确实是手头任务的最佳可能。

The size and complexity of today's information systems dwarf those of five, let alone twenty, years ago. The demands of modern industrial applications for faster systems with greater memories are moving from "large" databases comprising a few billion bytes, or gigabytes, of information to specialized systems in the range of many terabytes (trillions of bytes). As demand escalates, the manner in which data is organized and the algorithms (or problem-solving methods) used to manipulate information become increasingly critical. More effective techniques, that address time and space constraints, must be created to allow large systems to better perform search operations in response to sophisticated queries and updates. In particular, this work will focus on succinct representations of data structures and their application to text indexing, as well as structures working efficiently in a complex memory heirarchy. 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.