Published Articles >> Table of Contents >> Abstract

15th International Conference on Scientific and Statistical Database Management   p. 225
The Evolution of a Hierarchical Partitioning Algorithm for Large-Scale Scientific Data: Three Steps of Increasing Complexity
Chuck Baldwin, Lawrence Livermore National Laboratory
Tina Eliassi-Rad, Lawrence Livermore National Laboratory
Ghaleb Abdulla, Lawrence Livermore National Laboratory
Terence Critchlow, Lawrence Livermore National Laboratory

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SSDM.2003.1214983
Send link to a friend

Abstract
As scientific data sets grow exponentially in size, the need for scalable algorithms that heuristically partition the data increases. In this paper, we describe the three-step evolution of a hierarchical partitioning algorithm for large-scale spatio-temporal scientific data sets generated by massive simulations. The first version of our algorithm uses a simple top-down partitioning technique, which divides the data by using a four-way bisection of the spatio-temporal space. The shortcomings of this algorithm lead to the second version of our partitioning algorithm, which uses a bottom-up approach. In this version, a partition hierarchy is constructed by systematically agglomerating the underlying Cartesian grid that is placed on the data. Finally, the third version of our algorithm utilizes the intrinsic topology of the data given in the original scientific problem to build the partition hierarchy in a bottom-up fashion. Specifically, the topology is used to heuristically agglomerate the data at each level of the partition hierarchy. Despite the growing complexity in our algorithms, the third version of our algorithm builds partition hierarchies in less time and is able to build trees for larger size data sets as compared to the previous two versions.
Back to Top Additional Information
Citation:  Chuck Baldwin, Tina Eliassi-Rad, Ghaleb Abdulla, Terence Critchlow, "The Evolution of a Hierarchical Partitioning Algorithm for Large-Scale Scientific Data: Three Steps of Increasing Complexity," ssdbm, p. 225,  15th International Conference on Scientific and Statistical Database Management,  2003