(A) disk allocation method using genetic algorithm for cartesian product files

Abstract

The disk allocation problem examined in this thesis is finding a method to distribute Binary Cartesian Product Files on multiple disks to maximize parallel disk I/O accesses for partial match retrieval. This problem is known to be NP-hard, and heuristic approaches have been applied to obtain suboptimal solutions. Recently, efficient heuristic methods such as Binary Disk Modulo(BDM) and Error Correcting Code(ECC) methods have been proposed along with the restriction that the number of disks in which files are stored should be a power of 2. However, restriction on the number of applied disks causes the problems of economics and spaces, when more disks should be added to extend the size of the file system. Moreover, all of the proposed methods do not consider the data access patterns. In real databases, reflecting a known access pattern on the disk allocation method is very important for improving query access time. The design of a new disk allocation scheme which has no restriction on the number of disks and reflects the data access patterns, is the main theme of this thesis. As a first step of designing a new disk allocation method, a bucketvector and a disk mapping function have been defined. A bucketvector is a permutation of buckets which will be allocated to the disks. The disk mapping function maps the buckets to the disks only by using the position indexes of buckets in the bucketvector and no restriction is assumed on the number of disks. Thus, if the bucket permutations are different, the different results of bucket mappings are obtained. Then, the disk allocation problem is translated into a searching problem to find a best bucketvector among many candidates. The most distinctive feature of the proposed method is in the searching mechanism, in which the fitness values of a group of solutions searched in the past are fed back to the searching mechanism as an input parameters for future searching, thus the searching proceeds toward the direction determi...