AF: Small: RUI: Towards Resolving the Dynamic Optimality Conjecture.
AF:小:RUI:解决动态最优猜想。
基本信息
- 批准号:1910873
- 负责人:
- 金额:$ 40万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2019
- 资助国家:美国
- 起止时间:2019-10-01 至 2024-09-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Searching is a fundamental problem in computer science, and faster search algorithms have been the focus of many researchers for decades. Being a basic primitive in all databases, fast searching in the age of big data has numerous applications in almost any field of data science. A binary search tree (BST) was one of the first and simplest data structures developed for searching, in which the keys in the database are stored in a binary tree, which allows an easy search algorithm to locate keys. In the real world, a sequence of searches come in an online fashion (the next search is revealed only after the current search is conducted), which led researchers to ask whether dynamically adjusting a BST may help access future (unknown) searches faster. While it may seem counterintuitive, for a wide variety of special search sequences, there exist online data structures that perform these searches almost as fast as the best offline algorithm -- one that knew all the searches in advance. Two such data structures are Splay Trees, developed by Sleator and Tarjan [1985] , and Greedy developed by Lucas [1988] and Munro [2000]. The dynamic optimality conjecture states that one of these online algorithms, in fact, accesses all sequences almost as fast as the optimal offline algorithm. This conjecture, widely regarded as one of fundamental problems in data structures, remains unresolved after 35 years. In this project the PI proposes three avenues to attack this conjecture. This project aims at producing the next generation of researchers and promoting under-represented groups in science and technology. Because of the simplicity of the conjecture, many undergraduate students will be able to understand it, appreciate the field of data structures, and thereby be motivated to pursue a career in computer science. The PI already has minority undergraduate and graduate students involved in this project. CUNY Queens College is a Hispanic-serving institution. The PI is committed to engaging more undergraduate students and women in research.The dynamic optimality conjecture is perhaps one of the most elusive unsolved problems in data structures. It postulates the existence of an online binary search tree (BST) which is O(1) competitive with the optimal offline self-balancing BST (called OPT). It is one of the simplest cases of instance optimality, and has been particularly elusive in that highly restricted consequences of the conjecture had remained open for three decades. The traversal conjecture and the weighted dynamic finger property are two recently settled conjectures (the former being resolved by the PI and his co-authors). After overcoming these last-remaining barriers, one needs a new set of barriers that will get us closer to proving or disproving dynamic optimality for the two main candidates, Splay trees and Greedy. The PI maps out a plan to attack this conjecture.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
搜索是计算机科学中的一个基本问题,快速搜索算法几十年来一直是许多研究人员关注的焦点。作为所有数据库中的基本元素,大数据时代的快速搜索在几乎所有数据科学领域都有许多应用。二叉搜索树(BST)是为搜索而开发的第一个也是最简单的数据结构之一,其中数据库中的键存储在二叉树中,这允许简单的搜索算法来定位键。在真实的世界中,一系列搜索以在线方式出现(下一个搜索只有在当前搜索进行之后才会显示),这导致研究人员询问动态调整BST是否有助于更快地访问未来(未知)搜索。虽然这看起来似乎违反直觉,但对于各种特殊的搜索序列,存在在线数据结构,它们执行这些搜索的速度几乎与最好的离线算法一样快-一种预先知道所有搜索的算法。两种这样的数据结构是Splay Trees,由Sleator和Tarjan [1985]开发,以及Greedy,由Lucas [1988]和Munro [2000]开发。动态最优性猜想指出,这些在线算法之一,事实上,访问所有序列几乎一样快的最佳离线算法。这个猜想被广泛认为是数据结构中的基本问题之一,35年后仍然没有得到解决。在这个项目中,PI提出了三种方法来攻击这个猜想。 该项目旨在培养下一代研究人员,促进科学和技术领域代表性不足的群体。由于猜想的简单性,许多本科生将能够理解它,欣赏数据结构领域,从而有动力追求计算机科学的职业生涯。PI已经有少数民族本科生和研究生参与了这个项目。纽约市立大学皇后学院是一所为西班牙裔服务的机构。PI致力于吸引更多的本科生和女性参与研究。动态最优性猜想可能是数据结构中最难以捉摸的未解决问题之一。它假设存在一个在线二叉搜索树(BST),这是O(1)的最佳离线自平衡BST(称为OPT)的竞争。这是实例最优性的最简单的例子之一,并且特别难以捉摸,因为这个猜想的高度限制的结果已经开放了30年。遍历猜想和加权动态指属性是最近解决的两个猜想(前者由PI和他的合著者解决)。在克服了这些最后剩下的障碍之后,我们需要一组新的障碍,这将使我们更接近于证明或反驳两个主要候选者的动态最优性,即Splay树和Greedy。PI制定了一个计划来攻击这个猜想。这个奖项反映了NSF的法定使命,并被认为值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估。
项目成果
期刊论文数量(10)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Batched Predecessor and Sorting with Size-Priced Information in External Memory
批处理前驱和外部存储器中按大小定价的信息排序
- DOI:10.1007/978-3-030-61792-9_13
- 发表时间:2021
- 期刊:
- 影响因子:0
- 作者:Bender, Michael A;Goswami, Mayank;Medjedovic, Dzejla;Montes, Pablo;Tsichlas, Kostas
- 通讯作者:Tsichlas, Kostas
Stability of SGD: Tightness Analysis and Improved Bounds
- DOI:
- 发表时间:2021-02
- 期刊:
- 影响因子:0
- 作者:Yikai Zhang;Wenjia Zhang-;Sammy Bald;Vamsi Pingali;Chao Chen;Mayank Goswami
- 通讯作者:Yikai Zhang;Wenjia Zhang-;Sammy Bald;Vamsi Pingali;Chao Chen;Mayank Goswami
Topological Detection of Trojaned Neural Networks
- DOI:
- 发表时间:2021-06
- 期刊:
- 影响因子:0
- 作者:Songzhu Zheng;Yikai Zhang;H. Wagner;Mayank Goswami;Chao Chen
- 通讯作者:Songzhu Zheng;Yikai Zhang;H. Wagner;Mayank Goswami;Chao Chen
Learning to Segment from Noisy Annotations: A Spatial Correction Approach
- DOI:10.48550/arxiv.2308.02498
- 发表时间:2023-07
- 期刊:
- 影响因子:0
- 作者:Jiacheng Yao;Yikai Zhang;Songzhu Zheng;Mayank Goswami;P. Prasanna;Chao Chen
- 通讯作者:Jiacheng Yao;Yikai Zhang;Songzhu Zheng;Mayank Goswami;P. Prasanna;Chao Chen
Obtaining Approximately Optimal and Diverse Solutions via Dispersion
通过分散获得近似最优且多样化的解
- DOI:
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Gao, Jie;Goswami, Mayank;C.S., Karthik;Tsia, Meng-Tsung;Tsai, Shih-Yu;Yang Hao-Tsung
- 通讯作者:Yang Hao-Tsung
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Mayank Goswami其他文献
Weakly confined silicon nano-structures as a THz absorbing material
弱约束硅纳米结构作为太赫兹吸收材料
- DOI:
10.1063/5.0204896 - 发表时间:
2024 - 期刊:
- 影响因子:0
- 作者:
Pooja Sudha;Mayank Goswami;Arup Samanta - 通讯作者:
Arup Samanta
Adaptive Discretization for Computerized Tomography
计算机断层扫描的自适应离散化
- DOI:
- 发表时间:
2018 - 期刊:
- 影响因子:0
- 作者:
S. Shakya;A. Saxena;P. Munshi;Mayank Goswami - 通讯作者:
Mayank Goswami
Fair subgraph selection for contagion containment (Brief Announcement)
- DOI:
10.1016/j.procs.2023.08.250 - 发表时间:
2023-01-01 - 期刊:
- 影响因子:
- 作者:
Esther M. Arkin;Rezaul A. Chowdhury;Mayank Goswami;Jason Huang;Joseph S.B. Mitchell;Valentin Polishchuk;Rakesh Ravindran - 通讯作者:
Rakesh Ravindran
Pattern-Avoiding Access in Binary Search Trees
二叉搜索树中避免模式访问
- DOI:
10.1109/focs.2015.32 - 发表时间:
2015 - 期刊:
- 影响因子:0
- 作者:
Parinya Chalermsook;Mayank Goswami;L. Kozma;K. Mehlhorn;Thatchaphol Saranurak - 通讯作者:
Thatchaphol Saranurak
Missing Motility: High-resolution in vivo imaging of retinal microglia reveals stationary ramified cells.
运动性缺失:视网膜小胶质细胞的高分辨率体内成像揭示了静止的分支细胞。
- DOI:
- 发表时间:
2016 - 期刊:
- 影响因子:0
- 作者:
Eric B. Miller;Pengfei Zhang;Mayank Goswami;R. Zawadzki;E. Pugh;M. E. Burns - 通讯作者:
M. E. Burns
Mayank Goswami的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Mayank Goswami', 18)}}的其他基金
CRII: AF: RUI: Faster and Cache-Efficient Similarity Filters and Searches for Big Data
CRII:AF:RUI:更快且高效缓存的相似性过滤器和大数据搜索
- 批准号:
1755791 - 财政年份:2018
- 资助金额:
$ 40万 - 项目类别:
Standard Grant
相似国自然基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
- 批准号:32000033
- 批准年份:2020
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
- 批准号:31972324
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
- 批准号:81900988
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
AF: Small: RUI: Toward High-Performance Block Krylov Subspace Algorithms for Solving Large-Scale Linear Systems
AF:小:RUI:用于求解大规模线性系统的高性能块 Krylov 子空间算法
- 批准号:
2327619 - 财政年份:2023
- 资助金额:
$ 40万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: RUI: Data Science from Economic Foundations
合作研究:AF:小型:RUI:来自经济基础的数据科学
- 批准号:
2218814 - 财政年份:2022
- 资助金额:
$ 40万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: RUI: Data Science from Economic Foundations
合作研究:AF:小型:RUI:来自经济基础的数据科学
- 批准号:
2218813 - 财政年份:2022
- 资助金额:
$ 40万 - 项目类别:
Standard Grant
AF: Small: RUI: Competitive Search, Evacuation and Reconfiguration with Coordinated Mobile Agents
AF:小型:RUI:通过协调移动代理进行竞争性搜索、疏散和重新配置
- 批准号:
1813940 - 财政年份:2018
- 资助金额:
$ 40万 - 项目类别:
Standard Grant
AF: Small: RUI: Unifying Self-Assembly Through Tile Automata
AF:小:RUI:通过平铺自动机统一自组装
- 批准号:
1817602 - 财政年份:2018
- 资助金额:
$ 40万 - 项目类别:
Standard Grant
AF: Small: RUI: New Directions in Kolmogorov Complexity and Network Information Theory
AF:小:RUI:柯尔莫哥洛夫复杂性和网络信息理论的新方向
- 批准号:
1811729 - 财政年份:2018
- 资助金额:
$ 40万 - 项目类别:
Standard Grant
AF: Small: RUI: The model-based approach and a new kind of Cylindrical Algebraic Decomposition
AF:小:RUI:基于模型的方法和一种新型圆柱代数分解
- 批准号:
1525896 - 财政年份:2015
- 资助金额:
$ 40万 - 项目类别:
Interagency Agreement
AF: Small: RUI: Faster Arithmetic for Sparse Polynomials and Integers
AF:小:RUI:稀疏多项式和整数的更快算术
- 批准号:
1319994 - 财政年份:2013
- 资助金额:
$ 40万 - 项目类别:
Interagency Agreement
AF: Small: RUI: A new and improved algorithm for fitting RNA backbone in crystallographic data
AF:小:RUI:一种新的改进算法,用于在晶体学数据中拟合 RNA 主链
- 批准号:
1218145 - 财政年份:2012
- 资助金额:
$ 40万 - 项目类别:
Standard Grant
AF: Small: RUI: Network design and facility location problems
AF:小:RUI:网络设计和设施选址问题
- 批准号:
1218620 - 财政年份:2012
- 资助金额:
$ 40万 - 项目类别:
Standard Grant