Search Algorithms for Data Retrieval

从实用和理论的角度考虑了三组关于计算几何和数据库管理中的排序、搜索和相关问题的未决问题。(1)第一组问题涉及最近引入的融合树数据结构。融合树可以在O(logN/loglogN)的最坏情况下执行树的搜索和更新操作，并且支持最坏情况的O(NxlogN/logN)的排序时间。这些结果通过利用数字计算机的能力在恒定的时间内执行算术和按位逻辑运算来绕过信息论下限。在这个数学模型中，出现了许多关于排序、搜索、平衡树操作和散列的上下限的未决问题。第二个目标是检查算法，以提高关系演算、低密度脂蛋白和SETL查询的性能。它的目标是研究与数据库性能相关的理论和实用问题。这项研究既考察了将一般查询分解为组成部分的方法，也考察了处理这些单独部分的基本搜索算法。这项研究还包括对统计抽样对提高算法性能的影响的检查。(3)第三个研究领域是计算几何领域。讨论了该主题对关系数据库的影响。还研究了融合树对几何搜索算法的影响。这一计算几何的研究包括对范围查询算法的先前研究的继续，并特别关注聚集范围查询的加减运算数量的下界问题。

Three groups of open questions concerning sorting, searching, and related problems in computational geometry and database management are considered from both a pragmatic and theoretical perspective. (1) The first group of questions concerns the recently introduced fusion tree data structure. Fusion trees can perform dynamic tree search-and-update operations in O( logN / log logN ) worst-case time, and they support a worst- case time O(NxlogN/loglogN) for sorting. These results circumvent the Information Theoretic Lower Bound by utilizing the power of a digital computer for performing arithmetic and bitwise logical operations in constant time. Numerous open questions arise about upper and lower bounds for sorting, searching, balance tree operations, and hashing in this mathematical model. The second goal is to examine algorithms in order to improve the performance of relational calculus, LDL and SETL queries. Its goal is to study both theoretical and pragmatic issues related to data base performance. This study examines both the methods for decomposing a general query into component parts, and the underlying search algorithms to process these individual parts. The research also includes an examination of the implications of statistical sampling to improve algorithmic performance. (3) The third research area is in the domain of computational geometry. The implications of this subject for relational databases are considered. Also investigated are the implications that fusion trees have for geometric search algorithms. This study of computational geometry includes a continuation of a prior investigation into range query algorithms, and special attention is given to the problem of lower bounding the number of addition-subtraction operations for an aggregate range query.