Spatial indexing of large volume bathymetric data sets
Loading...
Files
Date
1993
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Three spatial index structures based on Morton code sequence and R-tree indices were designed and implemented Indices for the Hydrographic Data Cleaning System (HDCS) were built with Morton sequence and R-tree structures directly implemented in the C language, and with Morton sequence structures managed by the INGRES relational database management system. A modified deletion algorithm for the R-tree index structure was developed. To test the software and to evaluate the implementation of the structures, experiments were carried out with a bathymetric data set surveyed in Conception Bay, Canada. Spanning four days, the survey includes 46 lines consisting of 54,192 profiles each of which contains 32 sounding points. The total amount of data is 128.9 megabytes. It is shown that R-tree indexing is superior to Morton sequence indexing by providing five to nine times faster range search speed, occupying less disk space, and better supporting the range deletion operation. Range deletion with the modified algorithm was 11.7 times faster, on average, than Guttman's original deletion algorithm. The experiment also showed that, on average, the INGRES RDBMS build time was 31.7 times slower than building the Morton sequence implemented in C, search time is 176 times slower than searching the Morton sequence, and occupied 4.4 times more space. The three spatial index structures, Morton sequence, R-tree and INGRES Morton sequence, required additional 1.9%, 1.7% and 7.9% of the original file storage for the HDCS data, respectively.