Abstract: The ability to perform permutations of large data sets in place reduces the amount of necessary available disk storage. The simplest way to perform a permutation often is to read the records of a data set from a source portion of data storage, permute them in memory, and write them to a separate target portion of the same size. It can be quite expensive, however, to provide disk storage that is twice the size of very large data sets. Permuting in place reduces the expense by using only a small amount of extra disk storage beyond the size of the data set.This paper features in-place algorithms for commonly used structured permutations. We have developed an asymptotically optimal algorithm for performing BMMC (bit-matrix-multiply/complement) permutations in place that requires at most \frac{2N}{BD}\left( 2\ceil{\frac{\rank{\gamma}}{\lg (M/B)}} + \frac{7}{2}\right) parallel disk accesses, as long as M >= 2BD, where N is the number of records in the data set, M is the number of records that can fit in memory, D is the number of disks, B is the number of records in a block, and \gamma is the lower left \lg (N/B) \times \lg B submatrix of the characteristic matrix for the permutation. This algorithm uses N+M records of disk storage and requires only a constant factor more parallel disk accesses and insignificant additional computation than a previously published asymptotically optimal algorithm that uses 2N records of disk storage.
We also give algorithms to perform mesh and torus permutations on a d-dimensional mesh. The in-place algorithm for mesh permutations requires at most 3\ceil{N/BD} parallel I/Os and the in-place algorithm for torus permutations uses at most 4dN/BD parallel I/Os. The algorithms for mesh and torus permutations require no extra disk space as long as the memory size M is at least 3BD. The torus algorithm improves upon the previous best algorithm in terms of both time and space.
David Kotz -- Last modified: Sun Feb 4 21:19:24 1996