Study of Scalable Declustering Algorithms for Parallel Grid Files

Loading...
Thumbnail Image

Files

CS-TR-3589.ps (1.02 MB)
No. of downloads: 463
CS-TR-3589.pdf (680.46 KB)
No. of downloads: 932

Publication or External Link

Date

1998-10-15

Advisor

Citation

DRUM DOI

Abstract

Efficient storage and retrieval of large multidimensional datasets is an important concern for large-scale scientific computations such as long-running time-dependent simulations which periodically generate snapshots of the state. The main challenge for efficiently handling such datasets is to minimize response time for multidimensional range queries. The grid file is one of the well known access methods for multidimensional and spatial data. We investigate effective and scalable declustering techniques for grid files with the primary goal of minimizing response time and the secondary goal of maximizing the fairness of data distribution. The main contributions of this paper are (1) analytic and experimental evaluation of existing index-based declustering techniques and their extensions for grid files, and (2) development of a proximity-based declustering algorithm called {\em minimax} which is experimentally shown to scale and to consistently achieve better response time compared to available algorithms while maintaining perfect disk distribution. (Also cross-referenced as UMIACS-TR-96-4)

Notes

Rights