AF: Small: Understanding Fudnamental Data Structures

AF：小：理解基本数据结构

• 批准号: 1018370
• 负责人: John Iacono
• 金额: $ 39.34万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-07-01 至 2014-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1018370&HistoricalAwards=false
• 关键词: AF; Small; Understanding; Fudnamental; Data

The need to efficiently store and access data is central to modern computing, and the design and analysis of methods to store and access data constitutes the field of data structures. This project will investigate the discovery of provably best data structures for several fundamental problems, including the dictionary and the priority queue. The dictionary supports the efficient insertion, deletion, and search of ordered data. The priority queue supports insertion and the removal of the minimum element.Data structures will be designed and analyzed under the paradigm of instance-based optimality. In this model, a data structure's performance on a sequence of operations is evaluated based on how well it compares to the speed of the best structure for that sequence among a naturally-defined class of structures. The classes of structures that will be examined include binary search trees and heaps. Binary search trees and heaps are arguably the most fundamental nontrivial classes of data structures in computer science. Despite their origins at the dawn of computing, a complete understanding of these classes of structures has remained elusive to this day.Other operations on fundamental data structures will be investigated. The ability to decrease the value of an item in a heap is vital to some algorithms, notably Dijkstra's algorithm for finding single-source shortest paths in a graph. Yet, it is not completely understood what types of structures can support this operation efficiently. Also, there is no known efficient method to support the splitting and merging of dictionaries; one goal of this project is to design a comparison-based dictionary do this in amortized logarithmic time.

有效地存储和访问数据的需求是现代计算的核心，而存储和访问数据的方法的设计和分析构成了数据结构领域。这个项目将研究发现可证明的最佳数据结构的几个基本问题，包括字典和优先级队列。字典支持有序数据的有效插入、删除和搜索。优先级队列支持最小元素的插入和删除。数据结构将在基于实例的最优性范式下设计和分析。在这个模型中，一个数据结构在一个操作序列上的性能是根据它与自然定义的一类结构中该序列的最佳结构的速度进行比较来评估的。将被检查的结构类包括二叉搜索树和堆。二叉搜索树和堆可以说是计算机科学中最基本的非平凡数据结构类。尽管它们起源于计算的黎明，但直到今天，对这些类型的结构的完整理解仍然是难以捉摸的。减少堆中项的值的能力对一些算法至关重要，特别是Dijkstra的算法，用于在图中查找单源最短路径。然而，人们并不完全了解什么类型的结构可以有效地支持这一行动。此外，还没有已知的有效方法来支持字典的拆分和合并;这个项目的一个目标是设计一个基于比较的字典，在摊销对数时间内完成这一工作。