Disk allocation methods for parallelizing grid files

摘要

The grid file is a well known access method for multi-dimensionalnand spatial data. The response time needed to process path and rangenqueries on the grid file access method can be improved significantly byndistributing the data pages over multiple disks. The paper explores thendisk allocation methods used to allocate the data pages of grid filenamong a set of disks, which can be accessed in parallel. Given N disks,na perfect allocation will speed up the processing of each query by anfactor of N in this environment. The authors show that no disknallocation is perfect for the set of all orthogonal range queries, evennon uniformly distributed read-only data. They then introduce twonfamilies of allocation methods, namely the Linear allocation method andnthe Lattice allocation method, which are perfect for a large collectionnof interesting path queries (rows, columns, diagonals, anti-diagonals)nand range queries (small rectangles), on an interesting set of datandistributions. They address the issues in extending disk allocationnmethods to general data distributions with random updates. Finally, theynprovide experimental results on the performance of the proposed methodsnand other well known disk allocation methods on different query sets,ndata distributions and data set sizes