Accession Number:

ADA110403

Title:

Balanced Forests of K-D* Trees as a Dynamic Data Structure.

Descriptive Note:

Technical rept.,

Corporate Author:

HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB

Personal Author(s):

Report Date:

1978-11-01

Pagination or Media Count:

36.0

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 ON to the 1-sk and ON to the 1-1k 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 ON units of memory space. In view of Rivests earlier conjecture Ri 76, it may be that these results are the best attainable without substantially expanding memory space.

Subject Categories:

  • Information Science
  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE