Y. Nakamura et al., A BALANCED HIERARCHICAL DATA STRUCTURE FOR MULTIDIMENSIONAL DATA WITHHIGHLY EFFICIENT DYNAMIC CHARACTERISTICS, IEEE transactions on knowledge and data engineering, 5(4), 1993, pp. 682-694
Citations number
18
Categorie Soggetti
Information Science & Library Science","Computer Sciences, Special Topics","Computer Applications & Cybernetics
A new multidimensional data structure, multidimensional tree (MD-tree)
, is proposed. The MD-tree is developed by extending the concept of th
e B-tree to the multidimensional data, so that the MD-tree is a height
balanced tree similar to the B-tree. The theoretical worst-case stora
ge utilization is guaranteed to hold more than 66.7%(2/3) of full capa
city. In this paper, the structure of the MD-tree and the algorithms t
o perform the insertion, deletion, and spatial searching am described.
By the series of simulation tests, the performances of the MD-tree an
d conventional methods are compared. The results indicate that storage
utilization is more than 80% in practice, and that retrieval performa
nce and dynamic characteristics are superior to conventional methods.