An Efficient Index Structure for Spatial Databases

An Efficient Index Structure for Spatial Databases

Kap S. Bang, Huizhu Lu
Copyright: © 1996 |Pages: 14
DOI: 10.4018/jdm.1996070101
OnDemand:
(Individual Articles)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

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.

Complete Article List

Search this Journal:
Reset
Volume 35: 1 Issue (2024)
Volume 34: 3 Issues (2023)
Volume 33: 5 Issues (2022): 4 Released, 1 Forthcoming
Volume 32: 4 Issues (2021)
Volume 31: 4 Issues (2020)
Volume 30: 4 Issues (2019)
Volume 29: 4 Issues (2018)
Volume 28: 4 Issues (2017)
Volume 27: 4 Issues (2016)
Volume 26: 4 Issues (2015)
Volume 25: 4 Issues (2014)
Volume 24: 4 Issues (2013)
Volume 23: 4 Issues (2012)
Volume 22: 4 Issues (2011)
Volume 21: 4 Issues (2010)
Volume 20: 4 Issues (2009)
Volume 19: 4 Issues (2008)
Volume 18: 4 Issues (2007)
Volume 17: 4 Issues (2006)
Volume 16: 4 Issues (2005)
Volume 15: 4 Issues (2004)
Volume 14: 4 Issues (2003)
Volume 13: 4 Issues (2002)
Volume 12: 4 Issues (2001)
Volume 11: 4 Issues (2000)
Volume 10: 4 Issues (1999)
Volume 9: 4 Issues (1998)
Volume 8: 4 Issues (1997)
Volume 7: 4 Issues (1996)
Volume 6: 4 Issues (1995)
Volume 5: 4 Issues (1994)
Volume 4: 4 Issues (1993)
Volume 3: 4 Issues (1992)
Volume 2: 4 Issues (1991)
Volume 1: 2 Issues (1990)
View Complete Journal Contents Listing