Search Algorithms for Data Retrieval

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

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.