| This thesis addresses the following question: Is it possible to have a k-dimensional data structure which provides for efficient k-d range search and dynamic updates on a set of n points in the worst case while maintaining reasonable storage and preprocessing requirements? Define a data structure to be optimally balanced when the product of its worst case preprocessing, storage, insertion, deletion, and range search cost functions is minimal and dynamically balanced when the product of its insert, delete and range search cost functions is minimal. The optimal balance cost is ;A new k-d structure labeled the k-d Range Deterministic Skip List (DSL) is defined and analyzed along with a new variation of the dynamic range tree labeled the k-d Range AVL tree. Both structures are dynamically balanced and optimal for worst case range search in the model. Experimentally, a mere 20 milliseconds was required to report all 500 datapoints in range for the largest 4-d structure (of 336 MB) built.;Both structures perform well. They possess similar update times but we find that the k-d Range DSL is approximately twice as fast as the k-d Range AVL tree for insertions while the k-d Range AVL tree is approximately fifteen times faster for deletions. |
