Efficiency of data structures

数据结构的效率

• 批准号: 8237-2007
• 负责人: Munro, Ian
• 金额: $ 6.7万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2011
• 资助国家: 加拿大
• 起止时间: 2011-01-01 至 2012-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=474352
• 关键词: Efficiency; 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.

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