Transposition Algorithms on Very Large Compressed Databases
Harry K. T. Wong, J. Z. Li · Very Large Data Bases · 1986
Transposition is the dominant operation for very large scientific and statistical databases. This paper presents four efficient transposition algorithms for very large compressed scientific and statistical databases. These algorithms operate directly on compressed data without the need to first decompress them. They are applicable to databases that are compressed using the general (and popular) class of methods called run-length encoding scheme. The algorithms have different performance behavior as a function of the database parameters, main memory availability, and the transposition request itself. The algorithms are described and analyzed with respect to the I/O and cpu cost. A decision procedure to select the most efficient algorithm, given a transposition request, is also given. The algorithms have been implemented and the analysis results experimentally validated. 14 refs.