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.