Data Structures for Sorting, Searching, Hashing, Computational Geometry and Nonprocedural Databases

适应快速检索的数据结构可能是计算机科学中最古老、最基本的主题之一。这个项目解决了几个实用和理论上的开放性问题。第一组开放问题涉及优于信息理论下界的最坏情况算法。最近设计了一种O（log N/log log N）最坏时间的动态树操作算法和一种O（N log N/log log N）最坏时间排序算法。这两种算法基本上都可以在所有数字计算机和所有可能的数据输入上运行。排序和搜索的新方法依赖于利用数字计算机的算术和按位逻辑运算的能力。关于排序、搜索、平衡树操作和散列的上界和下界可以在这个修改后的数学模型中演示的许多开放问题出现了。第二个研究领域是计算几何。许多几何问题，如Voronoi图的构造，被认为至少需要N log N时间，因为它们被简化为排序过程，但所有这些理论下界都需要根据最近排序和搜索的结果重新考虑。范围查询理论的早期研究也提出了几个悬而未决的问题。一个特定的问题涉及到考虑减法存在的下限的开发，第二个问题涉及到特别是报告查询的时间空间权衡。批量查询的范围查询算法，特别是执行关系演算和类似setl表达式的过程，也将被研究。

Data structures to accommodate fast retrieval are perhaps the oldest and certainly one of the most fundamental topics in computer science. This project addresses several open problems of both pragmatic and theoretical interest. The first group of open questions concerns worst-case algorithms that outperform the information theoretical lower bound. Recently an O(log N/log log N) worst-case time algorithm for dynamic tree operations and an accompanying O(N log N/log log N) worst-case time sorting algorithm have been designed. Both algorithms run on essentially all digital computers and on all possible data inputs. The new approach to sorting and searching rests on utilizing the power of a digital computer's arithmetic and bitwise logical operations. Numerous open questions arise about what upper and lower bounds for sorting, searching, balance tree operations, and hashing can be demonstrated in this modified mathematical model. A second research area focuses on computational geometry. Many geometric problems, such as Voronoi diagram construction, have been thought to require at least N log N time because of their reduction to sorting procedures, but all such theoretical lower bounds need to be reconsidered in light of the recent results for sorting and searching. There are also several open questions raised by earlier research into range query theory. One particular question concerns developing lower bounds that take into account the presence of subtraction, and a second concerns the time-space tradeoff for especially reporting queries. Range query algorithms for batch queries, especially procedures for executing relational calculus and SETL-like expressions, will also be studied.