AF: Small: Understanding Fudnamental Data Structures
AF: Small: Understanding Fudnamental Data Structures
批准号:
1018370
负责人:
John Iacono
金额:
$39.34万
依托单位:
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2010
资助国家:
美国
项目状态:
已结题
起止时间:
2010-07-01 至 2014-06-30
中文摘要
有效地存储和访问数据的需求是现代计算的核心,而存储和访问数据的方法的设计和分析构成了数据结构领域。这个项目将研究发现可证明的最佳数据结构的几个基本问题,包括字典和优先级队列。字典支持有序数据的有效插入、删除和搜索。优先级队列支持最小元素的插入和删除。数据结构将在基于实例的最优性范式下设计和分析。在这个模型中,一个数据结构在一个操作序列上的性能是根据它与自然定义的一类结构中该序列的最佳结构的速度进行比较来评估的。将被检查的结构类包括二叉搜索树和堆。二叉搜索树和堆可以说是计算机科学中最基本的非平凡数据结构类。尽管它们起源于计算的黎明,但直到今天,对这些类型的结构的完整理解仍然是难以捉摸的。减少堆中项的值的能力对一些算法至关重要,特别是Dijkstra的算法,用于在图中查找单源最短路径。然而,人们并不完全了解什么类型的结构可以有效地支持这一行动。此外,还没有已知的有效方法来支持字典的拆分和合并;这个项目的一个目标是设计一个基于比较的字典,在摊销对数时间内完成这一工作。
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
AF: SMALL: Fundamental Data Structures
-
批准号:1319648
-
项目类别:Standard Grant
-
资助金额:$51.59万
-
财政年份:2013
-
负责人:John Iacono
-
依托单位:
US-Belgium Cooperative Research: Retroactive Data Structures
-
批准号:0334653
-
项目类别:Standard Grant
-
资助金额:$0.0万
-
财政年份:2004
-
负责人:John Iacono
-
依托单位:
Understanding Binary Search Trees
-
批准号:0430849
-
项目类别:Standard Grant
-
资助金额:$0.0万
-
财政年份:2004
-
负责人:John Iacono
-
依托单位:
国内基金
海外基金
登录
查看更多内容
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2024
-
负责人:
-
依托单位:
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:10.0万元
-
批准年份:2022
-
负责人:张祥忠
-
依托单位:
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
-
批准号:32000033
-
项目类别:青年科学基金项目
-
资助金额:24.0万元
-
批准年份:2020
-
负责人:林平
-
依托单位:
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
-
批准号:31972324
-
项目类别:面上项目
-
资助金额:58.0万元
-
批准年份:2019
-
负责人:高学文
-
依托单位:
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
-
批准号:81900988
-
项目类别:青年科学基金项目
-
资助金额:21.0万元
-
批准年份:2019
-
负责人:毛梦莹
-
依托单位:
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
-
批准号:31870821
-
项目类别:面上项目
-
资助金额:56.0万元
-
批准年份:2018
-
负责人:陈江宁
-
依托单位:
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
-
批准号:31802058
-
项目类别:青年科学基金项目
-
资助金额:26.0万元
-
批准年份:2018
-
负责人:麻慧
-
依托单位:
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
-
批准号:31772128
-
项目类别:面上项目
-
资助金额:60.0万元
-
批准年份:2017
-
负责人:吴建国
-
依托单位:
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
-
批准号:81704176
-
项目类别:青年科学基金项目
-
资助金额:20.0万元
-
批准年份:2017
-
负责人:赵继梦
-
依托单位:
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
-
批准号:91640114
-
项目类别:重大研究计划
-
资助金额:85.0万元
-
批准年份:2016
-
负责人:何祖华
-
依托单位: