Disk Index Compression

Introduction

This is a work in progress page collecting links and describing how the compression of the disk index in BabuDB works.

Related Work

LZO: http://blog.chrisgoffinet.com/2009/06/parallel-lzo-splittable-on-hadoop-using-cloudera/

Super-scalar RAM-CPU cache compression: http://www.cwi.nl/htbin/ins1/publications?request#pdfgz&key#ZuHeNeBo:ICDE:06 presents three light-weight compression/decompression algorithms.

Inverted index compression:

• http://www2009.org/proceedings/pdf/p401.pdf
• http://nlp.stanford.edu/IR-book/html/htmledition/index-compression-1.html

Good background and description of block-level compression, "How to barter bits for chronons: compression and bandwidth trade offs for database scans":

• http://citeseerx.ist.psu.edu/viewdoc/download?doi#10.1.1.102.9090&rep#rep1&type#pdf

HyperTable, BigTable compression:

• http://citeseerx.ist.psu.edu/viewdoc/summary?doi#10.1.1.11.8470
• http://feedblog.org/2008/10/12/google-bigtable-compression-zippy-and-bmdiff/