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

点击翻译按钮获取中文摘要

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.