RMD-tree: A hierarchical data structure for multidimensional nonzero size spatial objects using MD-tree
✍ Scribed by Yasuaki Nakamura; Shigeru Abe; Yutaka Ohsawa; Masao Sakauchi
- Publisher
- John Wiley and Sons
- Year
- 1992
- Tongue
- English
- Weight
- 906 KB
- Volume
- 23
- Category
- Article
- ISSN
- 0882-1666
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
This paper proposes an RMD‐tree (region multidimensional tree), which is a method of data management based on the tree structure, aiming at the efficient management and retrieval of spatial objects with nonzero sizes.
In the proposed method, the spatial object in the N‐dimensional space corresponds to a point in the 2__N__‐dimensional space, being represented by its centroid and the extent along each axis. The coordinate transformation is applied to the point data and the data are managed by the tree structure, so that retrieval such as the point location problem or the range search in the n‐dimensional space can be performed only by the search for the point data in the hyper‐rectangle range.
By this approach, the space splitting and data management are made possible considering the size of the object as well as the centroid. By the coordinate transformation the object data are represented by the maximum and the minimum in the original N‐dimensional space, multiplied by a certain factor.
It is indicated by simulation experiments that the speed of search is improved by this method by a factor of 2 to 4, compared to the conventional method when the size of the object to be managed is enlarged. When points and objects with small sizes are to be handled, the performance is almost the same as that of the conventional method. In the experiment using the actual printed circuit board data, the speed of search also is improved by approximately a factor of 2.