The DR-tree: A Main Memory Data Structure for Complex Multi-dimensional Objects
Source: GeoInformatica, Volume 5, Number 2, June 2001 , pp. 181-207(27)
Abstract:An efficient index structure for complex multi-dimensional objects is one of the most challenging requirements in non-traditional applications such as geographic information systems, computer-aided design, and multimedia databases. In this paper we first propose a main memory data structure for complex multi-dimensional objects. Then, we present an extension of the existing multi-dimensional index structure. Among existing multi-dimensional index structures, the popular R*-tree is selected. The R*-tree is coupled with the main memory data structure to improve the performance of spatial query processing. An analytical model is developed for our index structure. Experimental results show that the analytical model is accurate, the relative error being below 15%. The performance of our index structure is compared with that of a state-of-the-art index structure by experimental measurements. Our index structure outperforms the state-of-the-art index structure due to its ability to reduce a large amount of storage.
Document Type: Regular Paper
Affiliations: 1: Department of Computer Engineering, Sangju National University, 386, Gajang-dong, Sangju-si 741-711, Korea firstname.lastname@example.org 2: Department of Computer Science, Korea Advanced Institute of Science and Technology, 373-1, Kusong-dong, Yusong-gu, Taejon 305-701, Korea email@example.com
Publication date: 2001-06-01