A balanced hierarchical data structure for multidimensional data with highly efficient dynamic characteristics

Author

Nakamura, Yasuaki ; Abe, Shigeru ; Ohsawa, Yutaka ; Sakauchi, Masao

Author_Institution

Mitsubishi Electric Corp., Hyogo, Japan

Volume

5

Issue

4

fYear

1993

fDate

8/1/1993 12:00:00 AM

Firstpage

682

Lastpage

694

Abstract

A new multidimensional data structure, multidimensional tree (MD-tree), is proposed. The MD-tree is developed by extending the concept of the 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 storage utilization is guaranteed to hold more than 66.7% (2/3) of full capacity. The structure of the MD-tree and the algorithms to perform the insertion, deletion, and spatial searching are described. By the series of simulation tests, the performances of the MD-tree and conventional methods are compared. The results indicate that storage utilization is more than 80% in practice, and that retrieval performance and dynamic characteristics are superior to conventional methods

Keywords

tree data structures; B-tree; balanced hierarchical data structure; deletion; dynamic characteristics; highly efficient dynamic characteristics; insertion; multidimensional data; multidimensional tree; retrieval performance; simulation; spatial searching; worst-case storage utilization; Binary trees; Data structures; Geographic Information Systems; Laboratories; Multidimensional systems; Nearest neighbor searches; Performance evaluation; Testing; Tree data structures;

fLanguage

English

Journal_Title

Knowledge and Data Engineering, IEEE Transactions on

Publisher

ieee

ISSN

1041-4347

Type

jour

DOI

10.1109/69.234779

Filename

234779