Bulk-loading of a multidimensional file: algorithm and its performance evaluation

摘要

The multilevel grid file (MLGF) is a multidimensional file supporting multi-attribute accesses efficiently. The efficient bulk-loading of a multidimensional file is very important in constructing a database since this should handle an enormous volume of objects. In this paper, we propose the MLGF_BulkLoad, a new algorithm for bulk-loading of the MLGF. The main feature of the MLGF_BulkLoad is to simultaneously process all the objects or directory entries to be placed on each page belonging to the MLGF when accessing the page. This avoids the overhead for accessing the same page multiple times, which results from applying the MLGF insertion algorithm repeatedly. The MLGF_BulkLoad consists of two phases. The first phase relocates all the objects in order that the logically-adjacent objects in multidimensional data space are clustered in one-dimensional physical space. For this, we employ the Z-transformation, which has been known to map effectively multidimensional space into one dimensional space preserving proximity. The second phase paginates the relocated objects and creates the leaf-level directory entries, each of which corresponds to the page containing a set of objects. Simultaneously, it performs the same actions on the directory entries recursively in a bottom-up fashion. For performance evaluation, we analyze the MLGF_BulkLoad in terms of the number of page accesses. The result shows the superiority of the MLGF_Bulk-Load. We also present performance tendency of the MLGF_BulkLoad according to the changes of various parameter values through simulation.