EFFICIENT BULK-LOADING OF GRIDFILES

This paper considers the problem of bulk-loading large data sets for t he gridfile multiattribute indexing technique. We propose a rectilinea r partitioning algorithm that heuristically seeks to minimize the size of the gridfile needed to ensure no bucket overflows. Empirical studi es on both synthetic data sets and on data sets drawn from computation al fluid dynamics applications demonstrate that our algorithm is very efficient, and is able to handle large data sets. In addition, we pres ent an algorithm for bulk-loading data sets too large to fit in main m emory. Utilizing a sort of the entire data set it creates a gridfile w ithout incurring any overflows.