A dynamic data structure for multi-dimensional range searching
Loading...
Files
Date
1996
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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 Q(n2lg4kn) and the dynamic balance cost is O(lg3kn). The optimal worst case range search time is O(lgkn + t) (where we report t points in range) for such structures. Structures optimal for range search in the class of dynamically balanced structures are illustrated and found to be within O(lgk-1n) of optimal.
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.