Balanced Forests of K-D* Trees as a Dynamic Data Structure.
Abstract
This paper presents an algorithm that optimizes the worst-case performance of a dynamically changing k-d tree-like structure. Our proposed algorithm will have an O logs n to the base 2 worst-case insertion and deletion runtime. It will insure that partial match and region queries can be performed in the same O(N to the 1-s/k) and O(N to the 1-1/k) retrieval times previously attributed to k-d trees. The coefficient associated with our dynamic retrieval algorithm will be only slightly larger than that of the previous static algortihms. The data structure employed here will consist of a forest of trees whose members are slightly modified versions of k-d trees designated as k-d* trees. The salient characteristic of this forest is that the number and height of its trees will be sufficiently controlled to insure efficient worst-case runtime. A brief discussion of attempts to apply AVL or bounded balance techniques to k-d trees will also be found in this paper (based on generalizations of AVL-62 and NR-73). Such techniques will be shown to be inherently less efficient than our balanced forests of k-d trees. Our discussion will be primarily theoretical. Its results are significant because they contain the best combination of multidimensional retrieval and update runtime thus far derived for a dynamic data structure which occupies O(N) units of memory space. In view of Rivest's earlier conjecture (Ri 76), it may be that these results are the best attainable without substantially expanding memory space.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1978
- Accession Number
- ADA110403
Entities
People
- Dan E. Willard
Organizations
- Harvard University