Transposition Algorithms on Very Large Compressed Databases.

Harry K. T. Wong, J. Z. Li: Transposition Algorithms on Very Large Compressed Databases. VLDB 1986: 304-311

@inproceedings{DBLP:conf/vldb/WongL86,
  author    = {Harry K. T. Wong and
               J. Z. Li},
  editor    = {Wesley W. Chu and
               Georges Gardarin and
               Setsuo Ohsuga and
               Yahiko Kambayashi},
  title     = {Transposition Algorithms on Very Large Compressed Databases},
  booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
               August 25-28, 1986, Kyoto, Japan, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1986},
  isbn      = {0-934613-18-4},
  pages     = {304-311},
  ee        = {db/conf/vldb/WongL86.html},
  crossref  = {DBLP:conf/vldb/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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 compressrd 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.

Copyright © 1986 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb7588 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, Yahiko Kambayashi (Eds.): VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings. Morgan Kaufmann 1986, ISBN 0-934613-18-4
Contents

References

[Shoshani 1982]: Arie Shoshani: Statistical Databases: Characteristics, Problems, and some Solutions. VLDB 1982: 208-222
[Shoshani et al.1984]: Arie Shoshani, Frank Olken, Harry K. T. Wong: Characteristics of Scientific Databases. VLDB 1984: 147-160
[Turner et al.1979]: M. J. Turner, R. Hammond, P. Cotton: A DBMS for Large Statistical Databases. VLDB 1979: 319-327
[SAS 1979]: ...
[McCarthy et al.1982]: ...
[Eggers & Shoshani 1980]: Susan J. Eggers, Arie Shoshani: Efficient Access of Compressed Data. VLDB 1980: 205-211
[Aronson 1977]: ...
[Klug 1982]: Anthony C. Klug: Access Paths in the 'ABE' Statistical Query Facility. SIGMOD Conference 1982: 161-173
[Epstein ]: ...
[Klug 1981]: ...
[Tsuda & Sato 1983 a]: Takao Tsuda, Takashi Sato: Transposition of Large Tabular Data Structures with Applications to Physical Database Organization. Acta Inf. 19: 13-33(1983)
[Tsuda & Sato 1983 b]: Takao Tsuda, Akira Urano, Takashi Sato: Transposition of Large Tabular Data Structures with Applications to Physical Database Organization. Acta Inf. 19: 167-182(1983)
[Batory 1979]: Don S. Batory: On Searching Transposed Files. ACM Trans. Database Syst. 4(4): 531-544(1979)
[Floyd 1972]: ...
[Wong & Li ]: ...