AF: Small: RUI: Towards Resolving the Dynamic Optimality Conjecture.

搜索是计算机科学中的一个基本问题，而更快的搜索算法几十年来一直是许多研究人员关注的焦点。作为所有数据库中的基本原语，大数据时代的快速搜索在几乎任何数据科学领域都有许多应用。二叉树(BST)是为搜索而开发的最早也是最简单的数据结构之一，其中数据库中的关键字存储在二叉树中，这允许一种简单的搜索算法来定位关键字。在现实世界中，一系列搜索是以在线方式进行的(只有在进行当前搜索后才会显示下一次搜索)，这导致研究人员询问，动态调整BST是否有助于更快地访问未来(未知)搜索。虽然这看起来可能有悖常理，但对于各种各样的特殊搜索序列，存在着执行这些搜索的在线数据结构，其执行速度几乎与最好的离线算法一样快--一种提前知道所有搜索的算法。两种这样的数据结构是Sleator和Tarjan[1985]开发的Splay树，以及Lucas[1988]和Munro[2000]开发的贪婪。动态最优性猜想指出，事实上，这些在线算法之一访问所有序列的速度几乎与最优离线算法一样快。这一猜想被广泛认为是数据结构中的基本问题之一，但在35年后仍未得到解决。在这个项目中，PI提出了三种方法来反驳这一猜想。该项目旨在培养下一代研究人员，并促进科学和技术领域中代表性不足的群体。由于猜想的简单性，许多本科生将能够理解它，欣赏数据结构领域，从而有动力追求计算机科学的职业生涯。PI已经有少数族裔本科生和研究生参与了这个项目。纽约州立大学皇后学院是一所为拉美裔服务的机构。PI致力于吸引更多的本科生和女性参与研究。动态最优猜想可能是数据结构中最难以捉摸的未解决问题之一。它假定存在一个与最优离线自平衡BST(称为OPT)竞争O(1)的在线二叉搜索树(BST)。这是实例最优的最简单情况之一，尤其难以捉摸，因为该猜想的高度受限的后果三十年来一直是公开的。遍历猜想和加权动态手指性质是最近确定的两个猜想(前者由Pi和他的合著者解决)。在克服了这些最后剩下的障碍之后，人们需要一组新的障碍，让我们更接近于证明或反驳两个主要候选者--Splay Trees和贪婪--的动态最优性。这个奖项反映了NSF的法定使命，通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.