language: en

Storage of Two and Three Dimensional Raster Type Data for Optimized Retrieval of One, Two or Three Dimensional Features

Kjell Bratbergsengen
Department of Computer Systems and Information Science Norwegian University of Science and Technology,
Trondheim, Norway
email: kjellb@idi.ntnu.no

Abstract We are analyzing storage structures for two and three dimensional raster type data which are used for feature retrieval. The features are one, two or three dimensional objects with regular outlines like a rectangle or a prism. The features could be parts of a map or image, an area of special interest for searching after oil, a sequence of ultra sound images, and so on. The storage medium is magnetic disk. The data are stored in chunks or blocks representing a regular part of the source object. We analyze the shape and the size to minimize the cost of retrieval. The optimization is based on minimum time to do retrieval. We have five combinations: Lines and areas from areas and volumes, and volumes from volumes. The optimal block sizes for random retrieval varies, with case, feature size and disk characteristics. One general observation is that longer disk tracks gives larger blocks. For line retrieval the optimal block size is only depending on disk track length. For other cases it is also depending on the feature size. For partly sequential retrieval the block size is not the actual block size used during retrieval, but the smallest addressing unit, and the optimal addressing unit could be rather small. The analysis reveals that using too small blocks could be very costly. The time could easily double or triple if small blocks are used. In many cases the optimal block size is several tracks.

Keywords: storage and retrieval, matrix, optimization

1 Problem Introduction