ACM SIGMOD Anthology VLDB dblp.uni-trier.de

A Compression Technique for Large Statistical Data-Bases.

Susan J. Eggers, Frank Olken, Arie Shoshani: A Compression Technique for Large Statistical Data-Bases. VLDB 1981: 424-434
@inproceedings{DBLP:conf/vldb/EggersOS81,
  author    = {Susan J. Eggers and
               Frank Olken and
               Arie Shoshani},
  title     = {A Compression Technique for Large Statistical Data-Bases},
  booktitle = {Very Large Data Bases, 7th International Conference, September
               9-11, 1981, Cannes, France, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1981},
  pages     = {424-434},
  ee        = {db/conf/vldb/EggersOS81.html},
  crossref  = {DBLP:conf/vldb/81},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper we explore the compression of large statistical databases and propose techniques for organizing the compressed data, such that the time required to access the data is logarithmic. Our techniques are variations of run-length encoding, in which modified run-lengths for the series are extracted from the data stream and stored in a header, which is used to form the base level of a B-tree index into the database. The run-lengths are cumulative, and therefore the access time of the data is logarithmic in the size of the header. We discuss the details of the compression scheme and its implementation, present several special cases and give an analysis of the relative performance of the various versions.

Copyright © 1981 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981
Contents BibTeX

References

[1]
...
[2]
...
[3]
Don S. Batory: On Searching Transposed Files. ACM Trans. Database Syst. 4(4): 531-544(1979) BibTeX
[4]
...
[5]
Susan J. Eggers, Arie Shoshani: Efficient Access of Compressed Data. VLDB 1980: 205-211 BibTeX
[6]
...
[7]
Bruce Hahn: A New Technique for Compression and Storage of Data. Commun. ACM 17(8): 434-436(1974) BibTeX
[8]
Michael Hammer, Bahram Niamir: A Heuristic Approach to Attribute Partitioning. SIGMOD Conference 1979: 93-101 BibTeX
[9]
...
[10]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[11]
Per Svensson: On Search Performance for Conjunctive Queries in Compressed, Fully Transposed Ordered Files. VLDB 1979: 155-163 BibTeX
[12]
Robert Endre Tarjan, Andrew Chi-Chih Yao: Storing a Sparse Table. Commun. ACM 22(11): 606-611(1979) BibTeX
[13]
Jacob Ziv, Abraham Lempel: A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory 23(3): 337-343(1977) BibTeX
[14]
Jacob Ziv, Abraham Lempel: Compression of Individual Sequences via Variable-Rate Coding. IEEE Transactions on Information Theory 24(5): 530-536(1978) BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Fri Oct 3 22:46:39 2008