Paper Info
Title
A General-Purpose Compression Scheme for Databases
Abstract
Summary form only given. Current adaptive compression schemes such as GZIP and COMPRESS are impractical for database compression as they do not allow random access to individual records. A compression algorithm for general-purpose database systems must address the problem of randomly accessing and individually decompressing records, while maintaining compact storage of data. The SEQUITUR algorithm of Nevill-Manning et al., (1994, 1996, 1997) also adaptively compresses data, achieving excellent compression but with significant main-memory requirements. A preliminary version of SEQUITUR used a semi-static modelling approach to achieve slightly worse compression than the adaptive approach. We describe a new variant of the semi-static SEQUITUR algorithm, RAY, that reduces main-memory use and allows random-access to databases. RAY models repetition in sequences by progressively constructing a hierarchical grammar with multiple passes through the data. The multiple pass approach of RAY uses statistics on character pair repetition, or digram frequency, to create rules in the grammar. While our preliminary implementation is not especially fast, the multi-pass approach permits reductions in compression time, at the cost of affecting compression performance, by limiting the number of passes. We have found that RAY has practicable main-memory requirements and achieves better compression than an efficient Huffmann scheme and popular adaptive compression techniques. Moreover, our scheme allows random access to data and is not restricted to databases of text
Year
DOI
Venue
1999
10.1109/DCC.1999.785676
Data Compression Conference
Keywords
Field
DocType
hierarchical grammar,ray models repetition,compression time-at,general-purpose compression scheme,multiple pass,multi-pass approach,compression performance-by,character pair repetition,digram frequency,multiple pass approach,main-memory use,sequences,database management systems,computer science,ray,frequency,random access,information retrieval,data compression,compression algorithms,statistics,database systems
Data compression ratio,Lossy compression,Grammar-based code,Computer science,Sequitur algorithm,Theoretical computer science,S3 Texture Compression,Data compression,Image compression,Database,Lossless compression
Conference
ISSN
ISBN
Citations 
1068-0314
0-7695-0096-X
3
PageRank 
References 
Authors
0.38
4
3
Name
Order
Citations
PageRank
Adam Cannane1887.88
Hugh E. Williams2104893.45
Justin Zobel36882880.46