Welcome to the InfoSci Platform
Reference Hub1
An Efficient Index Structure for Spatial Databases

An Efficient Index Structure for Spatial Databases

Kap S. Bang, Huizhu Lu
Copyright: © 1996 |Volume: 7 |Issue: 3 |Pages: 14
ISSN: 1063-8016|EISSN: 1533-8010|EISBN13: 9781466637986|DOI: 10.4018/jdm.1996070101
Cite Article Cite Article

MLA

Bang, Kap S., and Huizhu Lu. "An Efficient Index Structure for Spatial Databases." JDM vol.7, no.3 1996: pp.3-16. http://doi.org/10.4018/jdm.1996070101

APA

Bang, K. S. & Lu, H. (1996). An Efficient Index Structure for Spatial Databases. Journal of Database Management (JDM), 7(3), 3-16. http://doi.org/10.4018/jdm.1996070101

Chicago

Bang, Kap S., and Huizhu Lu. "An Efficient Index Structure for Spatial Databases," Journal of Database Management (JDM) 7, no.3: 3-16. http://doi.org/10.4018/jdm.1996070101

Export Reference

Mendeley
Favorite Full-Issue Download

Abstract

In this paper, the authors propose an efficient spatial data structure called the Multi-R tree. The Multi-R tree is an improvement of the R-tree, R+-tree and R*-tree, and can be used as an index structure for spatial databases. The Multi- R tree improves performance by distributing spatial objects into several data spaces instead of one data space in the Rtree, the R+-tree or the R*-tree. Each data space is associated with a tree in the Multi-R tree. The structure of the Multi-R tree eliminates the node redundancy which appears in the R+-tree at leaf level and keeps disjoint intermediate rectangles. A set of new algorithms for the Multi-R tree is also proposed and implemented. Three popular spatial data structures, the R-tree, R+-tree and R*-tree, are implemented based on the algorithms given in original literature to be compared with the Multi-R tree. An experimental performance analysis for four implemented structures is given with various types of testing data sets: random data, uniformly distributed data, VLSI layout data and TIGER/Line file. Namely, the number of disk accesses and actual response time for each of those four data structures to process a query are compared. Construction times, space utilization and actual memory sizes of the four data structures are also given. Results show that the Multi-R tree requires fewer disk accesses and less processing time than the R-tree, R+-tree and the R*-tree do for a deletion operation and answering a range query in most cases except for a point query or a range query with very small size. In the cases of a point query or small size query processing, the performance of the Multi-R tree is still better than the performances of the Rtree and R*-tree but slightly worse than the R+-tree. Thus, the Multi-R tree may be used as an efficient index structure for spatial databases, e.g., geographical information system, CAD, and VLSI etc.

Request Access

You do not own this content. Please login to recommend this title to your institution's librarian or purchase it from the IGI Global bookstore.